首页 > 代码库 > （字典树）codeforces - 713A Sonya and Queries
（字典树）codeforces - 713A Sonya and Queries
原题链接：http://codeforces.com/problemset/problem/713/Attr
题意：一个集合，有三个操作，+-?，其中+和-和上一次cf的字典树那题是一个意思，?操作是统计满足01模式串的字典树中数的个数。如果模式串比字典中的数长就补全数，如果数长就补全模式串。
分析：
这题居然写了一个小时，一开始20分钟差不多写完了，但是一直坑在两种长度不同的情况上，后来仔细一想，卧槽，so easy啊，直接默认全部补全到18位不就行了。。那样这题就是一个简单的求前缀的个数。
其实思路和上次的差不多，都是补全后插入。我好年轻。
代码：
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 typedef struct Trie_node { 28 int cnt; 29 struct Trie_node* next[2]; 30 int exist; 31 } TrieNode,*Trie; 32 33 TrieNode* createTrieNode() { 34 TrieNode* node = (TrieNode *)malloc(sizeof(TrieNode)); 35 node->cnt = 0; 36 node->exist =0; 37 memset(node->next, 0, sizeof(node->next)); 38 return node; 39 } 40 41 void Trie_insert(Trie root, ll &nn) { 42 Trie node = root; 43 for(int i=0;i<18;i++){ 44 int id=nn&1; 45 if(node->next[id]==NULL)node->next[id]=createTrieNode(); 46 node=node->next[id]; 47 node->cnt++; 48 nn/=10; 49 } 50 } 51 52 void Trie_remove(Trie root,ll &nn){ 53 Trie node = root; 54 for(int i=0;i<18;i++){ 55 int id=nn&1; 56 node=node->next[id]; 57 node->cnt--; 58 nn/=10; 59 } 60 } 61 62 int Trie_search(Trie root, string word) { 63 Trie node = root; 64 reverse(word.begin(),word.end()); 65 int len=word.length(); 66 for(int i=0;i<18-len;i++){ 67 word.push_back(‘0‘); 68 } 69 for(int i=0;i<word.length();i++) { 70 int id = word[i]-‘0‘; 71 node = node->next[id]; 72 if(node==NULL||node->cnt<=0)return 0; 73 } 74 return node->cnt; 75 } 76 char op[2]; 77 char num[20]; 78 ll nn; 79 void solve() { 80 TrieNode *root=createTrieNode(); 81 int n; 82 scanf("%d",&n); 83 for(int i=0;i<n;i++){ 84 scanf("%s",op); 85 if(op[0]==‘+‘){ 86 scanf("%I64d",&nn); 87 Trie_insert(root,nn); 88 } 89 if(op[0]==‘-‘){ 90 scanf("%I64d",&nn); 91 Trie_remove(root,nn); 92 } 93 if(op[0]==‘?‘){ 94 scanf("%s",num); 95 printf("%d\n",Trie_search(root,num)); 96 } 97 } 98 } 99 100 101 102 103 int main() {104 105 106 #ifndef ONLINE_JUDGE107 freopen("in.txt", "r", stdin);108 //freopen("out.txt", "w", stdout);109 110 #endif111 //iostream::sync_with_stdio(false);112 solve();113 return 0;114 }
（字典树）codeforces - 713A Sonya and Queries
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。