D. XOR Construction

题解

首先根据b1⊕b2=a1，b2⊕b3=a2...bj⊕bj+1=aj

我们不难得出b1​⊕bj+1=a1⊕a2⊕a3....⊕aj

因此我们只需要确定b1的值就能够确定其余所有bi的值，而题目又要求我们的b处于0~n-1范围内，这实际上实在寻找一个 b1​ 使得异或出来的所有值越小越好，所以我们拆位，假设所有数字的第 i 位为 1的个数大于为 0 的个数，那我们最好异或上一个 2^i，这样可以使大部分数字变小。

正确性证明：首先b要求的结果一定是0~n-1，其和是固定的，即n*（n-1）/2，然后我们让所有前缀异或上一个b1，因为前缀异或必然不同（题目说明一定有解），所以每个bi也一定不同，那么我们想竭尽全力让所有数字和最小也只有这么做（贪心）才能实现。

code

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int a[N];
int main(){
    int n,ans=0;
    cin>>n;
    for (int i=1;i<n;i++){
        cin>>a[i];
        a[i]^=a[i-1];
    }
    for (int i=20;i>=0;i--){
        int n1=0,n2=0;
        for (int j=n-1;j>=0;j--)
            if (a[j]>>i&1==1) n1++;
            else n2++;
        if (n1>n2) ans|=1<<i;
    }
    cout<<ans;
    for (int i=1;i<n;i++) cout<<" "<<(ans^a[i]);
    return 0;
}