CodeForces - 1174D Ehab and the Expected XOR Problem(构造+思维+位运算)

题目链接：点击查看

题目大意：给出一个 n，再给出一个 x，要求构造一个数列，满足该数列的所有子串的异或和都不等于 0 且都不等于 x，在满足上面的条件下尽可能长

题目分析：因为这个题目最终的目标是需要让所有的“子串”的异或和都不等于某个值，因为是连续的，所以不难想到可以对于答案数组求一下前缀异或和，此时所有的“子串”都可以通过前缀异或和的任意两个数字表示出来，如 ( a[ l ] xor a[ l + 1 ] xor ... xor a[ r - 1 ] xor a[ r ] ) = sum[ r ] xor sum[ l - 1 ]

那么我们现在的目标就转换成，构造出一个前缀异或和，需要满足以下两个条件：

任意两个数字不能相等（满足所有子串的异或和都不等于 0）

任意两个数字的异或和不能等于 x（满足所有子串的异或和都不等于 x）

更具体的，对于某个数字 i 来说，i 和 i xor x 这两个数只能选择一个，所以我们扫一遍能选则选就好了

最后构造出来的是一个前缀异或和，如果想要还原原数组的话，可以利用 a[ i ] = sum[ i ] xor sum[ i - 1 ] 进行还原

代码：
 

//#pragma GCC optimize(2) //#pragma GCC optimize("Ofast","inline","-ffast-math") //#pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e6+100;bool vis[N];int main() { #ifndef ONLINE_JUDGE // freopen("data.ans.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n,x;scanf("%d%d",&n,&x);vector<int>ans;vis[0]=vis[x]=true;for(int i=1;i<1<<n;i++)if(!vis[i]){vis[i]=vis[i^x]=true;ans.push_back(i);}printf("%d\n",ans.size());int pre=0;for(auto it:ans){printf("%d ",it^pre);pre=it;}return 0; }

 

总结

以上是生活随笔为你收集整理的CodeForces - 1174D Ehab and the Expected XOR Problem(构造+思维+位运算)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。