題目鏈接：點(diǎn)擊查看

題目大意：給出一個(gè) n，再給出一個(gè) x，要求構(gòu)造一個(gè)數(shù)列，滿足該數(shù)列的所有子串的異或和都不等于 0 且都不等于 x，在滿足上面的條件下盡可能長(zhǎng)

題目分析：因?yàn)檫@個(gè)題目最終的目標(biāo)是需要讓所有的“子串”的異或和都不等于某個(gè)值，因?yàn)槭沁B續(xù)的，所以不難想到可以對(duì)于答案數(shù)組求一下前綴異或和，此時(shí)所有的“子串”都可以通過(guò)前綴異或和的任意兩個(gè)數(shù)字表示出來(lái)，如 (?a[ l ] xor a[ l + 1 ] xor ... xor a[ r - 1 ] xor a[ r ] )?= sum[ r ] xor sum[ l - 1 ]

那么我們現(xiàn)在的目標(biāo)就轉(zhuǎn)換成，構(gòu)造出一個(gè)前綴異或和，需要滿足以下兩個(gè)條件：

任意兩個(gè)數(shù)字不能相等（滿足所有子串的異或和都不等于 0）

任意兩個(gè)數(shù)字的異或和不能等于 x（滿足所有子串的異或和都不等于 x）

更具體的，對(duì)于某個(gè)數(shù)字 i 來(lái)說(shuō)，i 和 i xor x 這兩個(gè)數(shù)只能選擇一個(gè)，所以我們掃一遍能選則選就好了

最后構(gòu)造出來(lái)的是一個(gè)前綴異或和，如果想要還原原數(shù)組的話，可以利用 a[ i ] = sum[ i ] xor sum[ i - 1 ] 進(jìn)行還原

代碼：
?

//#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; }

?

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 1174D Ehab and the Expected XOR Problem(构造+思维+位运算)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。