• 微信公众号：美女很有趣。 工作之余，放松一下，关注即送10G+美女照片！

2021“MINIEYE杯”中国大学生算法设计超级联赛（1）1006 / HDU6955. Xor sum（01Trie/好题）

11小时前 2次浏览

Problem Description

Given a sequence of integers of length n, find the shortest consecutive subsequence witch XOR sum not less than k.

If there are multiple consecutive subsequences of the same length, print the consecutive subsequence with the smallest left end point.

If there are no consecutive subsequence witch XOR sum not less than k, just print “-1”.

Input

The first line contains a single integer t (t<=100) representing the number of test cases in the input. Then t test cases follow.

The first line of each test case contains two integers n (1<=n<=100000) and k (0<=k<2^30), representing the length of sequence.

The second line of each test contains n integers ai (0<=ai<2^30), representing the integers in sequence.

The number of test witch n>1000 does not exceed 5.

Output

For each test case, print two integers in one line, representing the left end point and right end point of the consecutive subsequence.

If there are no consecutive subsequence witch XOR sum not less than k, print “-1” in one line.

Sample Input

``````2
3 2
1 2 2
9 7
3 1 3 2 4 0 3 5 1
``````

Sample Output

``````2 2
5 7
``````

1. 怎么知道覆盖这个节点的最靠右的异或前缀和的下标呢？答：在insert的时候维护一个数组mx即可。因为是从左往右遍历，因此插入时对于01链上的节点直接更新就OK。
2. 怎么知道最终搜到的区间异或和是否一定大于等于k或者小于k呢？答：在不断递归搜索的过程中传递一个参数sum表示当前搜索路径上两异或前缀和异或得到的区间异或和的前面一部分的大小，然后将其后面若干位全变为0或变为1来比较判断。描述比较费劲，不妨看一个例子：设右端点对应的异或前缀和为01101，沿trie树从高位往低位搜索到的部分为00，此时高两位异或得到01，还剩下三位没有搜索到，若k取小于等于01000即8的数，那么最终无论如何都能满足要求，反之若k取大于10000即16的数那么最终必然不可能满足要求。

``````#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1e5 + 10;
int tol; //节点个数
int val[32 * MAXN]; //点的值
int ch[32 * MAXN][2]; //边的值
int mx[32 * MAXN];
int n, k, a[100005], sum[100005];
void init() {
tol = 1;
ch[0][0] = ch[0][1] = 0;
for(int i = 0; i <= 32 * n; i++) mx[i] = 0;
}
void insert(int x, int pos)
{ //往 01字典树中插入 x
int u=0;
for(int i = 31; i >= 0; i--) {
int v=(x>>i)&1;
mx[u] = max(mx[u], pos);//维护mx数组，顺序更新实际上不需要max函数
if(!ch[u][v])
{ //如果节点未被访问过
ch[tol][0]=ch[tol][1]=0; //将当前节点的边值初始化
val[tol]=0; //节点值为0，表示到此不是一个数
ch[u][v]=tol++; //边指向的节点编号
}
u=ch[u][v]; //下一节点
}
val[u]=x; //节点值为 x，即到此是一个数
mx[u] = max(mx[u], pos);
}
int f(int p, int sum, int i, int k, int x) {
int ans = -1;
if(sum >= k) {
//cout << "ok" << endl;
return mx[p];//没必要继续往下走了
}
if(sum + ((1ll << (i + 1)) - 1) < k) {//这么走下去不论怎么选都不可行
return -1;
}
if(ch[p][0]) {
ans = max(ans, f(ch[p][0], sum + (x & (1 << i)), i - 1, k, x));
}
if(ch[p][1]) {
ans = max(ans, f(ch[p][1], sum + ((x & (1 << i)) ^ (1 << i)), i - 1, k, x));
}
return ans;
}
int query(int x, int k) {
return f(0, 0, 31, k, x);
}
signed main() {
ios::sync_with_stdio(false);
int T;
cin >> T;
while (T --) {
init();
cin >> n >> k;
insert(0, 0);
int ansl = 0, ansr = 0, minlen = 0x3f3f3f3f;
for(int i = 1; i <= n; i++) {
cin >> a[i];
sum[i] = sum[i - 1] ^ a[i];
}
for(int i = 1; i <= n; i++) {
if(a[i] >= k) {
ansl = ansr = i;
minlen = 1;
break;
}
int lpos = query(sum[i], k);
if(lpos != -1 && (sum[i] ^ sum[lpos]) >= k) {
int len = i - lpos;
if(len < minlen) {
minlen = len;
ansl = lpos + 1, ansr = i;
} else if(len == minlen) {
if(ansl > lpos + 1) {
ansl = lpos + 1;
ansr = i;
}
}
}
insert(sum[i], i);
}
if(minlen != 0x3f3f3f3f) {
cout << ansl << " " << ansr << endl;
} else {
cout << -1 << endl;
}
}
return 0;
}
``````