题目描述
3485. 最大异或和
给定一个非负整数数列 a,初始长度为 N。
请在所有长度不超过 M 的连续子数组中,找出子数组异或和的最大值。
子数组的异或和即为子数组中所有元素按位异或得到的结果。
注意:子数组可以为空。
输入格式
第一行包含两个整数 N,M。
第二行包含 N 个整数,其中第 i 个为 ai。
输出格式
输出可以得到的子数组异或和的最大值。
数据范围
对于 20% 的数据,1≤M≤N≤100
对于 50% 的数据,1≤M≤N≤1000
对于 100% 的数据,1≤M≤N≤105,0≤ai≤231−1
样例
输入样例:
3 2
1 2 4
输出样例:
6
难度:中等
时/空限制:1s / 256MB
总通过数:169
总尝试数:659
来源:美团2021,笔试题
算法标签
tire树 + 前缀和 + 贪心
C++ 代码
#include <iostream>
using namespace std;
const int N = 31 * 1e5 + 10;
const int M = 1e5 + 10;
int son[N][2], cnt[N], idx;
int s[M];
int n, m;
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]]){
//相反数不存在,没办法只能异或相同的了
p = son[p][u];
res = res * 2;
}
else{
//有相反数,非常好,直接异或上去
p = son[p][!u];
res = res * 2 + 1;
}
}
//得到一个当前的解
return res;
}
int main(){
cin >> n >> m;
for (int i = 1; i <= n;i++){
int x;
cin >> x;
s[i] = s[i - 1] ^ x;
}
insert(s[0], 1);
int res = 0;
for (int i = 1; i <= n;i++){
//长度为m,窗口往后滑了一格,容量不够了,把最前面那个踢出去
if(i>m)
insert(s[i - 1 - m], -1);
//当前解看看是不是整体的最优解,是的就更新
res = max(res, query(s[i]));
//窗口往后滑,把后面的一个加进来。
insert(s[i], 1);
}
cout << res;
}