nyoj--290--动物统计加强版

绝地灬酷狼 2022-06-10 04:38 202阅读 0赞

## 动物统计加强版 ##

时间限制： 3000 ms  |  内存限制： 150000 KB

难度： 4

描述

在美丽大兴安岭原始森林中存在数量繁多的物种，在勘察员带来的各种动物资料中有未统计数量的原始动物的名单。科学家想判断这片森林中哪种动物的数量最多，但是由于数据太过庞大，科学家终于忍受不了，想请聪明如你的ACMer来帮忙。

输入

第一行输入动物名字的数量N(1<= N <= 4000000),接下来的N行输入N个字符串表示动物的名字（字符串的长度不超过10,字符串全为小写字母，并且只有一组测试数据）。

输出

输出这些动物中最多的动物的名字与数量，并用空格隔开（数据保证最多的动物不会出现两种以上）。

样例输入

10
    boar
    pig
    sheep
    gazelle
    sheep
    sheep
    alpaca
    alpaca
    marmot
    mole

样例输出

sheep 3

解题思路：

开始用map做了一遍，果断超时。后来改用字典树做，ac了，思路也很简单，就是在声明Trie节点的时候，加入一个num成员，用来记录各个单词出现的个数，在插入单词

的同时，进行计数，另外声明一个int 型的ans，记录出现的单词的最大次数，char类型的数组 b，记录出现次数最多的单词，当单词全部插入的时候，结果也就出来了，这里有两种字典树实现的方法，一种是利用树组实现，另一种是用链表实现，可以根据自己的情况进行选择；

链表代码：

C++ Code

<table style="width:100%; font-family:'Consolas','Courier New'; font-size:12px; vertical-align:text-top; line-height:15px"> 
 <tbody> 
 <tr> 
 <td style="color:#008284; background-color:#e3e3e3; vertical-align:text-top"> 
 <div style="margin:7px; text-align:right; white-space:nowrap">
 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 
 
 </div> </td> 
 <td style="background-color:#008284; padding:1px"> 
 <div style="border:1px #008284 solid"></div> </td> 
 <td style="background-color:rgb(239,239,239); width:100%; vertical-align:text-top"> 
 <div style="margin:7px"> 
 #include&lt;bits/stdc++.h&gt; 
 
 #define&nbsp;MAX&nbsp; 
 26 
 
 using&nbsp; 
 namespace&nbsp;std; 
 
 typedef&nbsp; 
 struct&nbsp;TrieNode&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 ///Trie节点声明 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;&nbsp;num;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 ///记录这个单词的个数 &nbsp;&nbsp;&nbsp;&nbsp; 
 struct&nbsp;TrieNode&nbsp;*next[MAX];&nbsp;&nbsp;&nbsp; 
 ///儿子分支 }&nbsp;Trie; 
 
 int&nbsp;ans&nbsp;=&nbsp;- 
 1; 
 
 char&nbsp;b[ 
 15]; 
 
 void&nbsp;insert1(Trie&nbsp;*root,&nbsp; 
 char&nbsp;*s) 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 char&nbsp;w[ 
 15]; 
 &nbsp;&nbsp;&nbsp;&nbsp;strcpy(w,&nbsp;s); 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 if(root&nbsp;==&nbsp; 
 NULL&nbsp;||&nbsp;*s&nbsp;==&nbsp; 
 '\0') 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp;; 
 &nbsp;&nbsp;&nbsp;&nbsp;Trie&nbsp;*p&nbsp;=&nbsp;root; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 while(*s&nbsp;!=&nbsp; 
 0) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if(p-&gt;next[*s&nbsp;-&nbsp; 
 'a']&nbsp;==&nbsp; 
 NULL) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Trie&nbsp;*temp&nbsp;=&nbsp;(Trie&nbsp;*)malloc( 
 sizeof(Trie)); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;i&nbsp;=&nbsp; 
 0;&nbsp;i&nbsp;&lt;&nbsp;MAX;&nbsp;i++) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;temp-&gt;next[i]&nbsp;=&nbsp; 
 NULL; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;temp-&gt;num&nbsp;=&nbsp; 
 0; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;p-&gt;next[*s&nbsp;-&nbsp; 
 'a']&nbsp;=&nbsp;temp; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;p&nbsp;=&nbsp;p-&gt;next[*s&nbsp;-&nbsp; 
 'a']; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 else 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;p&nbsp;=&nbsp;p-&gt;next[*s&nbsp;-&nbsp; 
 'a']; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;s++; 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;p-&gt;num++; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 if(p-&gt;num&nbsp;&gt;&nbsp;ans) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ans&nbsp;=&nbsp;p-&gt;num; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;strcpy(b,&nbsp;w); 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 } 
 
 int&nbsp;main() 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;n; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 char&nbsp;a[ 
 15]; 
 &nbsp;&nbsp;&nbsp;&nbsp;Trie&nbsp;*root&nbsp;=&nbsp;(Trie&nbsp;*)malloc( 
 sizeof(Trie)); 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;i&nbsp;=&nbsp; 
 0;&nbsp;i&nbsp;&lt;&nbsp;MAX;&nbsp;i++) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;root-&gt;next[i]&nbsp;=&nbsp; 
 NULL; 
 &nbsp;&nbsp;&nbsp;&nbsp;scanf( 
 "%d",&nbsp;&amp;n); 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;i&nbsp;=&nbsp; 
 0;&nbsp;i&nbsp;&lt;&nbsp;n;&nbsp;i++) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;scanf( 
 "%s",&nbsp;a); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;insert1(root,&nbsp;a); 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;printf( 
 "%s&nbsp;%d\n",&nbsp;b,&nbsp;ans); 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp; 
 0; 
 } 
 
 </div> </td> 
 </tr> 
 </tbody> 
</table>

数组代码：

C++ Code

<table style="width:100%; font-family:'Consolas','Courier New'; font-size:12px; vertical-align:text-top; line-height:15px"> 
 <tbody> 
 <tr> 
 <td style="color:#008284; background-color:#e3e3e3; vertical-align:text-top"> 
 <div style="margin:7px; text-align:right; white-space:nowrap">
 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 
 
 </div> </td> 
 <td style="background-color:#008284; padding:1px"> 
 <div style="border:1px #008284 solid"></div> </td> 
 <td style="background-color:rgb(239,239,239); width:100%; vertical-align:text-top"> 
 <div style="margin:7px"> 
 #include&nbsp;&lt;bits/stdc++.h&gt; 
 
 using&nbsp; 
 namespace&nbsp;std; 
 
 #define&nbsp;idx(x)&nbsp;x&nbsp;-&nbsp; 
 'a'; 
 
 const&nbsp; 
 int&nbsp;MAXN&nbsp;=&nbsp;1e6; 
 
 struct&nbsp;Trie 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;next[ 
 26]; 
 ///存储下一个节点的情况 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;val; 
 ///数据域 &nbsp;&nbsp;&nbsp;&nbsp; 
 char&nbsp;w[ 
 15]; 
 }&nbsp;tree[MAXN]; 
 
 
 int&nbsp;maxn&nbsp;=&nbsp;- 
 1; 
 
 char&nbsp;ans[ 
 15]; 
 
 int&nbsp;nxt,&nbsp;T; 
 ///nxt表示节点的编号 
 char&nbsp;str[ 
 15]; 
 
 int&nbsp;add() 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 ///开辟新的节点，并进行初始化 &nbsp;&nbsp;&nbsp;&nbsp;memset(&amp;tree[nxt],&nbsp; 
 0,&nbsp; 
 sizeof(Trie)); 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp;nxt++; 
 } 
 
 void&nbsp;Insert( 
 char&nbsp;*s) 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;rt&nbsp;=&nbsp; 
 0,&nbsp;len&nbsp;=&nbsp;strlen(s);&nbsp; 
 ///rt=0，每次插入都从根节点开始查询， &nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;i&nbsp;=&nbsp; 
 0;&nbsp;i&nbsp;&lt;&nbsp;len;&nbsp;i++) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;c&nbsp;=&nbsp;idx(s[i]); 
 ///把字母转化为数字 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if(!tree[rt].next[c]) 
 ///如果这个节点还不存在，就用add函数开辟新的节点 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;tree[rt].next[c]&nbsp;=&nbsp;add(); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;rt&nbsp;=&nbsp;tree[rt].next[c]; 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;tree[rt].val++; 
 &nbsp;&nbsp;&nbsp;&nbsp;strcpy(tree[rt].w,&nbsp;s); 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 if(tree[rt].val&nbsp;&gt;&nbsp;maxn) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;maxn&nbsp;=&nbsp;tree[rt].val; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;strcpy(ans,&nbsp;tree[rt].w); 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 } 
 
 int&nbsp;main() 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp;memset(&amp;tree[ 
 0],&nbsp; 
 0,&nbsp; 
 sizeof(Trie)); 
 &nbsp;&nbsp;&nbsp;&nbsp;nxt&nbsp;=&nbsp; 
 1; 
 &nbsp;&nbsp;&nbsp;&nbsp;scanf( 
 "%d",&nbsp;&amp;T); 
 &nbsp;&nbsp;&nbsp;&nbsp;maxn&nbsp;=&nbsp;- 
 1; 
 &nbsp;&nbsp;&nbsp;&nbsp;ans[ 
 15]; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 while(T--) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;scanf( 
 "%s",&nbsp;str); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Insert(str); 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;printf( 
 "%s&nbsp;%d\n",&nbsp;ans,&nbsp;maxn); 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp; 
 0; 
 } 
 </div> </td> 
 </tr> 
 </tbody> 
</table>