题解：P10307 「Cfz Round 2」Binary

szh_AK_all · 2024-04-04 21:04:31 · 题解

这题挺巧妙的。

分析

可以想想，对于一个数 x，x+1 在什么情况下会对答案产生贡献？假设在二进制下 x+1 在 x 的基础上产生了 k 个进位，也就是说 x 在二进制下第 0,1,\dots,k-1 位都由 1 变为了 0，而第 k 位则由 0 变为了 1，而其他位则不变。那么，也就是说，当 a_0⊕a_1⊕\dots a_k-1=a_k 时，会对答案产生贡献。

所以，可以枚举进位个数 i，若 a_0⊕a_1⊕\dots a_{i-1}=a_i，则答案会增加。那么会增加多少呢？用排列组合的思想，即在 n 位下已经确定了 i+1 位的数字个数，也就是对于第 i+2,i+3,\dots n 位来说，可以有两种选择：该位为 0 或者 1，所以这样的数字个数为 2^{n-(i+1)}。由于题目要求用二进制的形式输出答案，所以在用二进制存储答案的数组的第 n-(i+1) 设为 1 即可。

还需注意判断边界，即 i=0 或 i=n 的情况，若它们满足条件，则各自会产生 1 的贡献，即答案的第 0 位增加 1。由于第 0 位可能会增加两个 1，所以要处理下进位。

Code

#include <bits/stdc++.h>
using namespace std;
int a[200005];
int k[200005];//记录答案
int qian[200005];

int qpow(int a, int b) {//没用，就当做防抄袭吧
    int ans = 1;
    while (b) {
        if (b & 1)
            ans *= a;
        a *= a;
        b /= 2;
    }
    return ans;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        scanf("%d", &n);
        for (int i = 1; i <= n + 1; i++) {
            scanf("%d", &a[i]);
            qian[i] = qian[i - 1] ^ a[i];
        }
        for (int i = 0; i < n; i++) {
            if (i == 0 && a[1] == 0)
                k[n - 1]++;
            else if (i != 0) {
                if (qian[i] == a[i + 1])
                    k[n - (i + 1)]++;
            }
        }
        if (qian[n] == a[n + 1])
            k[0]++;
        for (int i = 0; i <= n; i++) {
            k[i + 1] += k[i] / 2;
            k[i] %= 2;
        }
        int tot = n;
        while (tot > 0 && k[tot] == 0)
            tot--;
        for (int i = tot; i >= 0; i--) {
            cout << k[i];
            k[i] = 0;//记得清空
        }
        cout << endl;
    }
}