题目链接：https://vjudge.net/problem/POJ-1451 ac代码： 出处：https://www.cnblogs.com/8023spz/p/9613371.html
#include <algorithm> #include <stdio.h> #include <bitset> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <deque> #include <functional> #include <iostream> #include <map> #include <queue> #include <set> #include <stack> #include <string> #include <vector> using namespace std; #define Max 100001 int t,w,p,pos; map<string,int>num; map<string,string>more; int to[26]={2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,7,7,7,8,8,8,9,9,9,9}; int trie[Max][26],times[Max]; void Insert(char *s,int x) { int c=0; string temp,s1; for(int i=0;s[i];i++) { s1+=s[i]; int d=s[i]-'a'; if(!trie[c][d]) { trie[c][d]=++pos; } c=trie[c][d]; times[c]+=x; temp+='0'+to[d]; if(num[temp]<times[c]) { num[temp]=times[c]; more[temp]=s1; } } } int main() { char s[101]; int d; scanf("%d",&t); int Case=1; while(t--) { memset(times,0,sizeof(times)); num.clear(); more.clear(); scanf("%d",&w); for(int i=0;i<w;i++) { scanf("%s %d",s,&d); Insert(s,d); } scanf("%d",&p); printf("Scenario #%d:\n",Case++); for(int i=0;i<p;i++) { scanf("%s",s); string s1; for(int k=0;s[k+1];k++) { s1+=s[k]; if(more[s1]!="") { cout<<more[s1]<<endl; //printf("%s\n",more[s1].c_str()); } else { printf("MANUALLY\n"); } } putchar('\n'); } putchar('\n'); } return 0; }