Poj1451

题目大意：给你一个手机字典，让你根据用户的输入键号对应找到输入次数最多的那一个单词并输出。

算法思想：字典树的应用，仙剑好字典树，再便利用户的输入，运用递归找到最优数组，并输出，

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int t,m,w,k,MAX;
char c[12][5]={{"\0"},{"\0"},{"abc"},{"def"},{"ghi"},{"jkl"},{"mno"},{"pqrs"},{"tuv"},{"wxyz"}};
char str[105],str2[105];
char tmp[105],ans[105];
typedef struct Trie
{
    Trie *next[105];
    int num;
};

void add_tree(int w,Trie *root)
{
    Trie *p=root;
    for(int i=0;i<strlen(str);i++)
    {
        int id=str[i]-'a';
        if(p->next[id]==NULL)
        {
            p->next[id]=new Trie();
        }
        p=p->next[id];
        p->num+=w;
    }
}
void find_res(int x,int pos,Trie *root)
{
    Trie *p=root;
    int d=str2[pos]-'0';
    for(int i=0;i<strlen(c[d]);i++)
    {
        int id=c[d][i]-'a';
        if(p->next[id]==NULL)
            continue;
        else
            tmp[pos]=id+'a';
        if(pos==x)
        {
            if(MAX<p->next[id]->num)
            {
                MAX=p->next[id]->num;
                strcpy(ans,tmp);
            }
        }
        else
            find_res(x,pos+1,p->next[id]);

    }
}
int main()
{
    Trie *root;
    scanf("%d",&t);
    int sym=0;
    while(t--)
    {
        sym++;
        memset(ans,0,sizeof(ans));
        root=new Trie();
        scanf("%d",&m);
        for(int i=1;i<=m;i++)
        {
            scanf("%s%d",str,&w);
            add_tree(w,root);
        }
        scanf("%d",&k);
       bool flag=false;
        while(k--)
        {
            scanf("%s",str2);
            if(!flag)
            {
                 printf("Scenario #%d:\n",sym);
                 flag=true;
            }

           for(int i=0;i<strlen(str2)-1;i++)
           {
               MAX=-1;
               memset(tmp,0,sizeof(tmp));
               find_res(i,0,root);
               if(MAX!=-1)
                    printf("%s\n",ans);
               else
                    printf("MANUALLY\n");
           }
           printf("\n");

        }
        printf("\n");
    }


    return 0;
}