首页 > 代码库 > Codeforces Round #371 (Div. 2) C. Sonya and Queries（字典树）
Codeforces Round #371 (Div. 2) C. Sonya and Queries（字典树）
题目戳这
题意：给你一个数字 n ，然后 n 组输入，如果第一个字符是+，就把后面的那个数字加入到集合里面去，如果第一个字符是减号，就把后面的那个数字从集合里面去掉一个，如果是问好，就开始配对，看看有多少个数字是和问号后面的数字是匹配的，是否配对的规则是，问好后面的数字都是二进制，一表示奇数，零表示偶数，如果集合中的数字长度和二进制的输入长度不一样，就把短的那个在前面加零，比如，二进制是101，集合中的数字是12，那就是101和012匹配，如果二进制是11，集合中的数字是12345，那么就是00011和12345匹配，奇偶数的位置要一样。
思路：用字典树来进行增删查的操作，并且每次把数字插入进字典树的时候，都要把数字补齐成18位，然后从左边开始插入进字典树，并且插入的时候按照奇偶数的位置把偶数换成零，把奇数换成一插入进字典树，查询的时候也是要把二进制补齐成18位，然后进行查询，删除的时候也是要把数字处理成01串。
p.s.这道题有两种做法，一种就是用字典树来进行增删查，还有一种就是把每个数都换成01串之后再处理成十进制，然后用数组标记的做法来进行增删查用字典树：
1 #include<stdio.h> 2 #include<iostream> 3 #include<string.h> 4 #include<math.h> 5 #include<algorithm> 6 #include<vector> 7 #include<string> 8 #include<queue> 9 #include<map> 10 #include<stack> 11 #include<set> 12 #define ll long long 13 #define maxn 100010 14 #define PI acos(-1.0) //圆周率 15 const ll INF = 1e18; 16 using namespace std; 17 struct node 18 { 19 int sz; 20 int ch[45*maxn][3]; 21 int sum[45*maxn]; 22 23 void trie() 24 { 25 sz=1; 26 memset(ch,0,sizeof(ch)); 27 memset(sum,0,sizeof(sum)); 28 } 29 30 void add(string x) 31 { 32 int len=x.length(); 33 int k=18-len; 34 int u=0; 35 for(int i=0;i<k;i++) 36 { 37 if(ch[u][0]==0) ch[u][0]=sz++; 38 u=ch[u][0]; 39 } 40 for(int i=0;i<len;i++) 41 { 42 int f=x[i]-‘0‘; 43 int t=0; 44 if(f%2==0) t=0; 45 else t=1; 46 47 if(ch[u][t]==0) ch[u][t]=sz++; 48 u=ch[u][t]; 49 } 50 51 sum[u]++; 52 } 53 54 void del(string x) 55 { 56 int len=x.length(); 57 int u=0; 58 int k=18-len; 59 60 for(int i=0;i<k;i++) 61 { 62 if(ch[u][0]==0) ch[u][0]=sz++; 63 u=ch[u][0]; 64 } 65 66 for(int i=0;i<len;i++) 67 { 68 int f=x[i]-‘0‘; 69 int t=0; 70 if(f%2==0) t=0; 71 else t=1; 72 73 if(ch[u][t]==0) ch[u][t]=sz++; 74 u=ch[u][t]; 75 } 76 77 sum[u]--; 78 } 79 80 int query(string x) 81 { 82 int len=x.length(); 83 int u=0; 84 int k=18-len; 85 86 for(int i=0;i<k;i++) u=ch[u][0]; 87 88 for(int i=0;i<len;i++) 89 { 90 int t=x[i]-‘0‘; 91 u=ch[u][t]; 92 } 93 94 return sum[u]; 95 } 96 }st; 97 int n; 98 string s; 99 char fu[3];100 int main()101 {102 scanf("%d",&n);103 st.trie();104 for(int i=0;i<n;i++)105 {106 scanf("%s",fu);107 cin>>s;108 109 if(fu[0]==‘+‘) st.add(s);110 else if(fu[0]==‘-‘) st.del(s);111 else printf("%d\n",st.query(s));112 }113 114 return 0;115 }
用数组标记：
1 #include<stdio.h> 2 #include<iostream> 3 #include<string.h> 4 #include<math.h> 5 #include<algorithm> 6 #include<vector> 7 #include<string> 8 #include<queue> 9 #include<map>10 #include<stack>11 #include<set>12 #define ll long long13 #define maxn 10001014 #define PI acos(-1.0) //圆周率15 const ll INF = 1e18;16 using namespace std;17 ll num[45*maxn];18 int n;19 int main()20 {21 scanf("%d",&n);22 ll k;23 char s[3];24 for(int i=0;i<n;i++)25 {26 scanf("%s %I64d",s,&k);27 int cnt=0;28 int f=0;29 ll ans=0;30 while(k)31 {32 cnt=k%10;33 k/=10;34 if(cnt%2!=0) ans+=(ll)pow(2,f);35 f++;36 }37 38 if(s[0]==‘+‘) num[ans]++;39 else if(s[0]==‘-‘) num[ans]--;40 else printf("%d\n",num[ans]);41 }42 43 return 0;44 }
Codeforces Round #371 (Div. 2) C. Sonya and Queries（字典树）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。