题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
import java.util.Scanner;
class Main{
// 有的时候其实正确但你运行仍然报错 所以有信心的时候直接交就好
// 本质就是到了某个点 i 这个时候从1 - i的xor sum可以知道 我们之前知道利用一组数据找xor 最大 给个数组找两个数间最大的xor和
//那么可以把这个问题转化 入股我们找到一个 prefixsum[j] 和prefixsum[i] xor 后得到最大 j < i
//prefixsum[j] = 1 … j prefixsum[i] = 1 ....j …i xor 后得到j + 1 to i的xor sum
//下面介绍下为什么一组可以知道两个数间最大xor
// 因为xor有特性 一定要找某个二进制位置不同的数 xor后才能得到最大值 所以我们可以根绝prefixsum[i] 32位数找某个前面
// 最匹配的prfixsum[j] xor后得到最大
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] nums = new int[n + 1];
for (int i = 1; i <= n; i) nums[i] = sc.nextInt();
Node root = new Node();
add(root, nums[0], 0);
int sum = nums[0];
int[] res = new int[]{0, 1, n};
for (int i = 1; i <= n; i) {
sum ^= nums[i];
int[] temp = find(root, sum);
if (temp[0] > res[0]) {
// 题目要求右端点靠前 我看成总区间更短的一个 加了|| temp[0] == res[0] && i - temp[1] - 1 < res[2] - res[1]
// 右端点靠前意思就是第一个
res = new int[]{temp[0], temp[1] + 1, i};
}
add(root, sum, i);
}
System.out.printf(“%d %d %d”, res[0], res[1], res[2]);
}
public static void add(Node root, int num, int index) {
for (int i = 31; i >= 0; i--) {
int x = (1 << i & num) != 0? 1 : 0;
if (root.nodes[x] == null) root.nodes[x] = new Node();
root = root.nodes[x];
}
root.index = index;
}
public static int[] find(Node root, int num) {
int res = 0;
for (int i = 31; i >= 0; i--) {
int x = (1 << i & num) != 0 ? 1 : 0;
int temp = x == 1? 0 : 1;
if (root.nodes[temp] != null) {
res ^= 1 << i;
root = root.nodes[temp];
} else {
root = root.nodes[x];
}
}
return new int[]{res, root.index}; // maxvalue, the end of last prefixsum
}
}
class Node{
Node[] nodes = new Node[2];
int index;
Node(){}
}