https://codeforces.com/problemset/problem/1895/D

题目大意

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

分析

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

解决

如何求这个偏移量？

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

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

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

复杂度$O(nlogn)$

代码

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