大致的思路和注释都在代码里面~
#include <iostream>
using namespace std;
/**
* 大致的思路
* 在一个非负的整数序列中我们要找到一个连续的子数组的异或和最大
* 我们很容易就能想到前缀和数组,但是这个前缀和数组s[i]不是一般的前缀和数组
* 而应该是前缀异或和数组
* 所以我们如果想要求区间[i,j]的异或和的话,结果就应该为s[j] ^ s[i-1]
* 因为j > i所以i之前的1到i-1的都抵消了
* 所以这道题就变成,在前缀异或和数组中找到两个数的异或和最大
* 这题就转变成了AcWings 143. 最大异或对的这道题
* 这道题的思路就变成了在一群数中找到两个异或最大的数
* 显然,两个数的异或值要最大的话,说明这两个数的二进制对应的位要尽可能的不同
* 而且应该优先从高位开始越不同,两个数的异或值越大
* 但是这道题有一个限制,就是连续子数组的异或和的长度不能超过M
* 所以我们要用类似滑动窗口的思想,如果对应的下标i大于m的话,就要把前面插入的字符串给删掉
* 所以为了实现这个删除的操作,我们没有必要实现真正的删除,而是应该定义一个cnt[p]数组
* 如果要insert就对应每个插入结点(idx)都+1,如果要删除就应该在每个插入结点(idx)都-1
*
*/
const int N = 1e5+10,M = 31 * N;
int son[M][2],idx;//idx对应每个结点从0开始的标签
int cnt[M];//cnt记录每个数对应二进制的最后一位的标记,因为cnt对应每一个结点是否存在,那么数组大小就要开到M
int s[N];//前缀异或和数组
int n,m;//n代表多少个数,m代表连续子数组的长度
void insert(int x,int v)//插入字典树,v = 1表示添加,v = -1表示删除
{
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)//找到x在对应字典树异或的最大值,思路就是如果有不同结点的话就+1然后往下走
{
int p = 0;
int res = 0;
for(int i = 30;i >= 0;i--)
{
int u = x >> i & 1;//从高到低取出x的每一个二进制位
if(cnt[son[p][!u]])//如果对应结点的二进制位的相反位的结点存在的话
{
res = res * 2 + 1;
p = son[p][!u];
}
else//如果不存在的话只能顺着往下走
{
res = res * 2 + 0;
p = son[p][u];
}
}
return res;
}
int main()
{
scanf("%d %d",&n,&m);
int x;
for(int i = 1;i <= n;i++)
{
scanf("%d",&x);
s[i] = s[i-1] ^ x;
}
int res = 0;//记录最大值
for(int i = 1;i <= n;i++)
{
if(i > m+1)
insert(s[i-m-1],-1);//因为是从下标1开始的,所以超出M的下标就对应的i+m+1
//那么如果i的下标大于m+1就要删除前面的数了
int t = query(s[i]);
res = max(res ,t);
insert(s[i],1);//把对应的数插入进去
}
printf("%d",res);
return 0;
}