本文共 1730 字，大约阅读时间需要 5 分钟。
Let the Balloon Rise（hdu 1004）
ACM比赛，裁判们最大的乐趣就是猜所有队伍做出哪道题的数量最多。比赛结束时，他们开始数挂出的哪种颜色气球的数量最多，即知道了他们猜测的结果。 今年，他们决定将这个有趣的工作交给你。
输入：
输入包括多组数据。每组数据以一个整数N (0 < N <= 1000) 开始，下面N行每行为一个气球的颜色。气球的颜色为一个只包含小写英文字母的字符串，且字符串长度不超过15。 当 N = 0 时，测试数据结束，且该组数据不用处理。
输出：
对于每组测试数据，你应该输出出现次数最多的气球颜色。每组数据其结果一定是惟一的。
输入样例：
5
green
red
blue
red
red
3
pink
orange
pink
0
输出样例：
red
pink
分析：
把每个单词插入到Trie树里，记录单词出现的次数。再查找Trie树，那个单词出现的次数最多即为输出结果。
代码：
#include#include #include #include using namespace std;typedef struct node//节点结构{ struct node * next[26]; int value; int num;}*trie, node;trie root;void init_trie(trie &p)//trie树初始化{ p = (trie) malloc ( sizeof(node) ); for(int i = 0; i < 26; i++) p->next[i] = 0; p->value = p->num = 0;}void insert(trie p,char s[])//插入操作{ int k = 0; while(s[k] != '\0') { if( ! p->next[s[k]-'a']) { trie q; init_trie(q); p->next[s[k]-'a'] = q; } p = p->next[s[k]-'a']; p->num ++; k++; } p->value = 1;}int find(trie p,char s[])//插找{ int k = 0; while(s[k] != '\0' && p->next[s[k]-'a']) { p = p->next[s[k]-'a']; k++; } if(s[k]=='\0') return p->num; return 0;}int main(){ int n; while(scanf("%d",&n) != EOF && n) { init_trie(root); char ch[1005][17]; for(int i = 0; i < n; i++) { cin>>ch[i]; insert(root, ch[i]); } int max = 0, tem, f; for(int i = 0; i < n; i++) { tem = find(root, ch[i]); if(tem > max) { max = tem; f = i; } } cout<< ch[f] << "\n"; } return 0;
转载地址：http://gsali.baihongyu.com/