题目描述
给定一个非负整数数列 a,初始长度为 N。
请在所有长度不超过 M 的连续子数组中,找出子数组异或和的最大值。
子数组的异或和即为子数组中所有元素按位异或得到的结果。
注意:子数组可以为空。
输入格式
第一行包含两个整数 N,M。
第二行包含 N 个整数,其中第 i 个为 ai。
输出格式
输出可以得到的子数组异或和的最大值。
数据范围
对于 20% 的数据,1≤M≤N≤100
对于 50% 的数据,1≤M≤N≤1000
对于 100% 的数据,1≤M≤N≤10^5,0≤ai≤2^31−1
输入样例:
3 2
1 2 4
输出样例:
6
没有想出来O(n^3)的做法0 0
算法1
(暴力枚举) $O(n^2)$
# include <iostream>
using namespace std;
const int maxn = 1e5+5;
int a[maxn];
int n,m;
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++){
cin >> a[i];
}
int res = 0;
for(int i = 1; i <= n; i ++){
int temp = a[i];
for(int j = i + 1; j <= i + m - 1 && j <= n; j ++){
temp ^= a[j];
res = max(res,temp);
}
}
cout << res << endl;
}
算法2
(二进制字典树枚举) $O(nlogn)$
C++ 代码
# include <iostream>
using namespace std;
const int maxn = 1e5+5;
int tire[maxn * 31][2],idx,cnt[maxn * 31];//需要注意的是我们存储的是2进制下的数,也就是数据范围最大为
//31个位置
int sum[maxn];//该数组为前缀异或和数组
int n,m;
void update(int x, int k)
{
int p = 0;//p为父节点
for(int i = 30; i >= 0; i --){
int son = x >> i & 1;//取出二进制第i位的数
if(!tire[p][son]) tire[p][son] = ++ idx;//加入子节点,son为0为左子树,son为1为右子树
p = tire[p][son];
cnt[p] += k;//到这个位置的数出现次数 +k
}
}
int query(int x)//询问区间
{
int p = 0;
int res = 0;
for(int i = 30; i >= 0; i --){
int son = x >> i & 1;
if(cnt[tire[p][!son]]){//如果存在一个与当前访问的子树值相反的点,则此位置为1
p = tire[p][!son];
res = res * 2 + 1;
}
/*
需要注意的是异或的特性,首先,我们的字典树中存储的某个前缀的区间的异或值,比如从
1到n,就是a1^a2^...^an,而当我们访问n+m时,我们就会以sum[n + m]为一个标准树,这颗
标准树存的值时 a1^a2^...a(n+m),所以当我们用这颗标准树去和sum[n] ~ sum[n + m - 1]
之间的区间去异或时,(要注意的是,以这棵标准树进行异或时, 当异或到终点时, 终点必定
是一个异或区间和),不论怎样, 最终异或出的都是一个连续的区间, 比如假如sum[n + m]
和sum[n + 5]异或的是最大的话,那结果就是 a1^a2^...^a[n + m] ^ a1^a2^...^a[n + 5]
由于异或的性质, 最终的结果就是 a[n + 6]^a[n + 7]^...^a[n + m], 即从n + 6 到 n + m
的连续异或区间和, 由此, 每次询问都必定是一段区间异或和
*/
else{//否则说明当前访问的子树与它的子树只存在同样的值,则此位置为0
p = tire[p][son];
res = res * 2;
}
}
return res;
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++){
int x;
cin >> x;
sum[i] = sum[i - 1] ^ x;
}
int res = 0;
update(sum[0], 1);//更新空树,s[0]可以取到
for(int i = 1; i <= n; i ++){
if(i > m) update(sum[i - m - 1], -1);//删除sum[i - m]以前的数
res = max(res, query(sum[i]));//更新最大值
update(sum[i], 1);//不要忘记把这个异或区间插入
}
cout << res << endl;
}