AcWing 3485. 最大异或和
原题链接
中等
作者:
就是氧气
,
2021-05-10 21:16:38
,
所有人可见
,
阅读 410
算法:trie+前缀和+滑动窗口 具体细节看注释
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 100010*31;
int son[N][2];
int cnt[N];
int idx;
int n,m;
int s[N];
void insert(int x,int v){
int p=0;
for(int i=30;i>=0;i--){
int u=(x>>i)&1;
if(!son[p][u]) son[p][u]=++idx;
p=son[p][u];
cnt[p]+=v;
}
}
int query(int x){
int res=0,p=0;
for(int i=30;i>=0;i--){
int u=(x>>i)&1;
if(cnt[son[p][!u]]){
p=son[p][!u];
res=res*2+1;
}
else{
p=son[p][u];
res=res*2;
}
}
return res;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
int x;
cin>>x;
s[i]=s[i-1]^x;
}
insert(s[0],1); //insert函数目的是插入时当前对应的01字典树所对应的二进制节点的数量++ 表示当前节点下面可选
int res=0;
for(int i=1;i<=n;i++){
if(i>m) insert(s[i-m-1],-1); //注意这里一定要减一 因为是先求后插入 比如长度为3 s的前缀和为1 2 3 4 5
//举个例子 当i=5 此时窗口内应该是 2 3 4 所以应当删除 5-3-1=1 然后才插入 我最初以为窗口是3 4 5所以大家不要犯这种错误
res=max(res,query(s[i]));
insert(s[i],1);
}
cout<<res<<endl;
return 0;
}