A. 相遇问题

简要题意

一个无限长的楼梯上站着两个人，其中一个人在第 $a$ 级台阶上，另一个人在第 $b$ 级台阶上。

每个人移动 $i$ 次的时候消耗的体力为 $i$，每一次可以向上或向下移动 $1$ 阶台阶，求两人相遇时消耗体力之和的最小值。

解题思路

考虑贪心策略。

显然，两人相向而行是需要的移动次数最少。同时可以发现两人移动的步数越接近得到的解越优（即移动的步数越平均越好），按这样的策略移动可以得到答案。

设移动的总步数为 $s$，则 $s = max(a,b)-min(a,b)$ ，则第一个人移动的步数为 $t_1 = \left \lfloor \frac{s}{2} \right \rfloor$ ，第二个人移动的步数为 $t_2 = \left \lceil \frac{s}{2} \right \rceil$ （或者 $t_2 = s - t_1$），两人消耗的体力分别为 $\frac{(t_1 + 1) \times t_1}{2}$ 、 $\frac{(t_2 + 1) \times t_2}{2}$。求和即可。

正确代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>

using namespace std;

typedef long long ll;
int a, b;

int main()
{
    cin >> a >> b;
    if (a > b) swap(a, b);
  	int s = b - a;
    int t1 = s / 2;
    int ans = t1 * (t1 + 1) / 2 + (s - t1) * (s - t1 + 1) / 2;
    cout << ans << endl;
    return 0;
}

B. 砝码称重

简要题意

给定一个整数 $n$，可以无限制的选取重量在 $1～n$ 之间的砝码，求可以凑出 $1～n$ 任意正整数所需要的最少的砝码数量。

解题思路

与第一题相比难度跨跃不大，门槛在读题。考察的是二进制。冷静思考一下还是很容易的。

任何一个数都可以由 $2$ 的整数次幂之和构成，因此，只需要求出 $n$ 的二进制表示下为 $1$ 的最高位，将这一位到第 $1$ 位所代表的 $2$ 的整数次幂全部选上，则 $1～n$ 之间所有的重量都可以凑出。

代码运用了一点小技巧，可能会难理解一些。

正确代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>

using namespace std;

int n, ans;

string tobin(int x) // 将 10 进制的 x 转换为 2 进制。
{
	string res;
	while (x > 0) res += to_string(x % 2), x /= 2;
	return res;
}

int main()
{
	cin >> n;
	string bin = tobin(n);
	for (ans = bin.size() - 1; ans >= 0; ans -- ) // 倒序枚举
		if (bin[ans] == '1') break;
	cout << ans + 1 << endl;
	return 0;
}

C. 数列

简要题意

有一个整数数列 $a_0,a_1,a_2,a_3 …$，给出数列的前两项，其它项可以通过如下递推式求出：

$$a_n = p \times a_{n-1} + q \times a_{n-2}, n \ge 2$$

给定一个可能 非常大 的正整数 $N$ 和两个不大的正整数 $M,K$，分别计算并输出 $a_{N+1},a_{N+2},\dots,a_{N+K}$ 对 $M$ 取模的值。

数据范围

前三个测试点满足 $0 < a_0,a_1,p,q,M,K,N \le 10$。

所有测试点满足 $0 < a_0,a_1,p,q \leq 32693$，$0 < M \leq 3 \times 10^3$，$0 < K \leq 10^4$，$0 < N < 10^{10^6}$。

注意，$N$ 最多有 $10^6$ 位数。

解题思路

递推式其实是广义斐波那契数列。

这题是这场比赛的压轴题。

可以发现，在模意义下，斐波那契数列的第 $n + 1$ 项 $F_{n+1}$ 仅取决于（$p *F_{n-1} \ \text{mod} \ m$ 和 $q * F_{n} \ \text{mod} \ m$），不难发现，这个二元组有 $m^2$ 种取值，因此，在模意义下，斐波那契数列一定会最终产生循环，即当 $n$ 足够大时，一定会出现 $F_{n}=F_{n-k}$ 的情况。

由于 $n$ 可能 非常大，所以需要采取特殊的取模方法，这里采用 秦九韶算法。

取模减法可能会出现负数，要用到取模防负小技巧：

这题细节很多，写的时候要注意一下。

正确代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

#define endl '\n'

const int N = 1e7 + 10, M = 3010;

string n;
int m, k, p, q;
int a[N], id[M][M];

void print(int a, int b)
{
    for (int i = 0; i < k; i ++ )
    {
        int c = (p * b + q * a) % m;
        a = b, b = c;
        cout << a << endl;
    }
}

int mod(int len)
{
    int res = 0;
    for (auto c : n) res = (res * 10 + c - '0') % len;
    return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> a[0] >> a[1] >> p >> q;
    cin >> m >> k >> n;

    a[0] %= m, a[1] %= m;
    id[a[0]][a[1]] = 1;

    for (int i = 2; i < N; i ++ )
    {
        a[i] = (p * a[i - 1] + q * a[i - 2]) % m;
        auto& t = id[a[i - 1]][a[i]];
        if (t && n.size() > 7)
        {
            int len = i - t;
            int r = (mod(len) - t % len + len) % len; // 取模减法防负技巧。
            print(a[t + r], a[t + r + 1]);
            break;
        }
        t = i;
    }

    if (n.size() <= 7) print(a[stoi(n)], a[stoi(n) + 1]);
    return 0;
}

D. Yih 的线段树

简要题意

Yih 使用下面代码构造了一颗线段树：

void build(int x, int l, int r) {
    vis[x] = 1;
    if(l == r) return;
    int mid = (l + r) >> 1;
    build(x << 1, l, mid);
    build(x << 1 | 1, mid + 1, r);
}

对于一个数 $x$，若存在一个 $n$ 满足执行完 build(1,1,n) 后 $x$ 是最后一个被创建的节点，则称 $x$ 为 Yuzu 数。

Yih 想让你帮忙探索 Yuzu 数的性质。

有 $Q$ 组询问，每组询问给定一个正整数 $x$，对于每一组询问，输出 $x$ 是否为 Yuzu 数。

解题思路

暴力出奇迹，打表拿省一。再次印证。

直接看题没什么思路，看到数据范围超级大，想到打表找规律，把上面那段线段树代码搞上，发现有这样一个规律：

打表发现二进制下每一个 Yuzu 数都是由一堆 $1$ 后面接着一堆 $0$ 最后再加上一个 $1$ 构成的，为了方便，我们去掉最后一个 $1$，于是就很简单了。

没什么细节，很轻松就过掉了。

正确代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int t, n;

int main()
{
    cin >> t;
    while (t -- )
    {
        string bin;
        cin >> n;
        bool flag = n % 2;

        while (n) bin += to_string(n % 2), n /= 2;
        reverse(bin.begin(), bin.end());
        bin.pop_back();
        while (bin.back() == '0') bin.pop_back();

        for (int i = 0; i < bin.size(); i ++ )
            if (bin[i] == '0') flag = false;

        puts(flag ? "Y" : "N");
    }
    return 0;
}

然后就 $\text{AK}$ 了。

参考资料

1. 斐波那契数列的简单性质，博客园，changle_cyx，2020 年 2 月 2 日。
2. 数列（CSP-J 2022 模拟赛），AcWing，yxc，2022 年 8 月 14 日。