動物統計加強版

時間限制：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

來源

[陳玉 張云聰]原創

AC代碼：

#include<iostream> #include<cstdio> #include<cstring> using namespace std; int data_TrieNode; struct TrieNode{int data;TrieNode *next[26];void init(){data=0;memset(next,0,sizeof(next));} };TrieNode *root=NULL; int Build(char *c){TrieNode *p=root;TrieNode *q=NULL;int i,v,l=strlen(c);for(i=0;i<l;i++){v=c[i]-'a';if(p->next[v]==NULL){q=new TrieNode();p->next[v]=q;p=p->next[v];}else p=p->next[v];}p->data++;return p->data; } int main() {int n,s,i,p;char c[15],str[15];while(cin>>n){s=0;root=new TrieNode(); for(i=0;i<n;i++){scanf("%s",c);p=Build(c);if(s<p){s=p;strcpy(str,c);}}printf("%s %d\n",str,s);}return 0; }

WR代碼：

#include<iostream> #include<cstdio> #include<cstring> using namespace std; int data_TrieNode; struct TrieNode{int data;TrieNode *next[26];void init(){data=0;memset(next,0,sizeof(next));} }Tree[4000001]; inline TrieNode *new_TrieNode(){ Tree[data_TrieNode].init(); return &Tree[data_TrieNode++]; } TrieNode *root=NULL; void Build(char *c){TrieNode *p=root;TrieNode *q=NULL;int i,v,l=strlen(c);for(i=0;i<l;i++){v=c[i]-'a';if(p->next[v]==NULL){q=new_TrieNode();p->next[v]=q;}p=p->next[v];p->data++;} } int Find(char *c){int i,v,l=strlen(c);TrieNode *p=root;for(i=0;i<l;i++){v=c[i]-'a';if(p->next[v]==NULL){return 0;break;}else p=p->next[v];}return p->data; } int main() {int n,s,i,p;char c[4000001][15];while(cin>>n){data_TrieNode=0;s=0;root=new_TrieNode(); for(i=0;i<n;i++){scanf("%s",c[i]);Build(c[i]);}for(i=0;i<n;i++){p=Find(c[i]);if(s<p){s=p;strcpy(c[0],c[i]);} }printf("%s %d\n",c[0],s);}return 0; }

總結

以上是生活随笔為你收集整理的nyoj 290的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。