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

数据测试没问题,就是WA,用Trie树写的,高手帮着看下,谢谢!!

Posted by songxiangwu at 2011-04-21 16:42:23 on Problem 1002
#include<iostream>
#include<string>
using namespace std;
struct Node
{
	Node *next[10];
	bool isstring;
	int times;
	Node()
	{
		memset(next,NULL,sizeof(next));
		times=0;
		isstring=false;
	}
};
class Trie
{
private:
	Node *root;
public:
	Trie()
	{
		root=new Node();
	}
	~Trie()
	{
		deleteTree(root);
	}
	void Insert(const char *word)
	{
		Node * location=root;
		while(*word!=NULL)
		{
			if(location->next[*word-'0']==NULL)
			{
				Node *temp=new Node();
				location->next[*word-'0']=temp;
			}
			location=location->next[*word-'0'];
			word++;
		}
		location->isstring=true;
		location->times++;
	}
	bool search(char *word)
	{
		Node *location=root;
		while(*word!=NULL&&location)
		{
			location=location->next[*word-'0'];
			word++;
		}
		return (location!=NULL&&location->isstring);
	}
	void deleteTree(Node *root)
	{
		for(int i=0;i!=10;i++)
		{
			if(root->next[i]!=NULL)
			{
				deleteTree(root->next[i]);
			}
		}
		delete root;
	}
	int timescount(char *word)
	{
		Node *location=root;
		while(*word!=NULL&&location)
		{
			location=location->next[*word-'0'];
			word++;
		}
		return location->times;
	}
};
char ans[100001][10];
int main()
{
	int t,i,j,key;
	cin>>t;
	string s;
	char temp[10];
	Trie tree;
	int index=0;
	int tempt=t;
	while(t--)
	{
		key=0;
		cin>>s;
		for(i=0;i!=s.size();i++)
		{
			if(s[i]!='-')
			{
				if(s[i]>='0'&&s[i]<='9')
					temp[key]=s[i];
				else if(s[i]=='A'||s[i]=='B'||s[i]=='C')
					temp[key]='2';
				else if(s[i]=='D'||s[i]=='E'||s[i]=='F')
					temp[key]='3';
				else if(s[i]=='G'||s[i]=='H'||s[i]=='I')
					temp[key]='4';
				else if(s[i]=='J'||s[i]=='K'||s[i]=='L')
					temp[key]='5';
				else if(s[i]=='M'||s[i]=='N'||s[i]=='O')
					temp[key]='6';
				else if(s[i]=='P'||s[i]=='R'||s[i]=='S')
					temp[key]='7';
				else if(s[i]=='T'||s[i]=='U'||s[i]=='V')
					temp[key]='8';
				else if(s[i]=='W'||s[i]=='X'||s[i]=='Y')
					temp[key]='9';
				key++;
			}
		}
		temp[key]='\0';
		tree.Insert(temp);
		strcpy(ans[index],temp);
		index++;
	}
	for(i=0;i!=tempt-1;i++)
	{
		key=i;
		for(j=i+1;j!=tempt;j++)
		{
			if(strcmp(ans[j],ans[key])<0)
				key=j;
		}
		if(key!=i)
		{
			char temp0[10];
			strcpy(temp0,ans[key]);
			strcpy(ans[key],ans[i]);
			strcpy(ans[i],temp0);
		}
	}
	char temp6[10]={'*','*','*','*','*','*','*','*','*','\0'};
	int key1=0;
	for(i=0;i!=tempt;i++)
	{
		int key5=0;
		if(tree.search(ans[i]))
		{
			if(strcmp(ans[i],temp6)!=0&&tree.timescount(ans[i])>1)
			{
				cout<<ans[i][0]<<ans[i][1]<<ans[i][2]<<"-"<<ans[i][3]<<ans[i][4]<<ans[i][5]<<ans[i][6]<<ans[i][7]<<" "<<tree.timescount(ans[i])<<endl;
				key1++;
			}
			strcpy(temp6,ans[i]);
		}
	}
	if(key1==0)
	{
		cout<<"No duplicates."<<endl;
	}
	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