HDU - 6955 Xor sum【01字典树】

本文主要是介绍HDU - 6955 Xor sum【01字典树】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

要点：01-trie，前缀异或和， 每个结点存储当前最右位置，查询时去找满足大于k的最右位置，如果存在等于k的情况，则一定是for循环结束后才会出现的情况。

发现一个bug：int数值的右移不能大于31，否则不会得到准确值，如果非要连续除以2的次数达到31次以上(不包括31)，只能进行循环。

#include <cstdio>
#include <algorithm>using namespace std;
typedef long long LL;
const int N = 1e5 + 5;int t, n;
LL a[N], k;
int ch[32 * N][2];
int tot, maxR[32 * N];void init() {tot = 1;ch[0][0] = ch[0][1] = 0;
}void insert(LL x, int pos) {int u = 0;for (int i = 31; i >= 0; i--) {int v = (x >> i) & 1;if (!ch[u][v]) {ch[tot][0] = ch[tot][1] = 0;maxR[tot] = 0;ch[u][v] = tot++;}u = ch[u][v];maxR[u] = max(maxR[u], pos);}
}int query(LL x) {int res = 0, u = 0;for (int i = 31; i >= 0; i--) {int vx = (x >> i) & 1;int vk = (k >> i) & 1;if (!vx) {if (!vk) {// 如果下面的if成立, 则保证找到可行解if (ch[u][1]) res = max(res, maxR[ch[u][1]]);u = ch[u][0];} else u = ch[u][1];} else {if (!vk) {if (ch[u][0]) res = max(res, maxR[ch[u][0]]);u = ch[u][1];} else u = ch[u][0];}if (!u) break;}if (u) res = max(res, maxR[u]);return res;
}int main(void) {
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);scanf("%d", &t);while (t--) {init();scanf("%d%lld", &n, &k);int ansL = 0, ansR = n;for (int i = 1; i <= n; i++) {scanf("%lld", &a[i]);a[i] ^= a[i - 1];}for (int i = 1; i <= n; i++) {if ((a[i] ^ a[i - 1]) >= k) {ansL = ansR = i;break;}int nxtL = query(a[i]);if (nxtL > 0 && i - nxtL < ansR - ansL + 1) {ansL = nxtL + 1;ansR = i;}insert(a[i], i);}if (ansL) printf("%d %d\n", ansL, ansR);else printf("-1\n");}return 0;
}

这篇关于HDU - 6955 Xor sum【01字典树】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---