D. Ehab and the Expected XOR Problem

深藏阁楼爱情的钟 2021-11-29 10:48 137阅读 0赞

### 链接 ###

\[[https://codeforces.com/contest/1174/problem/D][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;
    }

转载于:https://www.cnblogs.com/mch5201314/p/10973140.html

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