题意：T9输入法，要求根据给出的字典，对给定的数字顺序，选择具有最高频率的词前缀。
解法：经典的字典树问题。根据字典词，建立字典树(Trie树），节点保存其权值(频率），对给定的数字进行搜索(DFS)，确定最大值。
具有相同最大值是，输出字典序靠前前缀。
源代码
1
#include<iostream>
2#include<stack>
3//#include<fstream>
4
5using namespace std;
6
7//字典树节点
8struct Node
9
{
10
int p; //频率
11 int lev; //节点处在的层，搜索时需用
12 char c; //节点对应的字符，此题搜索时要用，一般字典序可能不必
13 Node *letter[26];
14
};
15
16Node *root;
17
18//向字典树中加入一单词
19void InsertWord(const char *word, const int &pro)
20{
21 Node *ptr = root;
22 int len = strlen(word);
23
24 for(int i=0; i<len; i++)
25
{
26 int index = word[i] - 'a';
27 if(ptr->letter[index] == NULL)
28 {
29 ptr->letter[index] = new Node();
30 ptr->letter[index]->p = pro;
31 ptr->letter[index]->c = word[i];
32
}
33 else
34 {
35 ptr->letter[index]->p += pro;
36 }
37 ptr = ptr->letter[index];
38 }
39}
40
41//清除字典树
42void DelTree(Node *p)
43{
44 for(int i=0; i<26; i++)
45 {
46 if(p->letter[i] != NULL)
47 {
48 DelTree(p->letter[i]);
49 }
50 }
51 delete p;
52}
53
54//从字典树中找出数字串对应的最大频率单词前缀
55char* FindWord(const char *dec,int e)
56{
57 int mTable[10][4] = {{/**//*0,0,0,0*/},{/**//*0,0,0,0*/},{0,1,2,0},{3,4,5,0},{6,7,8,0}, //按键数字对应的字符映射表
58 {9,10,11,0},{12,13,14,0},{15,16,17,18},{19,20,21,0},{22,23,24,25}};
59
60 Node *ptr = root;
61 int maxP = 0;
62 char word[101]; //当前获得的前缀串
63 char *ans = new char[101]; //频率最大前缀串
64
65 stack<Node*> sq;
66
67 Node *cur,*nex;
68
69 cur = root;
70 cur->lev = -1;
71 sq.push(cur);
72
73 while(!sq.empty())
74 {
75 cur = sq.top();
76 sq.pop();
77
78 if(cur->lev > -1)
79 {
80 word[cur->lev] = cur->c;
81 }
82
83 if(cur->lev == e) //当层数与数字串位数相等时即判断
84 {
85 if(maxP <= cur->p) //注意相等情况，用于处理权值相等时的前缀选择（字典序靠前）
86 {
87 maxP = cur->p;
88 for(int i=0; i<=e; i++)
89 {
90 ans[i] = word[i];
91 }
92 }
93 }
94 else
95 {
96 int n = (dec[cur->lev + 1] == '7' || dec[cur->lev + 1] == '9') ? 4 : 3;
97 for(int i=0; i<n; i++)
98 {
99 int index = mTable[dec[cur->lev + 1] - '0'][i];
100 nex = cur->letter[index];
101 if(nex != NULL)
102 {
103 nex->lev = cur->lev + 1;
104 sq.push(nex);
105 }
106 }
107 }
108 }
109 if(maxP == 0)
110 {
111 return "MANUALLY";
112 }
113
114 ans[e + 1] = '\0';
115 return ans;
116}
117
118int main()
119{
120 int nCase;
121 int w,m;
122 char word[101];
123 int p;
124
125 char dec[101];
126
127 /**//*ifstream infile("input.txt");
128 ofstream outfile("output.txt");*/
129
130 cin>>nCase;
131 //infile>>nCase;
132 for(int k=1; k<=nCase; k++)
133 {
134 root = new Node();
135
136 cin>>w;
137 //infile>>w;
138 for(int i=0; i<w; i++)
139 {
140 cin>>word>>p;
141 //infile>>word>>p;
142 InsertWord(word,p);
143 }
144 cin>>m;
145 //infile>>m;
146
147 cout<<"Scenario #"<<k<<":"<<endl;
148 //outfile<<"Scenario #"<<k<<":"<<endl;
149 for(int i=0; i<m; i++)
150 {
151 cin>>dec;
152 //infile>>dec;
153
154 int len = strlen(dec) - 1;
155 for(int j=0; j<len; j++)
156 {
157 cout<<FindWord(dec,j)<<endl;
158 //outfile<<FindWord(dec,j)<<endl;
159 }
160 cout<<endl;
161 //outfile<<endl;
162 }
163 cout<<endl;
164 DelTree(root); //每次必须清空字典树，以防止影响后面新字典树的建立
165 }
166 /**//*infile.close();
167 outfile.close();*/
168 system("Pause");
169 return 0;
170}