题目描述
农夫约翰在给他的奶牛们喂食时遇到了一个问题。
他共有 N 头奶牛,编号 1∼N。
每次喂食前,这 N 头奶牛会按照 1∼N 的顺序站成一排。
此外,每头奶牛都被分配了一个可能不唯一的整数。
那么所有被分配的整数就形成了一个长度为 N 的整数序列。
请你在该整数序列中找出一个连续的非空子序列,使得子序列中元素的异或和能够最大。
如果存在多个这样的序列,那么选择序列末端整数对应的奶牛编号更小的那个序列。
如果仍然存在多个可选的序列,那么选择长度最短的那个序列。
输入格式
第一行包含整数 N。
第 2∼N+1 行,每行包含一个整数,其中第 i 行的整数表示编号为 i−1 的牛被分配的整数值。
输出格式
输出三个整数,分别表示最大的异或和,所选序列首端整数对应的奶牛编号,所选序列末端整数对应的奶牛编号。
数据范围
1≤N≤105,
分配给奶牛的整数的范围是 [0,221−1]。
样例
输入样例:
5
1
0
5
4
2
输出样例:
6 4 5
算法1
(trie树) $O()$
时间复杂度
参考文献
python3 代码
n = int(input())
nums = [int(input()) for _ in range(n)]
class Trie:
def __init__(self):
self.child = [None for _ in range(2)]
self.idx = -1
def insert(self, x: int, idx: int) -> None:
root = self
for i in range(20, -1, -1):
ID = (x >> i) & 1
if root.child[ID] == None:
root.child[ID] = Trie()
root = root.child[ID]
root.idx = idx
def query(self, x: int) -> int:
root = self
for i in range(20, -1, -1):
ID = (x >> i) & 1
if root.child[(1-ID)] == None:
root = root.child[ID]
else:
root = root.child[(1-ID)]
return root.idx
presum = [0 for _ in range(n + 1)]
for i in range(n):
presum[i + 1] = presum[i] ^ nums[i]
res = -1
s, e = -1, -1
T = Trie()
for i in range(n):
T.insert(presum[i], i)
k = T.query(presum[i+1])
cur = presum[k] ^ presum[i+1]
if cur > res:
res = cur
s = k + 1
e = i + 1
# elif cur == res:
# if (i+1 - (k+1)) < (e - s):
# s = k + 1
# e = i + 1
print("{} {} {}".format(res, s, e))
C++ 代码
#include<bits/stdc++.h>
using namespace std;
class Trie
{
public:
Trie * child[2];
int idx;
Trie()
{
memset(child, 0, sizeof(child));
this->idx = -1;
}
void insert(int x, int idx)
{
Trie * root = this;
for (int i = 20; i > -1; i --)
{
int ID = (x >> i) & 1;
if (root->child[ID] == NULL)
root->child[ID] = new Trie();
root = root->child[ID];
}
root->idx = idx;
}
int query(int x)
{
Trie * root = this;
for (int i = 20; i > -1; i --)
{
int ID = (x >> i) & 1;
if (root->child[1-ID] != NULL)
root = root->child[(1-ID)];
else
root = root->child[ID];
}
return root->idx;
}
};
int main()
{
int n;
cin >> n;
int nums[n];
memset(nums, 0, sizeof(nums));
for (int i = 0; i < n; i ++)
cin >> nums[i];
vector<int> presum(n + 1, 0);
for (int i = 0; i < n; i ++)
presum[i + 1] = presum[i] ^ nums[i];
int res = -1;
int s, e;
Trie * T = new Trie();
for (int i = 0; i < n; i ++)
{
T->insert(presum[i], i);
int k = T->query(presum[i + 1]);
int cur = presum[k] ^ presum[i + 1];
if (cur > res)
{
res = cur;
s = k + 1;
e = i + 1;
}
}
cout << res << ' ' << s << ' ' << e << endl;
return 0;
}