P3424 [POI2005]SUM-Fibonacci Sums

· · 题解

*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 及其高位合法。

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

特殊情况：\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;
}