链接
传送门
题意
给出一个可重集，最初其中有一个0，有插入删除询问三种操作。对于询问操作，输出给出的数字和可重集中的数字异或的最大值。
思路
对可重集中的数字建trie树，查询时每次都优先走于所给数字当前位相反的边，达到底层的结点即为与给出数字异或和最大的结点。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
| #include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 6400005;
char s[maxn];
struct Trie {
int next[maxn][2];
int fa[maxn];
int num[maxn];
int root, L;
int newnode() {
next[L][0] = next[L][1] = fa[L] = -1;
num[L] = 0;
return L++;
}
void Init() {
L = 0;
root = newnode();
}
void Insert(int x) {
int now = root;
for (int i = 30; i >= 0; --i) {
int k = (x & (1 << i)) ? 1 : 0;
if (next[now][k] == -1) {
next[now][k] = newnode();
fa[next[now][k]] = now;
}
now = next[now][k];
++num[now];
}
}
void Delete(int x) {
int now = root;
for (int i = 30; i >= 0; --i) {
int k = (x & (1 << i)) ? 1 : 0;
if (next[now][k] == -1) {
next[now][k] = newnode();
}
now = next[now][k];
--num[now];
}
while (fa[now] != -1) {
if (next[now][0] != -1 && num[next[now][0]] == 0) {
next[now][0] = -1;
}
if (next[now][1] != -1 && num[next[now][1]] == 0) {
next[now][1] = -1;
}
now = fa[now];
}
}
int getNum(int x) {
int now = root, y = 0;
for (int i = 30; i >= 0; --i) {
int k = (x & (1 << i)) ? 0 : 1;
y <<= 1;
if (next[now][k] == -1) {
k ^= 1;
}
y |= k;
now = next[now][k];
}
return x ^ y;
}
} trie;
int main() {
int n, x;
scanf("%d", &n);
trie.Init();
trie.Insert(0);
while (n--) {
scanf("%s%d", s, &x);
if (s[0] == '+') {
trie.Insert(x);
} else if (s[0] == '-') {
trie.Delete(x);
} else {
printf("%d\n", trie.getNum(x));
}
}
return 0;
}
|