Educational Codeforces Round 23 E. Choosing The Commander Trie

69 阅读 0 评论 46 点赞

我是靠谱客的博主秀丽钢笔，最近开发中收集的这篇文章主要介绍Educational Codeforces Round 23 E. Choosing The Commander Trie，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

链接：

http://codeforces.com/contest/817/problem/E

题意：

3种操作：

1 插入一个数

2 删除一个数

3 给出一个数pi和l，询问有多少个数pj满足pi^pj<l

题解：

把每个数用bitset变成字符串，然后建字典树，询问的时候当碰到 l 的某一位为1的某一位为1的时候，就更新结果，然后继续搜索

代码：

31 int Trie[MAXN][2], val[MAXN];
32 int sz = 1;
33
34 void insert(string s, int value) {
35
int now = 1;
36
rep(i, 0, s.length()) {
37
int x = s[i] - '0';
38
if (!Trie[now][x]) Trie[now][x] = ++sz;
39
now = Trie[now][x];
40
val[now] += value;
41 
}
42 }
43
44 int query(string s, string t) {
45
int now = 1, ret = 0;
46
rep(i, 0, s.length()) {
47
int a = s[i] - '0';
48
int b = t[i] - '0';
49
if (b) ret += val[Trie[now][a]];
50
now = Trie[now][a^b];
51 
}
52
return ret;
53 }
54
55 int main() {
56
ios::sync_with_stdio(false), cin.tie(0);
57
int q;
58
cin >> q;
59
while(q--) {
60
int k, p, l;
61
cin >> k >> p;
62
if (k == 1) {
63
string s = bitset<30>(p).to_string();
64
insert(s, 1);
65 
}
66
else if (k == 2) {
67
string s = bitset<30>(p).to_string();
68
insert(s, -1);
69 
}
70
else {
71
cin >> l;
72
string s = bitset<30>(p).to_string();
73
string t = bitset<30>(l).to_string();
74
cout << query(s, t) << endl;
75 
}
76 
}
77
return 0;
78 }