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

我的第555题,纪念一下!

Posted by dreamone at 2009-11-24 22:31:08 on Problem 2408 and last updated at 2009-11-24 22:32:04
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator