Educational Codeforces Round 23 E. Choosing The Commander（01Trie）

题意：三个操作：1增加一个数，2删除一个数，3求所有数^k<l的个数

思路：01Trie，求^k<l的个数时，如果l为1则加上0的，并往1走，如果l为0，就往0走。

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxnode = 1e5*32+5;
int ch[maxnode][2], val[maxnode], sz;
void init()
{
sz = 1;
memset(ch[0], 0, sizeof(ch[0]));
}
void Insert(int x)
{
int u = 0;
for(int i = 31; i >= 0; i--)
{
int idx = (x>>i)&1;
if(!ch[u][idx])
{
memset(ch[sz], 0, sizeof(ch[sz]));
val[sz] = 0;
ch[u][idx] = sz++;
}
u = ch[u][idx];
val[u]++;
}
}
void Delete(int x)
{
int u = 0;
for(int i = 31; i >= 0; i--)
{
int idx = (x>>i)&1;
u = ch[u][idx];
val[u]--;
}
}
int Match(int x, int y)
{
int u = 0, ans = 0;
for(int i = 31; i >= 0; i--)
{
int idxx = (x>>i)&1;
int idxy = (y>>i)&1;
if(!idxy)
{
if(!ch[u][idxx]) break;
u = ch[u][idxx];
}
else
{
if(ch[u][idxx]) ans += val[ch[u][idxx]];
if(!ch[u][!idxx]) break;
u = ch[u][!idxx];
}
}
return ans;
}
int main(void)
{
int q;
while(cin >> q)
{
init();
while(q--)
{
int cmd, x, y;
scanf("%d%d", &cmd, &x);
if(cmd == 1) Insert(x);
else if(cmd == 2) Delete(x);
else
{
scanf("%d", &y);
printf("%dn", Match(x, y));
}
}
}
return 0;
}

最后

以上就是迅速向日葵为你收集整理的Educational Codeforces Round 23 E. Choosing The Commander（01Trie）的全部内容，希望文章能够帮你解决Educational Codeforces Round 23 E. Choosing The Commander（01Trie）所遇到的程序开发问题。

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