AcWing 3485. 最大异或和
原题链接
中等
作者:
ITNXD
,
2021-05-10 23:37:20
,
所有人可见
,
阅读 351
详细请查看注释
参考代码:
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100001 * 31, M = 100001;
int n, m, son[N][2], cnt[N], idx, s[M];
/*
思路:
1. 先求出前i个数的异或和 s[i] ---> 前缀和思路 s[i] = s[i - 1] ^ a[i];
2. 然后在大小为 m 的滑动窗口内进行 Trie
题目要求区间长度为m,因此只要当前遍历位置i大于m就将s[i - m - 1]删掉即可保证区间长度为m!此时的区间长度为 i-m ~ i-1
因此如果我们要计算[i - m, i] 区间长度为m的子区间的异或和,可以直接另s[i - m],s[i - m + 1]...s[i - 1]
与s[i]异或即可,最终取一个最大值即可。所有与s[i]异或得到的最大值即为本题的解!
举例:i = 6, m = 3
s[6] ^ s[3]:a[6] ^ a[5] ^ a[4]
s[6] ^ s[4]:a[6] ^ a[5]
s[6] ^ s[5]:a[6]
从中选取最大值的过程就是Tire的query函数的含义了!
与普通Tire不同的是,我们需要在s[i]的每一位都要进行标记cnt,用于表示删掉(-1)和增加(+1)!
*/
// v为1表示插入,-1表示删除
void insert(int x, int 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;
}
}
int query(int x){
// res 初始值为s[i],即x
int res = x, p = 0;
for(int i = 30; i >= 0; i --){
int u = x >> i & 1;
// 有当前位相反数则走过去
if(cnt[son[p][!u]]) u = !u;
// 当前数去异或该位
res ^= u << i, p = son[p][u];
}
return res;
}
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i ++){
int x; cin >> x;
// 异或前缀和
s[i] = s[i - 1] ^ x;
}
// 将前缀和插入Tire
insert(s[0], 1);
int res = 0;
for(int i = 1; i <= n; i ++){
// 维护一个滑动窗口长度为m,超过长度立马删掉(对应到Tire就是将该序列位置全部-1)
if(i > m) insert(s[i - m - 1], -1);
res = max(res, query(s[i]));
insert(s[i], 1);
}
cout << res << endl;
return 0;
}