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

AC用字典树做的,不过效果不太好1325MS

Posted by 1401826426 at 2014-07-18 19:28:41 on Problem 1002
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
#define max 100005
struct node
{
	int v;
	int temp;
	struct node*next[10];
};
struct node*newnode()
{
	struct node*r;
	r=new struct node;
	r->v=r->temp=0;
	int i;
	for(i=0;i<10;i++)
	r->next[i]=NULL;
	return r;
}
int insert(struct node*root,string str)
{
	int i;
	struct node *r,*s;
	r=root;
	int flag=0;
    for(i=0;i<str.length();i++)
	{
		if(str[i]=='-')continue;
		if(r->next[str[i]-'0']==NULL)
		{
			s=newnode();
			s->v=1;
			r->next[str[i]-'0']=s;
			r=s;
		}
		else
		{
			r=r->next[str[i]-'0'];
			r->v++;
			flag++;
		}
	}
	r->temp=1;
    if(flag==7)return 1;
	return 0;
}
int search(struct node*root,string str)
{
	struct node*r;
	r=root;
	int i;
	for(i=0;i<str.length();i++)
	{
		if(str[i]=='-')continue;
		r=r->next[str[i]-'0'];
	}
	return r->v;
}
struct ca
{
     char str[100];
	int sum;
}s[max];
int cmp(struct ca a,struct ca b)
{
	if(strcmp(a.str,b.str)==-1)
		return 1;
	return 0;
}
char match[26]={"222333444555666777888999"};
int main()
{
	int n;
	cin>>n;
	struct node*root;
	root=newnode();
	int i=0;
	while(n--)
	{
		char temp[100];
		scanf("%s",temp);
		int L=strlen(temp);
		int k=0;
		int j;
        for(j=0;j<L;j++)
		{
			if(temp[j]=='Z'||temp[j]=='Q'||temp[j]=='-')
				continue;
			else if(temp[j]<'Q'&&temp[j]>='A')
				s[i].str[k]=match[(temp[j]-'A')];
			else if(temp[j]>'Q'&&temp[j]<='Z')
				s[i].str[k]=match[temp[j]-'A'-1];
			else
				s[i].str[k]=temp[j];
			k++;
			if(k==3)
			{s[i].str[k]='-';k++;}
		}
		s[i].str[k]='\0';k++;
		if(!insert(root,s[i].str)){i++;}
	}
	sort(s,s+i,cmp);
	int tag=0;int j;
	for(j=0;j<i;j++)
	{
		int t=search(root,s[j].str);
		if(t>=2)
        {
			tag=1;
		  printf("%s %d\n",s[j].str,t);
		}
	}
	if(!tag)printf("No duplicates.\n");
	return 0;
}




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