题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=100010*31;
//int son[N][2],cnt[N],a[100010],n,idx,s[100010];
// 整体思路 字典树求最大异或对的做法
// 将子数组l~r的异或和a[l]^...^a[r] 转化为前缀异或和数组(s[r]^s[l-1])
// 遍历s数组每轮内查询s[i]在合法范围的最大异或和 最后得到结果
// ps:合法范围就是s[max(i-m,0)]~s[i]
int son[N][2],a[100010],s[100010],n,idx,cnt[N];
//son数组 第一维是节点编号第二维是0或1儿子
//存的是p节点的0或1儿子的节点编号
//cnt数组当前存编号为p的节点出现的次数
void insert (int x,int v){
//插入兼删除函数 通过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;
//cnt数组存当前编号为p的节点出现的次数
}
}
int query (int x){
//查询x最大异或和
int p=0,res=0;
for (int i=30;i>=0;i--){
int u=x>>i&1;
if (cnt[son[p][!u]]) {
//由于我们的x可求异或和的范围不是所有s
//所以不是if (son[p][!u])
//而是cnt[son[p][!u]]当前可异或节点的出现次数
res=res*2+1;
p=son[p][!u];
}
else {
res*=2;
p=son[p][u];
}
}
return res;
}
int main()
{
int m;
cin>>n>>m;
for (int i=1;i<=n;i++){
cin>>a[i];
s[i]=s[i-1]^a[i];
}
insert(s[0],1);
//子数组可以为空 插入0
int res=0;
for (int i=1;i<=n;i++){
if (i>m) insert(s[i-m-1],-1);
//s[i]可求异或合法范围是s[max(i-m,0)]~s[i]
//要及时把超出范围的数去掉
res=max(res,query(s[i]));
insert(s[i],1);
}
cout <<res;
}