首页 > 其他 > 详细

bzoj4260: Codechef REBXOR

时间：2016-07-20 22:50:47 阅读：319 评论：0 收藏：0 [点我收藏+]

求异或maxmin一般用trie （二进制式的trie）。query中找的是满足((x>>i)&1)^A=1，那么A=((x>>i)&1)^1；maxx=max(sumx,sumi)(i=[1,x])。(YY一下异或的性质

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define REP(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define clr(x,c) memset(x,c,sizeof(x))
int read(){
	int x=0;char c=getchar();bool f=true;
	while(!isdigit(c)){
		if(c==‘-‘) f=false;c=getchar();
	}
	while(isdigit(c)) x=x*10+c-‘0‘,c=getchar();
	return f?x:-x;
}
const int nmax=400005;
const int maxn=10000005;
int seq[nmax],chd[maxn][2],sum[nmax],ll[nmax],rr[nmax],pt,n;
void init(){
	n=read();
	REP(i,1,n) seq[i]=read();
}
void insert(int x){
	int cur=0;
	dwn(i,30,0){
		int v=(x>>i)&1;
		if(!chd[cur][v]) chd[cur][v]=++pt;
		cur=chd[cur][v];
	}
}
int query(int x){
	int ans=0,cur=0;
	dwn(i,30,0){
		int v=((x>>i)&1)^1;
		if(chd[cur][v]) ans|=(1<<i),cur=chd[cur][v];
		else cur=chd[cur][v^1];
	}
	return ans;
}
void work(){
	clr(chd,0);pt=0;insert(sum[0]=0);
	REP(i,1,n) sum[i]=sum[i-1]^seq[i],ll[i]=max(ll[i-1],query(sum[i])),insert(sum[i]);
	clr(chd,0);pt=0;insert(sum[n+1]=0);
	dwn(i,n,1) sum[i]=sum[i+1]^seq[i],rr[i]=max(rr[i+1],query(sum[i])),insert(sum[i]);
	int ans=-1;
	REP(i,1,n-1) ans=max(ans,ll[i]+rr[i+1]);
	printf("%d\n",ans);
}
int main(){
	init();work();return 0;
}