首页 > 代码库 > （字典树）codeforces - 706D Vasiliy's Multiset
（字典树）codeforces - 706D Vasiliy's Multiset
原题链接：http://codeforces.com/problemset/problem/706/D
题意：需要你模拟一个多重集合（初始拥有0），该集合拥有三个功能
1、+ x 增加一个x（可以同时存在多个x，因为是多重集合）
2、- x 去掉一个x
3、? x 输出在这个集合中和x异或最大的值。
分析：有20万个操作，很容易想到树形数据结构，我们可以看到每个x最多只有10^9，而1<<30比10^9大一点，所以10^9次方最多就是29位的01串，可以维护一个字典树。
每个节点有两个分支，0和1，深度最深也就是29。
我一开始想到把01串倒着往里插，因为在x进行&和>>1操作可以很方便达到这一点，但是+和-操作如果这样实现，就很难实现?操作了。
因为根据异或运算就是对应位相同为0，不同为1，而在01串中，越往左的1在10进制中的值就越大。
要取得异或的最大值，很容易想到就是贪心，从最左边开始比较，每次取和自己不同的那个分支，往下走，如果与自己不同的那个分支未曾建立过，或者统计的cnt已经==0（-操作删除了）就走相同的那一分支。
同时我们能够发现可以直接正着插，也就是说不管你的有效01串有几位，都把29位包含前导0的01串全都存进去。这就方便了?操作。
代码：
1 #include <set> 2 #include <map> 3 #include <list> 4 #include <cmath> 5 #include <queue> 6 #include <vector> 7 #include <bitset> 8 #include <string> 9 #include <cctype> 10 #include <cstdio> 11 #include <cstring> 12 #include <cstdlib> 13 #include <iostream> 14 #include <algorithm> 15 16 using namespace std; 17 18 typedef long long ll; 19 typedef unsigned long long ull; 20 #define inf (0x3f3f3f3f) 21 #define lnf (0x3f3f3f3f3f3f3f3f) 22 #define eps (1e-8) 23 int sgn(double a){return a < -eps ? -1 : a < eps ? 0 : 1;} 24 25 //-------------------------- 26 27 28 struct Trie_node { 29 int cnt; 30 int next[2]; 31 }tree[10000010]; 32 int nxt; 33 34 int createTrieNode() { 35 memset(&tree[nxt], 0, sizeof(Trie_node)); 36 return nxt++; 37 } 38 39 void Trie_insert(int val) { 40 int rt=0; 41 char bir[30]; 42 for(int i=29;i>=0;i--){ 43 bir[i]=(val&1)+‘0‘; 44 val>>=1; 45 } 46 for(int i=0;i<30;i++){ 47 int id=bir[i]-‘0‘; 48 if(!tree[rt].next[id]){ 49 tree[rt].next[id]=createTrieNode(); 50 } 51 rt=tree[rt].next[id]; 52 tree[rt].cnt++; 53 } 54 } 55 56 void Trie_remove(int val){ 57 int rt=0; 58 char bir[30]; 59 for(int i=29;i>=0;i--){ 60 bir[i]=(val&1)+‘0‘; 61 val>>=1; 62 } 63 for(int i=0;i<30;i++){ 64 int id=bir[i]-‘0‘; 65 rt=tree[rt].next[id]; 66 tree[rt].cnt--; 67 } 68 69 } 70 71 int Trie_search(int val) { 72 int rt=0; 73 char res[30]={0}; 74 int ans=0; 75 char bir[30]; 76 for(int i=29;i>=0;i--){ 77 bir[i]=(val&1)+‘0‘; 78 val>>=1; 79 } 80 for(int i=0;i<30;i++){ 81 int id=bir[i]-‘0‘; 82 if(tree[rt].next[id^1]&&tree[tree[rt].next[id^1]].cnt>0){ 83 rt=tree[rt].next[id^1]; 84 res[i]=‘1‘; 85 } 86 else{ 87 rt=tree[rt].next[id]; 88 res[i]=‘0‘; 89 } 90 } 91 int k=0; 92 for(;k<30&&res[k]==‘0‘;){ 93 k++; 94 } 95 for(int i=29;i>=k;i--){ 96 ans+=(1<<(29-i))*(res[i]-‘0‘); 97 } 98 return ans; 99 }100 101 102 void init(){103 nxt=1;104 memset(&tree[0],0,sizeof(Trie_node));105 }106 107 char op[2];108 int v;109 110 void solve() {111 init();112 Trie_insert(0);113 int t;114 scanf("%d",&t);115 while(t--){116 scanf("%s%d",op,&v);117 if(op[0]==‘+‘)Trie_insert(v);118 else if(op[0]==‘-‘)Trie_remove(v);119 else if((op[0]==‘?‘))printf("%d\n",Trie_search(v));120 }121 }122 123 124 125 126 int main() {127 128 #ifndef ONLINE_JUDGE129 freopen("in.txt", "r", stdin);130 //freopen("out.txt", "w", stdout);131 #endif132 //iostream::sync_with_stdio(false);133 solve();134 return 0;135 }
（字典树）codeforces - 706D Vasiliy's Multiset
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。