HDU-1298-T9

HDU-1298-T9

http://acm.hdu.edu.cn/showproblem.php?pid=1298

很好的一题，字典树+DFS，思路参考swm8023大牛的

题意是模拟手机输入法，给出几个单词即频度，再给出几个数字串，确定对于给定的一个数字串，每输入一个数字，将显示什么字符

本题的数字串的每一个数字均代表一个字母，而不是平常的手机，多个数字可能代表一个字母，首先可将给出的单词即频度记录到字典树中，对于数字串进行DFS，查找其可能表示的频度最大的字符串

例如 ab 2

bc 3

23

23代表的字符串可能是ad,ae,af,bd,be,bf,cd,ce,cf，逐个搜索，找出频度最大的

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
struct node
{
	int count;
	node *childs[26];
	node()
	{
		count=0;
		for(int i=0;i<26;i++)
		childs[i]=NULL;
	}
};
node *root;
node *current,*newnode;
int p;
char s1[105],s2[105],find[105],ans[105];
char phone[8][4]={{0,1,2},{3,4,5},{6,7,8},{9,10,11},{12,13,14},{15,16,17,18},{19,20,21},{22,23,24,25}};
int  num[8]={3,3,3,3,3,4,3,4};
void insert(char *str,int k) //插入字符串和它的频度
{
	int i,m;
	current=root;
	for(i=0;i<strlen(str);i++)
	{
		m=str[i]-'a';
		if(current->childs[m]!=NULL)
		{
			current=current->childs[m];
			(current->count)+=k;
		}
		else
		{
			newnode=new node;
			(newnode->count)+=k;
			current->childs[m]=newnode;
			current=newnode;
		}
	}
}
void dfs(int cur,int len,node *nd)
{
    if(cur==len)
	{
		if(nd->count>p)   //找频度最大的
		{
			p=nd->count;
            for(int i=0;i<len;i++)
			find[i]=ans[i];
			find[len]='\0';
		}
	    return;
	}
    int t=s2[cur]-'2';
    for(int i=0;i<num[t];i++)
	{
		int r=phone[t][i];
		if(nd->childs[r]==NULL)
		continue;
		ans[cur]='a'+r;
        dfs(cur+1,len,nd->childs[r]);
	}
	return;
}
int main()
{
	int i,n,m,t,k,cnt,len;
	scanf("%d",&t);
	for(k=1;k<=t;k++)
	{
		printf("Scenario #%d:\n",k);
		scanf("%d",&n);
		root=new node;
		while(n--)
		{
			scanf("%s %d",s1,&cnt);
			insert(s1,cnt);
		}
		scanf("%d",&m);
		while(m--)
		{
			scanf("%s",s2);
			len=strlen(s2);
			for(i=1;i<len;i++)
			{
				p=0;  //记录字符出现的频度
				dfs(0,i,root);
				if(p>0)
				printf("%s\n",find);
				else
				printf("MANUALLY\n");
			}
			printf("\n");
		}
		printf("\n");
	}
	return 0;
}