不断的将字符串插在trie树中,并且不断的更新节点的附加信息。
用数组来模拟树型结构
Trie板题
Hardwood Species
题意
给很多个树的名称,会有重复的名字。
然后统计每一个不同的名字占有总数的比例
题解
键trie树,最后统计的时候扫一遍就可以了。
AC代码
用%.4f输出就AC了, 用%.4lf输出就WA了emmmmm
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57
| #include <iostream> #include <cstdio> #include <vector> #include <cstring> #include <algorithm> using namespace std; const int maxn = 1e4+10; struct Node{ int num; int son[256]; Node(){ this->num = 0; memset(this->son, 0, sizeof(this->son)); } }node[maxn]; char s[100]; char ss[100]; int tot = 1; void insert_trie(char* s, int p){ int len = strlen(s); int num; for(int i=0; i<len; i++){ num = s[i]; if(node[p].son[num]!=0){ p = node[p].son[num]; } else{ node[p].son[num] = tot++; p = tot-1; } } node[p].num++; } int tot_str=0; void print_trie(int p, int len){ if(node[p].num!=0){ printf("%s %.4lf\n", ss, double(node[p].num)/tot_str*100); } for(int i=0; i<256; i++){ if(node[p].son[i]){ ss[len] = i; print_trie(node[p].son[i], len+1); ss[len] = '\0'; } } } int main(){ while(gets(s)){ insert_trie(s, 0); tot_str++; } print_trie(0, 0); return 0; }
|
未解决的问题