首页 > 代码库 > CodeForces 706D Vasiliy's Multiset
CodeForces 706D Vasiliy's Multiset
字典树。
比较经典的题目了。把每一个数字都插入到字典树中，询问的时候如果$x$的第$i$位是$p$，那么尝试着在字典树上往$pXOR1$的节点走下去，没有$pXOR1$节点的话再走$p$的。删除操作的话可以记录一下每一个节点出现了几次，$Insert$的时候$s[p].cnt++$，$Delete$的时候$s[p].cnt--$，如果发现$s[p].cnt==0$，那么将以$p$为根的树全删了，也就是$p$的$father$到$p$的路标为$-1$。
#pragma comment(linker, "/STACK:1024000000,1024000000")#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<vector>#include<map>#include<set>#include<queue>#include<stack>#include<iostream>using namespace std;typedef long long LL;const double pi=acos(-1.0),eps=1e-8;void File(){ freopen("D:\\in.txt","r",stdin); freopen("D:\\out.txt","w",stdout);}const int maxn=200010;struct X { int nx[2], cnt; }s[32*maxn];int n,x,h,sz; char op[5];int add(){ sz++; s[sz].cnt=0; s[sz].nx[0]=s[sz].nx[1]=-1; return sz;}void Insert(int x){ int p=0; for(int i=30;i>=0;i--) { if((1<<i)&x) h=1; else h=0; if(s[p].nx[h]==-1) s[p].nx[h]=add(); p=s[p].nx[h]; s[p].cnt++; }}void Delete(int x){ int p=0; for(int i=30;i>=0;i--) { if((1<<i)&x) h=1; else h=0; int t=p; p=s[p].nx[h]; s[p].cnt--; if(s[p].cnt==0) s[t].nx[h]=-1; }}int Find(int x){ int p=0,res=0; for(int i=30;i>=0;i--) { if((1<<i)&x) h=1; else h=0; if(s[p].nx[h^1]!=-1) p=s[p].nx[h^1],res=res+(1<<i); else if(s[p].nx[h]!=-1)p=s[p].nx[h]; } return res;}int main(){ scanf("%d",&n); s[0].nx[0]=s[0].nx[1]=-1; s[0].cnt=0; sz=0; Insert(0); for(int i=1;i<=n;i++) { scanf("%s%d",op,&x); if(op[0]==‘+‘) Insert(x); else if(op[0]==‘-‘) Delete(x); else printf("%d\n",Find(x)); } return 0;}
CodeForces 706D Vasiliy's Multiset
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。