526互联

Educational Codeforces Round 157 D

发布时间 2023-11-10 14:16:07作者: ycllz

tilian
不太会这种题
发现找到一个数就能确定整个序列
然后转而发现 前缀异或和
b1 ^ b2 = a1
b1 ^ b3 = a2
...
我们发现要是n为偶数时能直接求出b1从而确定整个序列
而为奇数时我们无法确定b1
我们思考拆位之后 如果b1该位为0 算出真实的异或后的0 1 个数 b1该位为1 算出真实的异或后的0 1 个数
再与a1 a2 a3 该位上的0 1 个数看是否符合即可

int n,a[200010];
void solve() {
    cin>>n;
    for(int i=0;i<n-1;i++)cin>>a[i];
    for(int i=1;i<n-1;i++)a[i]^=a[i-1];
    int x=0;
    for(int i=0;i<20;i++){
        vector<int>cnt(2),res(2);
        for(int j=0;j<n;j++)res[j>>i&1]++;
        for(int j=0;j<n-1;j++)cnt[a[j]>>i&1]++;
        if(cnt[1]!=res[1])x|=1<<i;
    }
    cout<<x<<' ';
    for(int i=0;i<n-1;i++)cout<<(a[i]^x)<<' ';
}