AcWing 3485. 最大异或和
原题链接
中等
作者:
bigstone
,
2021-05-11 12:26:17
,
所有人可见
,
阅读 351
基于T143 1414
最大异或和 https://www.acwing.com/problem/content/3488/
找出数组中,长度不超过m且异或和最大的连续子数组的异或值
知识点:Trie树
由区间联想到前缀异或 和s
即将一段异或,变成两个数异或
-> 在si前找一个数sj,使得si^sj最大
每个数从0~30,一共31位
找sj时,对应二进制,从高位开始,选择与si同位置不同的数 - Trie
限制:i - j <= m,即j在[i - m, i - 1]中选
在每个节点记一个cnt,表示以这个点为根的子树中有多少个数
在该点子树中加一个数 cnt ++ / 减一个数 cnt --
i从1到n遍历,若i > m,则将s[i - m - 1]删去
取i - m - 1的原因:
1 2 3 4 5 6 7 8 (m = 4)
i
可以取的区间:4~7,即需要保留s[4 - 1],即s[3],即删去s[1], s[2]
即i - m - 1
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010 * 31, M = 100010;
int n, m;
int son[N][2], s[M], cnt[N], idx;
void insert(int x, int v) //v表示添加1/删除-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)
{
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;
}
int res = 0;
insert(s[0], 1);
for ( int i = 1; i <= n; i ++ ) //类似滑动窗口,前头每次添加一个数,末尾超出区间就删除
{
if ( i > m ) insert(s[i - m - 1], -1);
res = max(res, query(s[i]));
insert(s[i], 1);
}
cout << res;
return 0;
}