动物统计加强版（贪心，字典序）

动物统计加强版

时间限制：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，字典树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还没开够应该开到MAXN*12，数据量太大了 //肯定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; }

　　

自己写了一发链表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);//不加也可以为了优化内存，加了反而时间长一些； 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返回数组出现了一些问题，

链接会造成返回的数组结果是地址，出错，不连接就可以输出数组内容

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());//链接会造成返回的数组结果是地址，出错，不连接就可以输出数组内容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;} }

 

人之初，性本善。性相近，习相远。

苟不教，性乃迁。教之道，贵以专。 昔孟母，择邻处。子不学，断机杼。 窦燕山，有义方。教五子，名俱扬。 养不教，父之过。教不严，师之惰。 子不学，非所宜。幼不学，老何为。 玉不琢，不成器。人不学，不知义。 为人子，方少时。亲师友，习礼仪。 香九龄，能温席。孝于亲，所当执。 融四岁，能让梨。弟于长，宜先知。 首孝悌，次见闻。知某数，识某文。 一而十，十而百。百而千，千而万。 三才者，天地人。三光者，日月星。 三纲者，君臣义。父子亲，夫妇顺。 曰春夏，曰秋冬。此四时，运不穷。 曰南北，曰西东。此四方，应乎中。 曰水火，木金土。此五行，本乎数。 曰仁义，礼智信。此五常，不容紊。 稻粱菽，麦黍稷。此六谷，人所食。 马牛羊，鸡犬豕。此六畜，人所饲。 曰喜怒，曰哀惧。爱恶欲，七情具。 青赤黄，及黑白。此五色，目所识。 酸苦甘，及辛咸。此五味，口所含。 膻焦香，及腥朽。此五臭，鼻所嗅。 匏土革，木石金。丝与竹，乃八音。 曰平上，曰去入。此四声，宜调协。 高曾祖，父而身。身而子，子而孙。 自子孙，至玄曾。乃九族，人之伦。 父子恩，夫妇从。兄则友，弟则恭。 长幼序，友与朋。君则敬，臣则忠。 此十义，人所同。当师叙，勿违背。 斩齐衰，大小功。至缌麻，五服终。 礼乐射，御书数。古六艺，今不具。 惟书学，人共遵。既识字，讲说文。 有古文，大小篆。隶草继，不可乱。 若广学，惧其繁。但略说，能知原。 凡训蒙，须讲究。详训诂，明句读。 为学者，必有初。小学终，至四书。 论语者，二十篇。群弟子，记善言。 孟子者，七篇止。讲道德，说仁义。 作中庸，子思笔。中不偏，庸不易。 作大学，乃曾子。自修齐，至平治。 孝经通，四书熟。如六经，始可读。 诗书易，礼春秋。号六经，当讲求。 有连山，有归藏。有周易，三易详。 有典谟，有训诰。有誓命，书之奥。 我周公，作周礼。著六官，存治体。 大小戴，注礼记。述圣言，礼乐备。 曰国风，曰雅颂。号四诗，当讽咏。 诗既亡，春秋作。寓褒贬，别善恶。 三传者，有公羊。有左氏，有谷梁。 经既明，方读子。撮其要，记其事。 五子者，有荀扬。文中子，及老庄。 经子通，读诸史。考世系，知始终。 自羲农，至黄帝。号三皇，居上世。 唐有虞，号二帝。相揖逊，称盛世。 夏有禹，商有汤。周武王，称三王。 夏传子，家天下。四百载，迁夏社。 汤伐夏，国号商。六百载，至纣亡。 周武王，始诛纣。八百载，最长久。 周辙东，王纲坠。逞干戈，尚游说。 始春秋，终战国。五霸强，七雄出。 嬴秦氏，始兼并。传二世，楚汉争。 高祖兴，汉业建。至孝平，王莽篡。 光武兴，为东汉。四百年，终于献。 魏蜀吴，争汉鼎。号三国，迄两晋。 宋齐继，梁陈承。为南朝，都金陵。 北元魏，分东西。宇文周，与高齐。 迨至隋，一土宇。不再传，失统绪。 唐高祖，起义师。除隋乱，创国基。 二十传，三百载。梁灭之，国乃改。 梁唐晋，及汉周。称五代，皆有由。 炎宋兴，受周禅。十八传，南北混。 辽与金，皆称帝。元灭金，绝宋世。 舆图广，超前代。九十年，国祚废。 太祖兴，国大明。号洪武，都金陵。 迨成祖，迁燕京。十六世，至崇祯。 权阉肆，寇如林。李闯出，神器焚。 清世祖，膺景命。靖四方，克大定。 由康雍，历乾嘉。民安富，治绩夸。 道咸间，变乱起。始英法，扰都鄙。 同光后，宣统弱。传九帝，满清殁。 革命兴，废帝制。立宪法，建民国。 古今史，全在兹。载治乱，知兴衰。 史虽繁，读有次。史记一，汉书二。 后汉三，国志四。兼证经，参通鉴。 读史者，考实录。通古今，若亲目。 昔仲尼，师项橐。古圣贤，尚勤学。 赵中令，读鲁论。彼既仕，学且勤。 披蒲编，削竹简。彼无书，且知勉。 头悬梁，锥刺股。彼不教，自勤苦。 如囊萤，如映雪。家虽贫，学不辍。 如负薪，如挂角。身虽劳，犹苦卓。 苏老泉，二十七。始发愤，读书籍。 彼既老，犹悔迟。尔小生，宜早思。 若梁灏，八十二。对大廷，魁多士。 彼既成，众称异。尔小生，宜立志。 莹八岁，能咏诗。泌七岁，能赋棋。 彼颖悟，人称奇。尔幼学，当效之。 蔡文姬，能辩琴。谢道韫，能咏吟。 彼女子，且聪敏。尔男子，当自警。 唐刘晏，方七岁。举神童，作正字。 口而诵，心而惟。朝于斯，夕于斯。 晏虽幼，身已仕。有为者，亦若是。 犬守夜，鸡司晨。苟不学，曷为人。 蚕吐丝，蜂酿蜜。人不学，不如物。 幼而学，壮而行。上致君，下泽民。 扬名声，显父母。光于前，裕于后。 人遗子，金满赢。我教子，唯一经。 勤有功，戏无益。戒之哉，宜勉力。

总结

以上是生活随笔为你收集整理的动物统计加强版（贪心，字典序）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。