1298 t9.cpp

威士忌的HDU题解.大概有260多题的源码。对于学习非常有好处。

#include <cstdio>
#include <string>
using namespace std;

struct trie
{
	trie * next[8];
	char word[101];
	int p;
};
trie *thead;

struct WORD
{
 char str[101];
 int p;
}dic[1001];

char buff[101];
int mapping[26]  = {0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4,
     5, 5, 5, 5, 6, 6, 6, 7, 7, 7, 7},w,m;
     
inline trie * newnode()
{
	int i;
	
	trie *t;
	t=(trie*)malloc(sizeof(trie));
	memset(t,0,sizeof(trie));
	return t;
}
void insert(trie * s,char x[],int pri,int pos)
{
	int i,j,k,next,p;
	
	for(i=0; x[i] ; i++)
	{
		next=mapping[ x[i]-'a' ];
		if(!s->next[ next ])
		{
			s->next[ next ]=newnode();
			s= s->next[ next ];
			strncpy(s->word, x, i + 1);
			s->word[i+1]=0;
			p=pri;
			for(j=pos+1; j<w && strncmp(x,dic[j].str, i+1)==0 ; j++)
				p+=dic[j].p;
			s->p=p;
		}
		else
		{
			s=s->next[ next ];
			if(strncmp(s->word,x,i+1)!=0)
			{
				p=pri;
				for(j=pos+1; j<w && strncmp(x,dic[j].str, i+1)==0 ; j++)
					p+=dic[j].p;
				if(p > s->p)
				{
					strncpy(s->word, x, i + 1);
					s->p=p;
				}
			}
		}//if
	}//for
}
void deltrie(trie * s)
{
	int i;
	
	for(i=0;i<8;i++)
   	{
		if( s->next[i] ) 
			deltrie(s->next[i]);
	}
	if(s!=thead)
	{
		free(s);
		s=NULL;
	}
	else
		for(i=0;i<8;i++)
			s->next[i]=NULL;
}
void find(trie *s,char x[])
{
	int i,code;
	
	if(x[0]==0)
		return ;
	for(i=0; x[i]>'1' ; i++)
	{
		code=x[i]-'0'-2;
		s=s->next[code];
		if(!s)
		{
			while(x[i++] != '1') 
				printf("MANUALLY\n");
			return;
		}
		printf("%s\n",s->word);
	}
}

int main()
{
	int i,j,k,n,t,p;
	
	thead=newnode();
	scanf("%d",&t);
	for(k=1;k<=t;k++)
	{
		scanf("%d",&w);
		for(i=0;i<w;i++)
			scanf("%s %d",dic[i].str,&dic[i].p);
		for(i=0;i<w;i++)
			insert(thead,dic[i].str,dic[i].p,i);
		
		printf("Scenario #%d:\n", k);
		scanf("%d",&m);
		while(m--)
		{
			scanf("%s",buff);
			find(thead,buff);
			printf("\n");
		}
		printf("\n");
		deltrie(thead);
	}
	
	return 0;
}