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

HDU能过,POJ跪了。求大牛指点数据。。附代码。

Posted by 516032337 at 2012-07-27 15:01:14 on Problem 3630
#include<iostream>
#include<string>
using namespace std;
const int MAX = 1<<16;
int up;
struct Node 
{
	int c[11]; 
	bool isword;
	Node() 
	{	
		up++;
		isword = false;
		memset(c, 0, sizeof(c));
	}
}trie[MAX];    
struct Str
{
	char s[15];
	int l;	
}str[MAX];
void trieBuild() 
{	
	up = 0;
	trie[0] = Node();
}
bool trieAdd(char  s[]) 
{
	bool flag=true;
	int i, now = 0;
	for(i = 0; s[i]; ++i) 
	{
		int p = s[i]-'0';
		if(trie[now].c[p] == 0) 
		{
			trie[now].c[p] = up;
			trie[up] = Node();
		}
		now = trie[now].c[p];
		if(trie[now].isword==true) flag=false;
	}
	trie[now].isword = true;
	return flag;
}
int cmp(const void* a,const void* b)
{
	Str *c=(Str *)a;Str *d=(Str *)b;
	return c->l>d->l;
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		int n;
		scanf("%d",&n);
		char s[15];
		trieBuild();		
		for(int i=0;i<n;++i) 
		{
			scanf("%s",str[i].s);
			str[i].l=strlen(str[i].s);
		}
		qsort(str,n,sizeof(str[0]),cmp);
		bool flag=true;
		for(int i=0;i<n;++i)
		{
			if(false==trieAdd(str[i].s)) {flag=false;break;}
		}
		if(flag) printf("YES\n");
		else printf("NO\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