526互联

Educational Codeforces Round 157 (Rated for Div. 2) D. XOR Construction

发布时间 2023-11-05 00:19:48作者: My_opt

原题链接

解读一下题意：给一个长度n-1的数组，让你找到一个长度为n的数组b，并且是0到n-1的全排列，使得bi异或bi+1对于ai。
这道题乍一看没什么思路，但是仔细一想会发现其实考察的就是异或的性质。我们可以发现：如果a异或b等于c，那么abc任意两个异或都能得到另外一个，所以只要初始的b0确定了，那么后面整个b数组都唯一确定。那么要如何求b0呢？
我们要继续观察，我们拿到的a数组，和我们最后想要求出来的b数组之间有什么关系？以及，我们的初始的b0，是如何影响到a数组使之变成b的？
这里还是利用的异或的性质：我们单独考虑所有数在每一位的1的异或，如果是奇数次1，那么异或的结果一定还是1，偶数次则一定是0。也就是说，b0的某一个比特位为1，那么就可以直接改变整个a数组的异或结果（奇偶互换）。
而我们的目标数组也就是0到n-1的全排列在某一位的奇偶性是固定的，因此就可以反过来通过a数组退出b0是否需要在某一位为1。

#include <bits/stdc++.h>

using namespace std;

#define int long long

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n);
    map<int, int> mp;
    for (int i = 1; i < n; i++) {
        cin >> a[i];
        a[i] ^= a[i - 1];
        for (int bit = 0; bit < 32; bit++) {
            mp[bit] += (a[i] >> bit) & 1;
        }
    }

    int mask = 0;
    for (int bit = 0; bit < 32; bit++) {
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            cnt += (i >> bit) & 1;
        }
        //如果这一位1的个数不一样，说明需要用异或去改变
        if (mp[bit] != cnt) {
            mask |= (1 << bit);
        }
    }

    cout << mask << ' ';
    for (int i = 1; i < n; i++) {
        cout << (a[i] ^ mask) << " \n"[i == n - 1];
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}