首页 > 代码库 > trie树 Codeforces Round #367 D Vasiliy's Multiset
trie树 Codeforces Round #367 D Vasiliy's Multiset
1 // trie树 Codeforces Round #367 D Vasiliy‘s Multiset 2 // 题意:给一个集合,初始有0,+表示添加元素,-去除元素,?询问集合里面与x异或最大的值 3 // 思路:思路很好想,建立trie树,再贪心当前位是1则选0,0则选1 4 5 6 #include <bits/stdc++.h> 7 using namespace std; 8 #define LL long long 9 const double inf = 123456789012345.0;10 const LL MOD =100000000LL;11 const int N =1e7+10;12 #define clc(a,b) memset(a,b,sizeof(a))13 const double eps = 1e-7;14 void fre() {freopen("in.txt","r",stdin);}15 void freout() {freopen("out.txt","w",stdout);}16 inline int read() {int x=0,f=1;char ch=getchar();while(ch>‘9‘||ch<‘0‘) {if(ch==‘-‘) f=-1; ch=getchar();}while(ch>=‘0‘&&ch<=‘9‘) {x=x*10+ch-‘0‘;ch=getchar();}return x*f;}17 int d[N][2];18 int cnt=1;//节点下标19 int num[N];20 void update(int x){21 int k=1;22 for(int i=30;i>=0;i--){23 if(d[k][(x>>i)&1]==0) d[k][(x>>i)&1]=++cnt;24 k=d[k][(x>>i)&1];25 num[k]++;26 }27 }28 29 void update1(int x){30 int k=1;31 num[1]--;32 for(int i=30;i>=0;i--){33 k=d[k][(x>>i)&1];34 num[k]--;35 }36 }37 38 int query(int x){39 int k=1;40 int ans=0;41 for(int i=30;i>=0;i--){42 int t=(x>>i)&1;43 if(num[d[k][1^t]]) k=d[k][1^t],ans+=(1<<i);44 else k=d[k][t];45 }46 return ans;47 }48 49 int main(){50 int q;51 scanf("%d",&q);52 update(0);53 while(q--){54 char s[2];55 int x;56 scanf("%s%d",s,&x);57 if(s[0]==‘+‘) update(x);58 else if(s[0]==‘-‘) update1(x);59 else {60 int ans=query(x);61 printf("%d\n",ans);62 }63 }64 return 0;65 }
trie树 Codeforces Round #367 D Vasiliy's Multiset
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。