CF1592E Bored Bakry

題意：找出最長的區間 \([l,r]\) 滿足 \(a_{l}\&a_{l+1}\&\dots\&a_{r-1}\&a_{r}>a_{l}\oplus a_{l+1}\oplus\dots\oplus a_{r-1}\oplus a_{r}\) 。

首先發現如果有一段滿足這個條件的區間，那么一定有一個(較高的)二進制滿足：這個區間中的所有數的這一位都是 \(1\) 且數量為偶數。

又考慮到如果有更高位滿足了這個條件，低位都不用再考慮了。

但是如果在這一位滿足條件時，存在更高位的 \(\&\) 比 \(\oplus\) 小怎么辦？

那么考慮強制規定更高為的異或和為 \(0\) ，可以證明在枚舉到更高位時情況沒有算漏。

因此枚舉滿足條件的二進制位，找出一段極長的區間滿足這一段區間中忽略比這一位第的二進制位后異或之和為 \(0\) 。

$\texttt{code}$ n=rd(); for(int i=1;i<=n;i++) a[i]=rd(); memset(exist,-1,sizeof(exist)); for(int p=0;p<=20;p++) {tot0[cnt=1]=0;for(int i=1;i<=n;i++) if(!((a[i]>>p) & 1)) tot0[++cnt]=i;tot0[++cnt]=n+1;for(int i=2,l,r;i<=cnt;i++){l=tot0[i-1]+1,r=tot0[i]-1;for(int j=l;j<=r;j++) xorsum[j]=xorsum[j-1]^(a[j]>>p);exist[0]=l-1;for(int j=l;j<=r;j++){if(exist[xorsum[j]]!=-1) ans=max(ans,j-exist[xorsum[j]]);else exist[xorsum[j]]=j;}exist[0]=0;for(int j=l;j<=r;j++) exist[xorsum[j]]=-1,xorsum[j]=0;} } printf("%d\n",ans);

總結

以上是生活随笔為你收集整理的【做题记录】位运算的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。