「Cfz Round 2」Binary 题解

__ryp__ · 2024-04-04 16:09:08 · 题解

题意还是比较明确的。首先我们需要知道异或的两个性质：a\oplus a = 0 与 a\oplus 0 = a。

遇到没思路的时候，先来看几个栗子：

观察到：如果 u + 1 进了 k 位，就有 f(u + 1) = f(u)\oplus \sigma_k，其中 \sigma_k = \bigoplus\limits_{i=0}^k a_i，即 a 的前缀异或和。由题意，f(u + 1) = f(u)，故 \sigma_k = 0。然后考虑怎么统计答案。

如果 u + 1 进了 k 位，就意味着它的低 k 位全都是 1，那么就剩下 n - k - 1 位可以选，也就是 2^{n - k - 1} 种方案。

换句话说，每一个 \sigma_k = 0 的 k，都会产生 2^{n - k - 1} 的贡献。 题意中让我们输出二进制表示，于是我们将答案的第 n - k - 1 位置一即可。

最后考虑一个边缘情况：\sigma_n = 0，即样例二。这种情况特判，将最终答案加一即可。

赛时码：

#include <iostream>
using namespace std;
const int N = 2e5 + 10;
int res[N];

int main (void)
{
    int t;

    ios::sync_with_stdio (false), cin.tie (0), cout.tie (0);
    cin >> t;
    while (t--) {
        int n, sum = 0, high = 0;

        cin >> n;
        for (int i = 0; i <= n; i++) {
            int v;
            cin >> v;
            if ((sum ^= v) == 0 && i < n) res[n - i - 1] = 1, high = max (high, n - i - 1);
        }

        if (!sum) {
            int q = 0;
            while (res[q]) res[q++] = 0;
            res[q] = 1;
        }
        for (int i = high; i >= 0; i--) cout << res[i];
        cout << '\n';
        for (int i = 0; i <= high; i++) res[i] = 0;
    }
    return 0;
}