| ||||||||||
| 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 | |||||||||
Re:我的第555题,纪念一下!In Reply To:我的第555题,纪念一下! Posted by:dreamone at 2009-11-24 22:31:08 > #include<iostream>
> #include<algorithm>
> #include<string>
> #include<vector>
> using namespace std;
>
> struct node
> {
> bool flag;
> int size;
> node *next[26];
> node()
> {
> flag=0;
> for(int i=0;i<26;i++)
> next[i]=NULL;
> };
> }root;
> vector<string>pp[30001];
> string aa,buff;
> int N;
> int ID;
> int my[30001];
> struct AA
> {
> int sz;
> int id;
> };
> AA num[30001];
>
> int minn(int a,int b)
> {
> return a<b?a:b;
> }
> bool cmp(AA a,AA b)
> {
> if(a.sz>b.sz)
> return 1;
> else if(a.sz<b.sz)
> return 0;
> else
> {
> int i,j;
> i=0;j=0;
> sort(pp[a.id].begin(),pp[a.id].begin());
> sort(pp[b.id].begin(),pp[b.id].begin());
> while(i<pp[a.id].size()&&j<pp[b.id].size())
> {
> if(pp[a.id][i]<pp[b.id][i])
> return 1;
> else if(pp[a.id][i]>pp[b.id][i])
> return 0;
> i++;j++;
> }
> }
> return 0;
> }
> void dell(string buff,string aa)
> {
> int i,len;
> node *cur=&root;
> len=buff.size();
> for(i=0;i<len;i++)
> {
> if(cur->next[buff[i]-'a']==NULL)
> cur->next[buff[i]-'a']=new node();
> cur=cur->next[buff[i]-'a'];
> }
> if(!cur->flag)
> {
> cur->flag=1;
> cur->size=++ID;
> pp[ID].push_back(aa);
> num[N].sz++;
> num[N].id=ID;
> my[cur->size]=N;
> N++;
> }
> else
> {
> pp[cur->size].push_back(aa);
> num[my[cur->size]].sz++;
> num[my[cur->size]].id=cur->size;
> }
> }
> int main()
> {
> N=0;
> ID=0;
> int i,j;
> for(i=0;i<30001;i++)
> pp[i].clear();
> memset(num,0,sizeof(num));
> memset(my,-1,sizeof(my));
> while(cin>>buff)
> {
> // if(buff=="-1")
> // break;
> aa=buff;
> sort(buff.begin(),buff.end());
> dell(buff,aa);
> }
> sort(num,num+N,cmp);
> for(i=0;i<minn(N,5);i++)
> {
> printf("Group of size %d:",num[i].sz);
> sort(pp[num[i].id].begin(),pp[num[i].id].end());
> cout<<' '<<pp[num[i].id][0];
> for(j=1;j<pp[num[i].id].size();j++)
> {
> if(pp[num[i].id][j]!=pp[num[i].id][j-1])
> cout<<' '<<pp[num[i].id][j];
> }
> printf(" .\n");
> }
> return 0;
> }
>
> /*
> abc
> acb
> bca
> cab
> cba
> cd
> dc
> ab
> ab
> ba
> */
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator