题目大意： 在以前，手机输入法很麻烦，因为只有9个键，而字母有26个，所以一个键上同时包含这几个字母，这样的话，为了打出一个字母可能要按几次。比如键5有“JKL”， 如果要输入K，那么就要连按两次。 这样的输入法很麻烦。所以一家公司发明了T9技术输入法。这种输入法内置这很多英语单词，它可以根据英语出现的频率，是否存在等信息，每个字母只要按一次，就可以有想要的预选单词。 例如，假设输入法只内置了一个单词“hell”， 那么只需要按4355便可以出来。 注意，如果有一个单词hell， 那么这个单词的所有前缀，h, he, hel, 也当作是存在的
Sample Input
2 5 hell 3 hello 4
idea 8 next 8 super 3 2 435561 43321 7 another 5 contest 6 follow 3 give 13
integer 6 new 14 program 4 5 77647261 6391 4681 26684371 77771
Sample Output
Scenario #1: i id
hel hell hello i id ide idea Scenario #2: p pr pro prog progr progra program n
ne new g in int c co con cont anoth anothe another p pr MANUALLY MANUALLY
#include<iostream> #include<cstdio> #include<cstring> #include<vector> using namespace std; const int KIND = 26; const int MAXN = 15000; int cnt_node; vector<int>g[10]; char input[105]; char ans[105]; int num, Max; bool flag; struct node{ int prefix; node *next[KIND]; void init(){ prefix=0; memset(next, 0, sizeof(next)); } }Heap[MAXN]; inline node* newNode(){ Heap[cnt_node].init(); return &Heap[cnt_node++]; } void insert(node *root, char *str, int n){ for(char *p=str; *p; ++p){ int ch=*p-‘a‘; if(root->next[ch]==NULL) root->next[ch] = newNode(); root = root->next[ch]; root->prefix += n; } } void dfs(node *root, char *str, int pos){ //str保存输出结果 if(root==NULL)return; if(pos >= num){ if(root->prefix > Max){ strcpy(ans, str); Max=root->prefix; } flag=true; return ; } int u=input[pos]-‘0‘; for(int i=0; i<g[u].size(); ++i){ str[pos] = g[u][i]+‘a‘; dfs(root->next[g[u][i]], str, pos+1); str[pos] = 0; } } int main(){ int T,n,p,cas=1; char str[105]; // 键盘设置, 貌似这样写复杂了... for(int i=0; i<10; ++i) g[i].clear(); g[2].push_back(0), g[2].push_back(1), g[2].push_back(2); g[3].push_back(3), g[3].push_back(4), g[3].push_back(5); g[4].push_back(6), g[4].push_back(7), g[4].push_back(8); g[5].push_back(9), g[5].push_back(10), g[5].push_back(11); g[6].push_back(12), g[6].push_back(13), g[6].push_back(14); g[7].push_back(15), g[7].push_back(16), g[7].push_back(17),g[7].push_back(18); g[8].push_back(19), g[8].push_back(20), g[8].push_back(21); g[9].push_back(22), g[9].push_back(23), g[9].push_back(24), g[9].push_back(25); scanf("%d",&T); while(T--){ scanf("%d",&n); printf("Scenario #%d:\n", cas++); // Trie init cnt_node=0; node *root = newNode(); for(int i=0; i<n; ++i){ scanf("%s %d",str,&p); insert(root, str, p); } scanf("%d",&n); for(int i=0; i<n; ++i){ scanf("%s", input); for(int j=0; j<strlen(input)-1; ++j){ memset(str, 0, sizeof(str)); Max=-1; num=j+1; flag=false; dfs(root, str, 0); if(flag) puts(ans); else puts("MANUALLY"); } puts(""); } puts(""); } return 0; }