练习赛的时候这道题死活超时....想到了高位确定后..低位不能对高位产生影响..并且高位要尽可能的为1..就是想不出比较好的方法了实现...
围观大神博客..
思路很清晰了..没什么补充的..自己的思维还是不够啊...大神几句话点拨...豁然开朗...
Program:
#include#include #include #include #include #include #include #define oo 1000000007#define ll long long#define pi acos(-1.0)using namespace std;struct node{ int son[2]; ll w;}p[10000005];ll a[100005],totol,ans,_2jie[45];int num;void InsertToTrie(ll x){ int h=0,i,t; for (i=40;i>=0;i--) { if (x & _2jie[i]) t=1; else t=0; if (!p[h].son[t]) p[h].son[t]=++num; h=p[h].son[t]; } p[h].w=x; return;}ll SerchMax(ll x){ int h,i,t; h=0; for (i=40;i>=0;i--) { if (x & _2jie[i]) t=1; else t=0; if (p[h].son[1-t]) h=p[h].son[1-t]; else h=p[h].son[t]; } return p[h].w;} int main(){ int i,n; ll prefix,postfix; _2jie[0]=1; for (i=1;i<=40;i++) _2jie[i]=_2jie[i-1]*2; while (~scanf("%d",&n)) { postfix=0; for (i=1;i<=n;i++) scanf("%I64d",&a[i]),postfix^=a[i]; memset(p,0,sizeof(p)); ans=postfix; num=0; prefix=0; InsertToTrie(0); for (i=1;i<=n;i++) { prefix^=a[i]; InsertToTrie(prefix); postfix^=a[i]; ans=max(ans,SerchMax(postfix)^postfix); } printf("%I64d\n",ans); } return 0;}