题目大意#

已知异或的差分(异或意义的差分)，求原数组，要求原数组是一个排列

分析#

异或又称模二加（其实也是模二减，所以自己才能消去自己），加法有的性质它都有。本题相当于是给了差分，在不知道初始项的情况下求原数组。我们可以假设 a1 = 0 ，先得到一个数组。根据异或的性质可知这个数组与答案只相差一个整体异或的偏移量shift。

解决#

如何求这个偏移量？

由于题目保证答案一定存在，所以我们只需要尽量让数组接近答案就够了。

已知答案是一个0-n-1的排列。我们按位来考虑，对于某一个二进制位， $\sum (ans_i==0) >= (\sum ans_i==1)$ 恒成立

也就是说如果我们发现构造出的数组中某一位二进制上1比0多就翻转一下。

复杂度 $O(nlogn)$

代码#

1
void solve()
2
{
3
    int n;
4
    cin >> n;
5
    for (int i = 1; i < n; i++)
6
    {
7
        cin >> a[i];
8
    }
9
    int tmp=0;
10
    for(int i=0;i<n;i++)
11
    {
12
        tmp^=a[i];
13
        ans[i]=tmp;
14
    }
15
    int shift=0;
16
    for(int i=0;i<25;i++)
17
    {
18
        int cnt=0;
19
        for(int j=0;j<n;j++)
20
        {
21
            cnt+=ans[j]>>i&1;
22
        }
23
        if(cnt>n-cnt)
24
        {
25
            shift+=1ll<<i;
26
        }
27
    }
28
    for(int i=0;i<n;i++)
29
    {
30
        cout<<(ans[i]^shift)<<' ';
31
    }
32
    cout<<endl;
33
}