題目大意：

給出一個數列，求最大區間異或和。 異或和相同時取終點最靠前的，仍相同取最短的。 ? 簡單題解： 先求出前綴和。 對每個數，將其前一項的前綴和插入0-1樹中。 然后在該樹中，從高位到低位（貪心思想），查詢與當前前綴和的各位盡可能不同的前綴。 然后更新答案。 ? 我的代碼： 1 /* 2 ID:t-x.h1 3 LANG:C++ 4 TASK:cowxor 5 */ 6 #include<cstdio> 7 #include<cstring> 8 FILE *fi=fopen("cowxor.in","r"),*fo=fopen("cowxor.out","w"); 9 const int MAXn=100000+9,MAXt=9*MAXn; 10 int a[MAXn]; 11 int next[MAXt][2],pos[MAXt],num=1; 12 int main() 13 { 14 int n,i,j,k,ans=0,ansx=1,ansy=1; 15 fscanf(fi,"%d",&n); 16 for(i=1;i<=n;++i) 17 { 18 fscanf(fi,"%d",a+i); 19 a[i]^=a[i-1]; 20 21 //插入前一項 22 for(k=1,j=20;j>=0;--j) 23 { 24 if(!next[k][(a[i-1]>>j)&1]) 25 next[k][(a[i-1]>>j)&1]=++num; 26 pos[ k=next[k][(a[i-1]>>j)&1] ]=i; 27 } 28 29 //查詢當前項 30 31 for(k=1,j=20;j>=0;--j) 32 33 if(next[k][!( (a[i]>>j)&1 )]) 34 k=next[k][!( (a[i]>>j)&1 )]; 35 else 36 k=next[k][(a[i]>>j)&1]; 37 if(pos[k] && (a[i]^a[pos[k]-1])>ans) 38 ans=a[i]^a[pos[k]-1],ansx=pos[k],ansy=i; 39 } 40 fprintf(fo,"%d %d %d\n",ans,ansx,ansy); 41 fclose(fi); 42 fclose(fo); 43 return 0; 44 }

?

轉載于:https://www.cnblogs.com/txhwind/archive/2012/08/18/2645374.html

總結

以上是生活随笔為你收集整理的USACO 6.1.3 Cow XOR的全部內容，希望文章能夠幫你解決所遇到的問題。

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