首页 > 代码库 > BZOJ 4260 REBXOR
BZOJ 4260 REBXOR
TMD我怎么卡了这么久的常啊。。。。
就枚举分割点,左手一颗trie,右手一颗trie,就好了。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 400050 using namespace std; int n,a[maxn],x[maxn],root,ls[maxn*32],rs[maxn*32],tot=0; int mx[maxn],ans=0; int read() { char ch;int data=http://www.mamicode.com/0; while (ch<‘0‘ || ch>‘9‘) ch=getchar(); while (ch>=‘0‘ && ch<=‘9‘) { data=data*10+ch-‘0‘; ch=getchar(); } return data; } int ask(int now,int val,int bit) { if (!now) return 0; int ans=0; for (int i=bit;i>=0;i--) { int nb=val&(1<<i); if (!nb) { if (rs[now]) {now=rs[now];ans+=(1<<i);} else now=ls[now]; } else { if (ls[now]) {now=ls[now];ans+=(1<<i);} else now=rs[now]; } } return ans; } void modify(int now,int val,int bit) { int pos=now; for (int i=bit;i>=0;i--) { int nb=val&(1<<i); if (!nb) {if (!ls[pos]) ls[pos]=++tot;pos=ls[pos];} else {if (!rs[pos]) rs[pos]=++tot;pos=rs[pos];} } } int main() { n=read();tot=root=1; for (int i=1;i<=n;i++) {a[i]=read();x[i]=x[i-1]^a[i];} for (int i=1;i<=n;i++) { mx[i]=max(max(x[i],mx[i-1]),ask(root,x[i],30)); modify(root,x[i],30); } for(int i=1;i<=tot;i++) ls[i]=rs[i]=0; tot=root=1; for (int i=n;i>=1;i--) { int ret=ask(root,x[i],30); ans=max(ans,ret+mx[i-1]); modify(root,x[i],30); } printf("%d\n",ans); return 0; }
BZOJ 4260 REBXOR
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。