题目描述
给定一个非负整数数列 $a$,初始长度为 $N$。
请在所有长度不超过 $M$ 的连续子数组中,找出子数组异或和的最大值。
子数组的异或和即为子数组中所有元素按位异或得到的结果。
注意:子数组可以为空。
输入格式
第一行包含两个整数 $N$,$M$。
第二行包含 $N$ 个整数,其中第 $i$ 个为 $a_i$。
输出格式
输出可以得到的子数组异或和的最大值。
数据范围
对于 $20\%$ 的数据,$1≤M≤N≤100$
对于 $50\%$ 的数据,$1≤M≤N≤1000$
对于 $100\%$ 的数据,$1≤M≤N≤105,0≤a_i≤2^{31}−1$
输入样例
3 2
1 2 4
输出样例
6
算法1
(0-1字典树 + 贪心)
-
思想:将每个数字的二进制位,从高位到低位存储到前缀树中,也就是说前缀树中仅有0和1这两个数字。
-
根据数学知识可以知道:$2^i$ > $2^{i-1}$+$2^{i-2}$+…+$2^1$+$2^0$
- 可以发现:异或只要两位不相同就是1,如果高位有一位是1,那么数就会大于这一位是0且低位全是1的情况。这就是从高位开始遍历的贪心思想。
- 如果某一位二进制位是0,但是前缀树的遍历过程中没有1的分支,则被迫走0的分支,反过来同理
- 树的高度由二进制位最多的数字决定,所以分支非0即1,不会有某一个数的二进制位先走到底的情况
- 如何求异或区间和:类似前缀和,异或运算是无进位加法,可以用异或前缀和快速求出某个区间的和;不同于常规的前缀和,对于区间
[l, r]
,异或区间和为s[r+1] ^ s[l]
,所以这题可以转换为找到前缀和数组中的两个数使得异或和最大 - 这题还需要维护一个长度不超过m的滑动窗口,所以需要把窗口外的元素从字典树中删除,在代码的实现中,我们并不需要真的把节点删除,只需要给每个节点设置一个
cnt
变量表示这个节点在构建字典树的时候保存了几次即可,如果遍历的时候cnt > 0
,则说明这个节点可以往下走 - 还需要注意的是,前缀和数组的下标从
1
开始,s[i]
表示数组中前i
个数的异或和;s[0]
为0
,所以s[0]
与所有数的异或值都为另一个数,如果求前i
个数(a[0], a[1],... a[i-1]
)的异或和,计算公式为s[i] ^ s[0]
,也就是说s[0]
不能从字典树中删除,因为其不属于窗口内的元素
Java 代码
import java.util.*;
class Node{
Node[] son = new Node[2];
// 节点的出现次数
int cnt = 0;
}
public class Main{
static Node root = new Node();
// u=1为插入, -1为删除
static void insert(int x, int u){
Node p = root;
for(int i = 30; i >= 0; i--){
int t = (x >> i) & 1;
if(p.son[t] == null) p.son[t] = new Node();
p = p.son[t];
p.cnt += u;
}
}
static int query(int x){
Node p = root;
int res = 0;
for(int i = 30; i >= 0; i--){
int t = (x >> i) & 1;
if(p.son[t ^ 1] != null && p.son[t ^ 1].cnt > 0){
res |= (1 << i);
p = p.son[t ^ 1];
}else{
p = p.son[t];
}
}
return res;
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt();
int[] a = new int[n];
for(int i = 0; i < n; i++) a[i] = sc.nextInt();
int[] s = new int[n+1];
for(int i = 1; i <= n; i++) s[i] = s[i-1] ^ a[i-1];
int res = 0;
for(int i = 1, j = 1; i <= n; i++){
if(i - j > m){
insert(s[j++], -1);
}
insert(s[i], 1);
res = Math.max(res, query(s[i]));
}
System.out.println(res);
}
}
- 时间复杂度:$O(n)$
- 空间复杂度:$O(n)$
明白了,谢谢
对于区间[l, r],异或区间和为什么是s[r+1] ^ s[l]而不是s[l - 1] ^ s[r] 呢?
前缀和数组的有效下标从
1
开始,所以s[i]
表示前i
个数的区间异或和;对于区间[l, r]
,区间异或和为前r+1
个数的异或和 异或上 前l
个数的异或和,即s[r+1] ^ s[l]
,具体你可以参考一下子数组异或查询