自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 21:48:52，当前版本为作者最后更新于2022-02-05 10:56:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

*P3424 [POI2005]SUM-Fibonacci Sums

POI 合集。

好题！先求和，再调整。

由于题目给出的 $x, y$ 是齐肯多夫表示法，所以简单地对应位求和 $z = x + y$ 后，$z_i = 0/1/2$。

考虑从高往低位调整，即依次保证长为 $1$ 的前缀，长为 $2$ 的前缀 …… 直到整个数都满足齐肯多夫表示法，类似 数学归纳法。因为从低到高涉及进位，很麻烦。下称满足齐肯多夫表示法为 合法。

我们发现最棘手的是 $z_i = 2$，别的都好办。由于 $0200 = 0111 = 1001$，考虑一次操作 $op(i)$ 表示令 $z_i\gets z_i - 2$，$z_{i + 1}\gets z_{i + 1} + 1$，$z_{i - 2}\gets z_{i - 2} + 1$。此时可能导致低位 $3$ 的出现，但是问题不大，因为我们只关心 $i$ 及其高位。

我们的目标是 尽可能消掉 $2$，自然不希望已经处理好的高位重新出现 $2$。由于 $i + 1$ 及其高位合法，所以不会出现连续的两个 $1$。因此，若 $z_{i + 1} = 1$ 且 $z_i \geq 2$，$op(i)$ 会令 $z_{i + 1}$ 变成 $2$。

不妨先执行进位操作，即 $z_i \gets z_i - 1$，$z_{i + 1}\gets z_{i + 1} - 1$，$z_{i + 2}\gets z_{i + 2} + 1$。由于 $z_{i + 2}$ 一定等于 $0$，所以进位后等于 $1$。同时，若 $z_{i + 3} = 1$，那么继续进位到 $z_{i + 4}$。称从 $i$ 开始不断进位的过程为 $\mathrm{flush}(i)$，其代码如下：

void flush(int p) {while(z[p] && z[p + 1]) z[p + 2]++, z[p]--, z[p + 1]--, p += 2;}

注意，当 $i + 1$ 及其高位均合法时，操作才不会出错，即操作结束后 $i + 1$ 及其高位仍合法。容易证明这一点。否则可能出现数码 $2$。如当 $z_i = z_{i + 1} = z_{i + 2} = 1$ 时，这样的进位导致 $z_{i + 2} = 2$，破坏了齐肯多夫表示法，但若 $i + 1$ 及其高位合法，则不会出现 $z_{i + 1} = z_{i + 2} = 1$ 的情况。

执行完 $0$ 或 $1$ 次进位操作后，$z_{i + 1} = 0$，因此若 $z_i \geq 2$，再执行 $\mathrm{op}(i)$ 仅会将 $z_{i + 1}$ 变为 $1$，且由于 $z_i\leq 3$，故现在所有 $i$ 及其高位均有 $z \leq 1$，但 $i + 1$ 及其高位不一定合法，因为可能 $z_{i + 1} = z_{i + 2} = 1$。由于此时 $i + 2$ 及其高位合法，所以先 $\mathrm{flush}(i + 1)$，再 $\mathrm{flush}(i)$ 即可保证对于得到的结果，$i$ 及其高位合法。

啰里啰嗦这么一大堆，只是为了严谨证明以下做法的正确性：

• 从高到低考虑每一位 $i$。保证 $i + 1$ 及其高位合法。
• 首先 $\mathrm{flush}(i)$。
• 若 $z_i \geq 2$，则依次执行 $\mathrm{op}(i)$，$\mathrm{flush}(i + 1)$，$\mathrm{flush}(i)$。
• 此时 $i$ 及其高位合法。

特殊情况：$\mathrm{op}(2)$ 令 $z_1\gets z_1 + 1$，$z_2 \gets z_2 - 2$，$z_3\gets z_3 + 1$。$\mathrm{op}(1)$ 令 $z_1\gets z_1 - 2$，$z_2\gets z_2 + 1$。不难发现我们对高位的影响最多仅是令 $z_{i + 1}$ 加 $1$，和普通的 $\mathrm{op}(i)\ (i > 2)$ 是一样的，故特殊情况也一定合法。

时间复杂度分析：考虑 $d = \sum z_i$，每次进位均会让 $d$ 减少 $1$，而 op 不改变 $d$，故 flush 的总复杂度均摊为 $d$，即总时间复杂度线性。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5;
int n, m, x[N];
void flush(int p) {while(x[p] && x[p + 1]) x[p + 2]++, x[p]--, x[p + 1]--, p += 2;}
int main() {
	cin >> n; for(int i = 1; i <= n; i++) scanf("%d", &x[i]);
	cin >> m; for(int i = 1, y; i <= m; i++) scanf("%d", &y), x[i] += y;
	if(m > n) n = m;
	for(int i = n; i; i--) {
		flush(i);
		if(x[i] >= 2) {
			if(i >= 2) x[i] -= 2, x[max(1, i - 2)]++, x[i + 1]++;
			else x[i + 1]++, x[i] -= 2;
			flush(i + 1), flush(i);
		}
	} for(int i = n + 2; i; i--) if(x[i]) {cout << (n = i) << " "; break;}
	for(int i = 1; i <= n; i++) putchar(x[i] + '0'), putchar(' ');
	return 0;
}