最大异或和
题目描述
给定一个非负整数数列 $a$,初始长度为 $N$。
请在所有长度不超过 $M$ 的连续子数组中,找出子数组异或和的最大值。
子数组的异或和即为子数组中所有元素按位异或得到的结果。
注意:子数组可以为空。
输入格式
第一行包含两个整数$N$,$M$。
第二行包含 $N $个整数,其中第 $i$ 个为 $a_i$。
输出格式
输出可以得到的子数组异或和的最大值。
数据范围
对于 $20\%$ 的数据,$1≤M≤N≤100$
对于 $50\%$ 的数据,$1≤M≤N≤1000$
对于 $100\%$的数据,$1≤M≤N≤10^5$,$0≤a_i≤2^{31}−1$
输入样例:
3 2
1 2 4
输出样例:
6
思路
前缀和+trie+滑动窗口+贪心
-
对于从区间$[n,m]$的异或和可以表示为$s[m] \bigoplus s[n-1]$,可以先使用前缀和的思想,求出前缀异或和的结果
-
贪心:对于每一个树要异或和最大,就需要高位不同,从高到低枚举每个数的每一位,在前缀和中查询是否存在不同的位,计算最大值
- 滑动窗口,要求区间的长度不超过$m$,如果长度超过$m$,就删除前面添加到trie中的元素
实现代码
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 30 * 100010;
// 每个数最多有30个点,
int cnt[N], idx;
int son[N][2], s[100010];
int n, m;
// 1表示插入,0表示删除
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)
{
int p = 0;
int res = 0;
for(int i = 30;i >= 0;i --)
{
int u = x >> i & 1;
if(cnt[son[p][!u]]) res = res * 2 + 1, p = son[p][!u];
else res = res * 2, p = son[p][u];
}
return res;
}
int main()
{
scanf("%d%d",&n,&m);
// 求异或和
for(int i = 1;i <= n;i ++)
{
int x;
scanf("%d",&x);
s[i] = s[i -1] ^ x;
}
int res = 0;
insert(0, 1);
for(int i = 1;i <= n;i ++)
{
// 这里是删除i-m-1是因为 需要用的其实是比区间长度的位置多1
if(i > m) insert(s[i - m - 1], -1);
res = max(res,query(s[i]));
insert(s[i],1);
}
printf("%d",res);
return 0;
}