AcWing 3485. 最大异或和
原题链接
中等
作者:
术
,
2021-05-11 20:48:57
,
所有人可见
,
阅读 341
`#include <iostream>
using namespace std;
const int N=100005*31;
int m,n;
int s[N];
int a[N];
int son[N][2];//字典树
int idx;
int cnt[N];
void insert(int x,int v){//v=1为插入,-1为删除
//cout<<x<<v<<endl;
int p=0;//从根节点开始,
for(int i=30;i>=0;i--){//从高位开始
int t=x>>i&1;
if(!son[p][t]) son[p][t]=++idx;//结点编号
p=son[p][t];
cnt[p]+=v;//统计数量
}
}
int ans(int x){
int p=0;
int res=0;
for(int i=30;i>=0;i--){
int t=x>>i&1;
//查看cnt是否为空
if(cnt[son[p][!t]]) p=son[p][!t],res=res*2+1;//若存在此子树,则异或后此位为1
else p=son[p][t],res=res*2;
}
return res;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
//求前缀异或和
s[i]=s[i-1]^a[i];
}
int res=0;
//插入s0
insert(s[0],1);
for(int i=1;i<=n;i++){
if(i>m) insert(s[i-m-1],-1);///注意这里,sn-s1表示2~n的元素异或,不是1~n的元素;sn-s0才是
res=max(res,ans(s[i]));
insert(s[i],1);
}
cout<<res;
//cout << "Hello world!" << endl;
return 0;
}
`