AcWing 3485. 最大异或和
原题链接
中等
作者:
梁俊的爹
,
2021-07-16 10:59:04
,
所有人可见
,
阅读 202
#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<queue>
#include<stack>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
const int N=1e5+10;
int s[N];
int f[N*31][2];
int idx;
int cnt[N*31];
void insert(int x,int c){
int p=0;
for(int i=31;i>=0;i--){
int u=x>>i&1;
if(!f[p][u]){
f[p][u]=++idx;
}
p=f[p][u];
cnt[p]+=c; //添加s[i]时c等与1,删除s[i]时c等于-1
}
}
int querry(int x){
int p=0;
int sum=0;
for(int i=31;i>=0;i--){
int u=x>>i&1;
if(f[p][!u]&&cnt[f[p][!u]]>0){
p=f[p][!u];
sum+=1<<i;
}
else
{
p=f[p][u];
}
}
return sum;
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
s[i]=s[i-1]^x;
}
int ans=0;
int sum=0;
insert(s[0],1);
for(int i=1;i<=n;i++){
if(i>m){
insert(s[i-m-1],-1);//因为是先计算值再插入s[i],所以这里是i-m-1:
}
ans=max(ans,querry(s[i]));
insert(s[i],1);
}
cout<<ans<<"\n";
}
// 用到了前缀和的思想 还有滑动窗口 s[i]^s[i-1]=a[i];