卢俊达

题目大意：

模拟手机T9输入法。先给出n个单词和其出现概率，根据用户按下的数字键，选择相应概率最大的单词输出。

思路：

首先根据给出的单词建树，然后根据按下的数字进行广搜。

代码：

#include<iostream>
#include<stdio.h>
#include<queue>
using namespace std;
struct trie
//利用结构体来封装字典树的节点。
{
	trie* next[26];
	trie* pre;
	//指针指向父节点，用于回溯输出单词。 
	int total;
	//total用于记录概率。 
	char letter;
	trie()
	//构造函数。 
	{
		for(int i=0;i<26;i++)
			next[i]=NULL;
		pre=NULL;
		total=0;
		letter='\0';
	}
};
void insert(char* s,int n,trie* root)
//将字符串s所表示的单词插入到字典树中。 
{
	trie *p=root;
	for(int i=0;s[i]!='\0';i++)
	{
		if(p->next[s[i]-'a']==NULL)
		{
			p->next[s[i]-'a']=new trie;
			p->next[s[i]-'a']->pre=p;
			p->next[s[i]-'a']->letter=s[i];
		}
		p=p->next[s[i]-'a'];
		p->total+=n;
	}
}
void output(trie* point)
//从point开始回溯至root，输出途径节点的字母，达到输出单词的目的。 
{
	if(point->pre->pre!=NULL)
		output(point->pre);
	printf("%c",point->letter);
}
char T9[10][5]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
void bfs(char* num,trie* root)
//根据按键广搜 
{
	queue<trie*> q;
	q.push(root);
	for(int i=0;num[i]!='1';i++)
	{
		int size=q.size(),max=0;
		//max记录最大概率。 
		trie* now=NULL;
		//now指向表示概率最大的词的最后一个字母的节点。 
		while(size--)
		{
			trie *head=q.front();
			q.pop();
			for(int j=0;j<strlen(T9[num[i]-'0']);j++)
			//遍历num[i]所表示的几个字母。 
			{
				trie *temp=head->next[T9[num[i]-'0'][j]-'a'];
				if(temp!=NULL)
				//若树中存在此单词 
				{
					if(temp->total>max)
					{
						max=temp->total;
						now=temp;
					}
					q.push(temp);
				}
			}
		}
		if(now==NULL)
		//now==NULL说明没有单词对应现在的按键序列 
			printf("MANUALLY");
		else
			output(now);
		printf("\n");
	}
	printf("\n");
}
int main()
{
	int t;
	scanf("%d",&t);
	for(int i=1;i<=t;i++)
	{
		printf("Scenario #%d:\n",i);
		trie root;
		//字典树的根节点。 
		int w,m;
		for(scanf("%d",&w);w>0;w--)
		{
			char str[101];
			int p;
			scanf("%s%d",str,&p);
			insert(str,p,&root);
		}
		for(scanf("%d",&m);m>0;m--) 
		{
			char num[101];
			scanf("%s",num);
			bfs(num,&root);
			//对每个按键序列进行广搜。 
		}
		printf("\n");
	}
}