前置知识-异或和的性质:
1. 异或和本质就是模二加
2. 对整数的运算性质在模二的域下都成立
3. 因此,前缀和也成立
4. 且a^b = a+b = a-b,加和减没有区别
算法:
考虑前缀和s[],记录前i个元素的前缀和
原问题转化为在滑动窗口中求最大异或对问题
//
// Created by heyuehui on 5/11/2021.
//
/**
* 给定一个非负整数数列 a,初始长度为 N。
请在所有长度不超过 M 的连续子数组中,找出子数组异或和的最大值。
子数组的异或和即为子数组中所有元素按位异或得到的结果。
注意:子数组可以为空。
trie真的难调试啊,最后还是对照别人代码查错的,所以模板一定要背熟啊
*/
#include <iostream>
using namespace std;
const int N = 4010000;
int tr[N][2], cnt[N], idx;
/**
* 在支持删除操作的trie中,用cnt[]记录以当前为前缀的字符串数量(包括前缀本身),如果cnt[i] = 0, 则说明没有以当前为前缀的字符串
*/
int s[N];
void insert(int x, int v) {
/**
* v = 1 表示插入
* v = 0 表示删除
*/
int p = 0;
for (int i = 31; i >= 0; i--) {
int k = x >> i & 1;
if (!tr[p][k]) tr[p][k]= ++idx;
p = tr[p][k];
cnt[p] += v; // 注意cnt在这里 += v
}
}
int query(int x) {
int ans = 0;
int p = 0;
for (int i = 31; i >= 0; i--) {
int k = x >> i & 1;
if (cnt[tr[p][!k]]) p = tr[p][!k], ans |= 1 << i;
else p = tr[p][k];
}
return ans;
}
int main() {
int ans = 0;
int n, m; cin >> n >> m;
// 处理前缀和
for (int i = 1; i <= n; i++) {
int x; cin >> x;
s[i] = s[i-1]^x;
}
// 滑动窗口 + 最大异或对
insert(s[0], 1);
for (int i = 1; i <= n; i++) {
if (i > m) insert(s[i-m-1], -1);
ans = max(ans, query(s[i]));
insert(s[i], 1);
}
cout << ans << endl;
return 0;
}
兄弟有时间填个邀请码hhhhhhhhh(可以得AC币,邀请码在学生认证那填) 我的邀请码是:GUDFH