動物統(tǒng)計加強(qiáng)版

時間限制：3000?ms ?|? 內(nèi)存限制：150000?KB 難度：4 描述

在美麗大興安嶺原始森林中存在數(shù)量繁多的物種，在勘察員帶來的各種動物資料中有未統(tǒng)計數(shù)量的原始動物的名單。科學(xué)家想判斷這片森林中哪種動物的數(shù)量最多，但是由于數(shù)據(jù)太過龐大，科學(xué)家終于忍受不了，想請聰明如你的ACMer來幫忙。

輸入

第一行輸入動物名字的數(shù)量N(1<= N <= 4000000),接下來的N行輸入N個字符串表示動物的名字（字符串的長度不超過10,字符串全為小寫字母，并且只有一組測試數(shù)據(jù)）。?

輸出

輸出這些動物中最多的動物的名字與數(shù)量，并用空格隔開（數(shù)據(jù)保證最多的動物不會出現(xiàn)兩種以上）。?

樣例輸入

10 boar pig sheep gazelle sheep sheep alpaca alpaca marmot mole

樣例輸出

sheep 3

題解：貪心ac，字典樹me，map超時；

代碼：

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<vector> #include<algorithm> using namespace std; const int INF=0x3f3f3f3f; const double PI=acos(-1.0); typedef long long LL; #define mem(x,y) memset(x,y,sizeof(x)) #define T_T while(T--) #define F(i,x) for(i=0;i<x;i++) #define SI(x) scanf("%d",&x) #define SL(x) scanf("%lld",&x) #define PI(x) printf("%d",x) #define PL(x) printf("%lld",x) #define P_ printf(" ") const int MAXN=4000010; struct Node{char s[12];int num;friend bool operator < (Node const &a,Node const &b){if(strcmp(a.s,b.s)<0)return true;return false;} }dt[MAXN]; int main(){int N;int i,j;SI(N);mem(dt,0);F(i,N){scanf("%s",dt[i].s);dt[i].num=1;}sort(dt,dt+N);int ans=0;int ms=0;for(i=1;i<N;i++){if(strcmp(dt[i].s,dt[i-1].s)==0)dt[i].num=dt[i-1].num+1;if(dt[i].num>ms){ms=dt[i].num;ans=i;}}printf("%s %d\n",dt[ans].s,ms);return 0; }

　　

map超時

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<vector> #include<algorithm> #include<map> #include<string> using namespace std; const int INF=0x3f3f3f3f; const double PI=acos(-1.0); typedef long long LL; #define mem(x,y) memset(x,y,sizeof(x)) #define T_T while(T--) #define F(i,x) for(i=0;i<x;i++) #define SI(x) scanf("%d",&x) #define SL(x) scanf("%lld",&x) #define PI(x) printf("%d",x) #define PL(x) printf("%lld",x) #define P_ printf(" ") map<string,int>mp; int main(){int N;char s[15],t[15];SI(N);int i;mp.clear();F(i,N){scanf("%s",s);mp[s]++;}map<string,int>::iterator iter;int ms=0;for(iter=mp.begin();iter!=mp.end();iter++){if(iter->second>ms){ms=iter->second;strcpy(t,iter->first.c_str());}}printf("%s %d\n",t,ms);return 0; }

　　字典樹me

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<vector> #include<algorithm> #include<map> #include<string> using namespace std; const int INF=0x3f3f3f3f; const double PI=acos(-1.0); typedef long long LL; #define mem(x,y) memset(x,y,sizeof(x)) #define T_T while(T--) #define F(i,x) for(i=0;i<x;i++) #define SI(x) scanf("%d",&x) #define SL(x) scanf("%lld",&x) #define PI(x) printf("%d",x) #define PL(x) printf("%lld",x) #define P_ printf(" ") const int MAXN=4000010; int word[MAXN],ch[MAXN][26],val[MAXN];//ch[MAXN][26]里的MAXN還沒開夠應(yīng)該開到MAXN*12，數(shù)據(jù)量太大了 //肯定me了 char ans[12]; int sz,mm; void join(char *s){int len=strlen(s),k=0;for(int i=0;i<len;i++){int j=s[i]-'a';if(!ch[k][j]){mem(ch[sz],0);ch[k][j]=sz++;}k=ch[k][j];word[k]++;}if(word[k]>mm){mm=word[k];memcpy(ans,s,sizeof(s));} } int find(char *s){int i,j,len=strlen(s),k=0;F(i,len){j=s[i]-'a';k=ch[k][j];}return word[k]; } int main(){int N;int i,j;sz=0;SI(N);mm=0;char s[12];F(i,N){scanf("%s",s);join(s);}printf("%s %d\n",ans,mm);return 0; }

　　

自己寫了一發(fā)鏈表ac了；

#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> using namespace std; struct Node{int num;Node *next[30]; }; Node *root; char ans[12],s[12]; int mm; void insert(char *s){Node *p=root,*q;for(int i=0;s[i];i++){int j=s[i]-'a';if(p->next[j]==NULL){q=(Node *)malloc(sizeof(Node));q->num=0;for(int k=0;k<30;k++)q->next[k]=NULL;p->next[j]=q;}p=p->next[j];}if(++p->num>mm){mm=p->num;memcpy(ans,s,sizeof(s));} } void freeroot(Node *r){for(int i=0;i<30;i++){if(r->next[i]!=NULL){freeroot(r->next[i]);free(r->next[i]);}else free(r->next[i]);} } void initial(){root=(Node *)malloc(sizeof(Node));root->num=0;for(int i=0;i<30;i++)root->next[i]=NULL; } int main(){int N;scanf("%d",&N);initial();mm=0;while(N--){scanf("%s",s);insert(s);}printf("%s %d\n",ans,mm);freeroot(root);//不加也可以為了優(yōu)化內(nèi)存，加了反而時間長一些； return 0; }

　　

?

大神的鏈表；

#include<stdio.h> #include<string.h> #include<math.h> #include<stack> #include<iostream> #include<algorithm> #define fab(a) (a)>0?(a):(-a) #define LL long long #define MAXN 10010 #define mem(x) memset(x,0,sizeof(x)) #define INF 0xfffffff using namespace std; struct s {int num;s *next[26]; }; s *root; int ans=0; char sa[12]; void create(char *str) {int len=strlen(str);s *p=root,*q;for(int i=0;i<len;i++){int id=str[i]-'a';if(p->next[id]==NULL){q=(s *)malloc(sizeof(s));for(int j=0;j<26;j++)q->next[j]=NULL;q->num=0;p->next[id]=q;p=p->next[id];}else{//if(i==len-1)p=p->next[id];}}if(ans<++p->num){strcpy(sa,str);ans=p->num;}} void begin() {for(int i=0;i<26;i++)root->next[i]=NULL,root->num=0; } void freetree(s *t) {if(t==NULL)return;for(int i=0;i<26;i++){if(t->next[i]!=NULL)freetree(t->next[i]);}free(t);return; } int main() {int t,i,n;char ss[12];int bz=0;root=(s *)malloc(sizeof(s));begin();scanf("%d",&n);for(i=0;i<n;i++){scanf("%s",ss);create(ss);}printf("%s %d\n",sa,ans);freetree(root);return 0; }

　　過段時間又寫了下，一遍A，感覺比以前寫的要簡單些了；

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; typedef long long LL; #define mem(x,y) memset(x,y,sizeof(x)) #define SI(x) scanf("%d",&x) #define PI(x) printf("%d",x) #define P_ printf(" ") const int INF=0x3f3f3f3f; const int MAXN=4000010;//要開的足夠大 char ans[15]; int cur; struct Node{int num;Node* next[30];Node init(){for(int i=0;i<30;i++)next[i]=NULL;num=0;} }; Node head; void insert(char *s){int j;Node *p=&head,*q;for(int i=0;s[i];i++){j=s[i]-'a';if(p->next[j]==NULL){q=(Node *)malloc(sizeof(Node));q->init();p->next[j]=q;}p=p->next[j];}p->num++;if(p->num>cur){strcpy(ans,s);cur=p->num;} } int main(){int N;char s[15];while(~scanf("%d",&N)){head.init();cur=0;for(int i=0;i<N;i++){scanf("%s",s);insert(s);}printf("%s %d\n",ans,cur);}return 0; }

java代碼：很奇怪的說java返回數(shù)組出現(xiàn)了一些問題，

鏈接會造成返回的數(shù)組結(jié)果是地址，出錯，不連接就可以輸出數(shù)組內(nèi)容

import java.util.Scanner;public class nyoj290{public static void main(String[] argv){tire atire = new tire();Scanner cin = new Scanner(System.in);int N = cin.nextInt();char s[] = new char[20];while(N-- > 0){s = cin.next().toCharArray();atire.insert(s);}char[] xx = "hello".toCharArray();//System.out.println(getanimal1(xx));//System.out.print(atire.getanimal()+" " + atire.getnum());//鏈接會造成返回的數(shù)組結(jié)果是地址，出錯，不連接就可以輸出數(shù)組內(nèi)容System.out.print(atire.getanimal());System.out.println(" " + atire.getnum());} } class tire{private Node head = new Node();private int number;private static char[] animal;public tire(){number = 0;animal = new char[20];}public void insert(char[] s){Node p = head, q;int j;for(int i = 0; i < s.length; i++){j = s[i] - 'a';if(p.next[j] == null){p.next[j] = new Node();}p = p.next[j];}p.num++;if(p.num > number){number = p.num;animal = s;//System.out.println(animal); }}public int getnum(){return number;}public char[] getanimal(){//System.out.println(animal);return animal;} } class Node{public int num;public Node[] next = new Node[30];public Node(){for(int i = 0; i < 30; i++){next[i] = null;}num = 0;} }

?

人之初，性本善。性相近，習(xí)相遠(yuǎn)。

茍不教，性乃遷。教之道，貴以專。 昔孟母，擇鄰處。子不學(xué)，斷機(jī)杼。 竇燕山，有義方。教五子，名俱揚(yáng)。 養(yǎng)不教，父之過。教不嚴(yán)，師之惰。 子不學(xué)，非所宜。幼不學(xué)，老何為。 玉不琢，不成器。人不學(xué)，不知義。 為人子，方少時。親師友，習(xí)禮儀。 香九齡，能溫席。孝于親，所當(dāng)執(zhí)。 融四歲，能讓梨。弟于長，宜先知。 首孝悌，次見聞。知某數(shù)，識某文。 一而十，十而百。百而千，千而萬。 三才者，天地人。三光者，日月星。 三綱者，君臣義。父子親，夫婦順。 曰春夏，曰秋冬。此四時，運(yùn)不窮。 曰南北，曰西東。此四方，應(yīng)乎中。 曰水火，木金土。此五行，本乎數(shù)。 曰仁義，禮智信。此五常，不容紊。 稻粱菽，麥?zhǔn)蝠ⅰ４肆?#xff0c;人所食。 馬牛羊，雞犬豕。此六畜，人所飼。 曰喜怒，曰哀懼。愛惡欲，七情具。 青赤黃，及黑白。此五色，目所識。 酸苦甘，及辛咸。此五味，口所含。 膻焦香，及腥朽。此五臭，鼻所嗅。 匏土革，木石金。絲與竹，乃八音。 曰平上，曰去入。此四聲，宜調(diào)協(xié)。 高曾祖，父而身。身而子，子而孫。 自子孫，至玄曾。乃九族，人之倫。 父子恩，夫婦從。兄則友，弟則恭。 長幼序，友與朋。君則敬，臣則忠。 此十義，人所同。當(dāng)師敘，勿違背。 斬齊衰，大小功。至緦麻，五服終。 禮樂射，御書數(shù)。古六藝，今不具。 惟書學(xué)，人共遵。既識字，講說文。 有古文，大小篆。隸草繼，不可亂。 若廣學(xué)，懼其繁。但略說，能知原。 凡訓(xùn)蒙，須講究。詳訓(xùn)詁，明句讀。 為學(xué)者，必有初。小學(xué)終，至四書。 論語者，二十篇。群弟子，記善言。 孟子者，七篇止。講道德，說仁義。 作中庸，子思筆。中不偏，庸不易。 作大學(xué)，乃曾子。自修齊，至平治。 孝經(jīng)通，四書熟。如六經(jīng)，始可讀。 詩書易，禮春秋。號六經(jīng)，當(dāng)講求。 有連山，有歸藏。有周易，三易詳。 有典謨，有訓(xùn)誥。有誓命，書之奧。 我周公，作周禮。著六官，存治體。 大小戴，注禮記。述圣言，禮樂備。 曰國風(fēng)，曰雅頌。號四詩，當(dāng)諷詠。 詩既亡，春秋作。寓褒貶，別善惡。 三傳者，有公羊。有左氏，有谷梁。 經(jīng)既明，方讀子。撮其要，記其事。 五子者，有荀揚(yáng)。文中子，及老莊。 經(jīng)子通，讀諸史。考世系，知始終。 自羲農(nóng)，至黃帝。號三皇，居上世。 唐有虞，號二帝。相揖遜，稱盛世。 夏有禹，商有湯。周武王，稱三王。 夏傳子，家天下。四百載，遷夏社。 湯伐夏，國號商。六百載，至紂亡。 周武王，始誅紂。八百載，最長久。 周轍東，王綱墜。逞干戈，尚游說。 始春秋，終戰(zhàn)國。五霸強(qiáng)，七雄出。 嬴秦氏，始兼并。傳二世，楚漢爭。 高祖興，漢業(yè)建。至孝平，王莽篡。 光武興，為東漢。四百年，終于獻(xiàn)。 魏蜀吳，爭漢鼎。號三國，迄兩晉。 宋齊繼，梁陳承。為南朝，都金陵。 北元魏，分東西。宇文周，與高齊。 迨至隋，一土宇。不再傳，失統(tǒng)緒。 唐高祖，起義師。除隋亂，創(chuàng)國基。 二十傳，三百載。梁滅之，國乃改。 梁唐晉，及漢周。稱五代，皆有由。 炎宋興，受周禪。十八傳，南北混。 遼與金，皆稱帝。元滅金，絕宋世。 輿圖廣，超前代。九十年，國祚廢。 太祖興，國大明。號洪武，都金陵。 迨成祖，遷燕京。十六世，至崇禎。 權(quán)閹肆，寇如林。李闖出，神器焚。 清世祖，膺景命。靖四方，克大定。 由康雍，歷乾嘉。民安富，治績夸。 道咸間，變亂起。始英法，擾都鄙。 同光后，宣統(tǒng)弱。傳九帝，滿清歿。 革命興，廢帝制。立憲法，建民國。 古今史，全在茲。載治亂，知興衰。 史雖繁，讀有次。史記一，漢書二。 后漢三，國志四。兼證經(jīng)，參通鑒。 讀史者，考實錄。通古今，若親目。 昔仲尼，師項橐。古圣賢，尚勤學(xué)。 趙中令，讀魯論。彼既仕，學(xué)且勤。 披蒲編，削竹簡。彼無書，且知勉。 頭懸梁，錐刺股。彼不教，自勤苦。 如囊螢，如映雪。家雖貧，學(xué)不輟。 如負(fù)薪，如掛角。身雖勞，猶苦卓。 蘇老泉，二十七。始發(fā)憤，讀書籍。 彼既老，猶悔遲。爾小生，宜早思。 若梁灝，八十二。對大廷，魁多士。 彼既成，眾稱異。爾小生，宜立志。 瑩八歲，能詠詩。泌七歲，能賦棋。 彼穎悟，人稱奇。爾幼學(xué)，當(dāng)效之。 蔡文姬，能辯琴。謝道韞，能詠吟。 彼女子，且聰敏。爾男子，當(dāng)自警。 唐劉晏，方七歲。舉神童，作正字。 口而誦，心而惟。朝于斯，夕于斯。 晏雖幼，身已仕。有為者，亦若是。 犬守夜，雞司晨。茍不學(xué)，曷為人。 蠶吐絲，蜂釀蜜。人不學(xué)，不如物。 幼而學(xué)，壯而行。上致君，下澤民。 揚(yáng)名聲，顯父母。光于前，裕于后。 人遺子，金滿贏。我教子，唯一經(jīng)。 勤有功，戲無益。戒之哉，宜勉力。

總結(jié)

以上是生活随笔為你收集整理的动物统计加强版（贪心，字典序）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。