AcWing 3485. 最大异或和
原题链接
中等
作者:
EXCUTER
,
2021-06-08 18:11:38
,
所有人可见
,
阅读 347
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 100010 * 31, M = 100010;//N表示所有可能的trie树结点情况(就是每个点有俩儿子01),所以一共有100000 * 31个点.
int n, m;
int son[N][2], s[M], idx;//idx仅仅代表每个点的身份(idx的大小之间没有联系)
int cnt[N];//记录该点的子数棵树
void insert(int x, int v)//用trie树记录前缀异或和,v = 1时表示该点增加一棵子数(有cnt[i]个点有着在该点之前的相同二进制), v = -1时减少一个子树
{ //若经过该点,可知在该点之前S[j]中的高位与之前在该点记录的S[i]有着相同的二进制高位(trie数的知识)
int p = 0;
for(int i = 30; i >= 0; i --)//ai数据范围:二进制表示一共31位 >>30 即第30位 >>0 即第零位(二进制从第零位开始)。
{
int u = x >> i & 1;
if(!son[p][u]) son[p][u] = ++ idx;
p = son[p][u];
cnt[p] += v;
}
}
int quary(int x)//找区间异或和
{
int p = 0, res = 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;//尽量找与S[i]同一位上不同的数,从而得到1(从而不断缩小区间)
else p = son[p][u], res = res * 2; //保证在目前的总区间里i到j的区间里异或和最大。
} //补充:一个数自己与自己异或为0,0又是一个单位元(0^x = x) (方便理解区间异或和)
return res;
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++)
{
int x;
cin >> x;
s[i] = s[i - 1] ^ x;//前缀异或和
}
int res = 0;
insert(s[0], 1);//存S[0]是为了满足S[1]能够参与求最大异或和(原因由上述补充可知)
for(int i = 1; i <= n; i ++)//滑动区间
{
if(i > m) insert(s[i - m - 1], -1);
res = max(res, quary(s[i]));//在滑动区间里求最大异或和
insert(s[i], 1);//存S[i]
}
cout << res << endl;
return 0;
}