D. Ehab and the Expected XOR Problem

链接

[https://codeforces.com/contest/1174/problem/D]

题意

让你构造一个数组,使得任意子段异或和不为0也不为x,而且每个数字大于等于1小于(1<<n)

分析

比赛做不出来,还是太垃圾了,这只能说水平不够。而且我对位运算的题真的不敏感。
以后专门刷下位运算题。
我是看官方题解,知道的。首先有前缀异或和数组。
al⊕al+1⋯⊕ar=bl−1⊕br.,好有了这个之后,我们反向先把前缀异或和数组求出来。
对于a的任意子段都可以从b数组得到。看哪个表达式就知道了,那么使得a任意子段异或和不为0也不为x,
那么b的任意两两不能相等,如果有相等,就一定有某个子段a为0.为了a任意子段异或也不为x,那么b两两不能异或和为x.
既然把b求出来了,ai=bi⊕bi−1.这技巧确实学到了,而且对异或的性质更加深入了。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=4e6;
int s[N];

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n,x;
    while(cin>>n>>x){
        set<int> se;
        int cnt=0;
        se.insert(0);
        for(int i=1;i<(1<<n);i++){
            if(!se.count(i^x)){
                s[++cnt]=i;
                se.insert(i);
            }
        }
        cout<<cnt<<endl;
        for(int i=1;i<=cnt;i++)
        cout<<(s[i]^s[i-1])<<' ';
        cout<<endl;
    }
    return 0;
}
上一篇:如何开始TDD


下一篇:《剑指offer》第五十一题(数组中的逆序对)