Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 。。MLE了N次后79MS飘过

Posted by dahailixuxu at 2013-04-18 17:32:24 on Problem 2408
```#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int gcnt=0,L=0,N=0;
char s[30005][30],tmp[30];

struct GROUP
{
int cnt,cur;
char **p;
}*group[30005];

struct Trie
{
int id;
Trie *p[27];
}*root,pool[1000000];

int idx(char c)
{
return c-'a';
}

int search(char *s)
{
Trie *p=root;
for(int i=0;s[i]!=0;i++)
{
int c=idx(s[i]);
if(!p->p[c])
return -1;
p=p->p[c];
}
return p->id;
}

int insert(char *s)
{
Trie *p=root;
for(int i=0;s[i]!=0;i++)
{
int c=idx(s[i]);
if(!p->p[c])
{
Trie *q=&pool[L++];
q->id=-1;
p->p[c]=q;
}
p=p->p[c];
}
group[gcnt]=new GROUP;
group[gcnt]->cnt=0;
group[gcnt]->cur=0;
return p->id=gcnt++;
}

bool cmp1(char a,char b)
{
return a<b;
}

bool cmp2(char *a,char *b)
{
if(strcmp(a,b)<0)
return 1;
else
return 0;
}

bool cmp3(GROUP *a,GROUP *b)
{
if(a->cnt==b->cnt)
return cmp2(a->p[0],b->p[0]);
return a->cnt>b->cnt;
}

int main()
{
root=&pool[L++];
root->id=-1;
while(~scanf("%s",s[++N]))
{
strcpy(tmp,s[N]);
int len=strlen(tmp);
sort(tmp,tmp+len,cmp1);
int id=search(tmp);
if(id==-1)
id=insert(tmp);
group[id]->cnt++;
}
N--;
for(int i=0;i<gcnt;i++)
group[i]->p=new char*[group[i]->cnt];
for(int i=1;i<=N;i++)
{
strcpy(tmp,s[i]);
int len=strlen(tmp);
sort(tmp,tmp+len,cmp1);
int id=search(tmp);
int t=0;
for(;t<group[id]->cur;t++)
{
if(strcmp(s[i],group[id]->p[t])==0)
break;
}
if(t==group[id]->cur)
{
group[id]->p[t]=new char[30];
strcpy(group[id]->p[t],s[i]);
group[id]->cur++;
}
}
for(int i=0;i<gcnt;i++)
sort(group[i]->p,group[i]->p+group[i]->cur,cmp2);
sort(group,group+gcnt,cmp3);
for(int i=0,flag=0;i<gcnt && flag<5;i++)
{
printf("Group of size %d: ",group[i]->cnt);
for(int j=0;j<group[i]->cur;j++)
printf("%s ",group[i]->p[j]);
printf(".\n");
flag++;
}
return 0;
}
```

Followed by: