[Codeforces 842D Vitya and Strange Lesson]异或字典树

分类：Data Structure Trie Tree

1. 题目链接

[Codeforces 842D Vitya and Strange Lesson]

2. 题意描述

有 N 个数，M次查询 a1,a2,…,an 。每次查询包含一个数 x ，将所有数与x异或，即 ai=ai⨁x 。然后求出 mex{a1,a2,…,an} 。注意，当前操作会改变原数组。
mex{a1,a2,…,an} 表示除 a1,a2,…,an 之外的最小非负数。

3. 解题思路

首先，第 i 次询问，可以看成是与前面所有询问的叠加。因为是异或操作，只需要去一个前缀异或值就好了。
对输入的a1,a2,…,an建立一棵二叉字典树，并判断每个节点下的子树是否满了。那么对于每个询问，从二进制高位向低位遍历整个树，假如当前位为 j(j∈{0,1}) ，那么 j==0 就判断左儿子子树是否满，否则判断右儿子子树是否满。如果满，就走另外一棵子树。边走边计算答案就好了。

4. 实现代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e5 + 5;
const int MAXB = 20;
int n, m, a[MAXN];
struct Trie {
struct TNode {
int ch[2];
bool full;
void init() { full = false; ch[0] = ch[1] = 0; }
} nd[MAXN * MAXB];
int tot, Root;
void init() {
memset(nd, 0, sizeof(nd));
Root = tot = 1;
}
int newNode() {
nd[tot + 1].init();
return ++ tot;
}
void ins(int x) {
int pos = Root;
for(int i = MAXB; i >= 0; --i) {
int j = x >> i & 1;
if(!nd[pos].ch[j]) nd[pos].ch[j] = newNode();
pos = nd[pos].ch[j];
}
}
int getAns(int y) {
int pos = Root, ret = 0;
for(int i = MAXB; i >= 0; --i) {
ret = ret << 1;
int j = y >> i & 1;
if(!pos) continue;
if(nd[nd[pos].ch[j]].full == false) pos = nd[pos].ch[j], ret |= 0;
else pos = nd[pos].ch[j ^ 1], ret |= 1;
}
return ret;
}
void dfs(int u) {
if(!nd[u].ch[0] && !nd[u].ch[1]) {
nd[u].full = true;
return;
}
nd[u].full = true;
for(int i = 0; i < 2; ++i) {
if(!nd[u].ch[i]) {
nd[u].full = false;
continue;
}
dfs(nd[u].ch[i]);
nd[u].full &= nd[nd[u].ch[i]].full;
}
}
} trie;
int main() {
#ifdef ___LOCAL_WONZY___
freopen ("input.txt", "r", stdin);
#endif // ___LOCAL_WONZY___
while(~scanf("%d %d", &n, &m)) {
trie.init();
for(int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
trie.ins(a[i]);
}
int x, y = 0, ans;
trie.dfs(trie.Root);
while(m --) {
scanf("%d", &x); y ^= x;
ans = trie.getAns(y);
printf("%dn", ans);
}
}
#ifdef ___LOCAL_WONZY___
cout << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC * 1000 << " ms." << endl;
#endif // ___LOCAL_WONZY___
return 0;
}

最后

以上就是虚拟猎豹为你收集整理的[Codeforces 842D Vitya and Strange Lesson]异或字典树[Codeforces 842D Vitya and Strange Lesson]异或字典树的全部内容，希望文章能够帮你解决[Codeforces 842D Vitya and Strange Lesson]异或字典树[Codeforces 842D Vitya and Strange Lesson]异或字典树所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。