Educational Codeforces Round 23 E. Choosing The Commander （字典树）

题目大意：
总共有q次询问，对于每次询问有三种不同的操作；
p = 1，增加一个数字
p = 2，去掉一个数字
p = 3，对于当前存在的数字，有x，s，问有多少 num[i]^x < s？

题解：
用字典树存所有的数字的二进制形式，sum存每种类型的个数，对于每次询问的复杂度都是log（n）。具体看代码。

代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <stack>
#include <bitset>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <algorithm>
using namespace std;
#define clr(a,b) memset(a,b,sizeof(a))
#define pb(a) push_back(a)
#define fir first
#define se second
#define LL long long
typedef pair<int,int> pii;
typedef pair<LL,int> pli;
typedef pair<LL,LL> pll;
const int maxn = 1e5+5;
const LL inf = 0x3f3f3f3f3f3f3f3f;
LL mod = 1e9+7;
double eps = 0.00000001;
double PI = acos(-1);
//用数组来模拟建树
struct BitTrie {
int next[maxn*31][2],fa[maxn*31],sum[maxn*31],cnt;
//next存下一个节点的下标，fa存父节点的下标，sum存当前节点的存在的所有数字个数，cnt即节点数
void init() {
//初始化
cnt = 0;
clr(next,-1);
clr(sum,0);
clr(fa,-1);
}
void add(int x,int cn) {
int p = 0;
for(int i = 31;i >= 0;i--) {
int ff = (x>>i)&1;
if(next[p][ff] == -1) { //如果没有就新建节点
next[p][ff] = ++cnt;
}
fa[next[p][ff]] = p;
//保存父节点
p = next[p][ff];
//找到下一个节点
}
sum[p] += cn;
//for(int i = 0;i <= 10;i++) printf("%d ",fa[i]);
//cout<<endl;
while(p != -1) {
//回溯把所有子节点的个数加到父节点
int nfa = fa[p];
sum[nfa] = 0;
if(next[nfa][0] != -1) sum[nfa] += sum[next[nfa][0]];
if(next[nfa][1] != -1) sum[nfa] += sum[next[nfa][1]];
p = fa[p];
}
}
int query(int pp,int l) {
int ans = 0,p = 0;
for(int i = 31;i >= 0;i--) {
int idp = (pp>>i)&1;
int idl = (l>>i)&1;
if(idl) {
//如果位置i上l的二进制值是1，那么直接把二进制值是0的加到答案中，因为二进制值是0那么所有子节点都小于l，并且往下搜二进制值是1的子节点
if(next[p][idp] != -1) ans += sum[next[p][idp]];
if(next[p][!idp] != -1) p = next[p][!idp];
else break;
}
else {
//如果位置i上l的二进制值是0，那么往下搜二进制值是0的子节点
if(next[p][idp] != -1) p = next[p][idp];
else break;
}
}
return ans;
}
};
BitTrie tt;
int main() {
int q;
cin>>q;
tt.init();
while(q--) {
int k,p,l;
scanf("%d",&k);
if(k == 1) {
scanf("%d",&p);
tt.add(p,1);
}
if(k == 2) {
scanf("%d",&p);
tt.add(p,-1);
}
if(k == 3) {
scanf("%d%d",&p,&l);
printf("%dn",tt.query(p,l));
}
}
}

入门了字典树吧，感觉字典树也不是很难。
come on！

最后

以上就是孝顺绿茶为你收集整理的Educational Codeforces Round 23 E. Choosing The Commander （字典树）的全部内容，希望文章能够帮你解决Educational Codeforces Round 23 E. Choosing The Commander （字典树）所遇到的程序开发问题。

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