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][30],val[MAXN];
char dt[MAXN][12];
int sz;
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]++;
}
val[k]=1;
}
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;
char ans[12];
int i,j;
sz=0;
SI(N);
F(i,N){
scanf("%s",dt[i]);
join(dt[i]);
}int ms=0;
F(i,N){
int temp=find(dt[i]);
if(temp>ms){
ms=temp;
strcpy(ans,dt[i]);
}
}
printf("%s %d\n",ans,ms);
return 0;
}
大神的链表字典序ac；
#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;
}
原文：http://www.cnblogs.com/handsomecui/p/5002632.html