HDU-1298-T9

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

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

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

例如    ab  2

            bc  3

            23

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

#include
    
     #include
     
      #include
      
       #include
       
        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
        
         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
         
          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
          
           0) printf("%s\n",find); else printf("MANUALLY\n"); } printf("\n"); } printf("\n"); } return 0;}