首页 > 代码库 > UVa 10226 - Hardwood Species
UVa 10226 - Hardwood Species
题目:有很多不同名称的树,统计每种树出现的概率。
分析:字符串,字典树(trie)。直接利用字典树计数,然后排序输出即可。
说明:POJ2418没有测试组数,TLE几次才发现╮(╯▽╰)╭。
#include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> using namespace std; char words[32]; /* Trie define */ typedef struct node0 { char name[32]; int times; }tree; tree T[12001]; bool cmp( tree a, tree b ) { return strcmp(a.name, b.name)<0; } #define nodesize 30003 //节点个数 #define dictsize 128 //字符集大小 typedef struct node1 { int flag; //值域 node1* next[dictsize]; }tnode; tnode dict[nodesize]; class Trie { private: int size; int count; tnode* root; public: Trie() {initial();} void initial() { memset( dict, 0, sizeof( dict ) ); count = 0; size=0; root=newnode(); } tnode* newnode() {return &dict[size ++];} void insert( char* word ) { tnode* now = root; for ( int i = 0 ; word[i] ; ++ i ) { if ( !now->next[word[i]] ) now->next[word[i]] = newnode(); now = now->next[word[i]]; } if ( !now->flag ) { now->flag = ++ count; strcpy(T[now->flag-1].name, word); T[now->flag-1].times = 1; }else T[now->flag-1].times ++; } void output(int sum) { sort(T, T+count, cmp); for ( int i = 0 ; i < count ; ++ i ) printf("%s %.4lf\n",T[i].name,100.0/sum*T[i].times); } }trie; /* Trie end */ int main() { int t,count; scanf("%d",&t); getchar(); getchar(); while (t --) { trie.initial(); count = 0; while ( gets(words) && strlen(words) ) { trie.insert( words ); count ++; } trie.output(count); if (t) printf("\n"); } return 0; }
UVa 10226 - Hardwood Species
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。