Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
。。MLE了N次后79MS飘过#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: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator