POJ1451
本题题意比较有意思，大概就是模拟手机输入法，先给你一个用户的词库，即每个单词出现的次数，这个时候再按照九键输入法给你一个数字序列，问你在输入这个序列的过程中，出现的字符串顺序，也就是对于每个数字序列，给出一个最有可能出现的字符串。
这道题我的做法比较巧妙，但是不怎么会算复杂度，还是很快的过去了。首先我们考虑，对于每个数字序列，我们都可以用一个string去映射，这样我们可以用一个map来离线保存每个数字序列对应的最有可能出现的字符串，可是我们怎么知道每个数字序列最有可能出现的字符串是哪个呢，首先我们对单词进行映射，把每个单词映射成数字序列，然后在插入的过程中，对于每一个前缀都更新一下这个前缀对应的map，最后查询的时候就可以直接输出了。
POJ1451代码
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<sstream>
#include<map>
using namespace std;
const int maxn =2e6+5;
int tree[maxn][30];
int sum[maxn];
int tot;
int belong[30];
map<string,int> mm;//每种数字序列最大出现次数
map<string,string>mm2;//每种序列对应的最大次数的字符串
void insert_(char *str,int num)
{int len=strlen(str);int root=0;string strr="";string str2="";for(int i=0;i<len;i++){int id=str[i]-'a';strr+=(belong[id]+'0');//将插入的字符串映射成数字序列str2+=str[i];//当前前缀if(!tree[root][id]) tree[root][id]=++tot;root=tree[root][id];sum[root]+=num;//统计每个前缀出现次数if(mm[strr]<sum[root])//更新map{mm[strr]=sum[root];mm2[strr]=str2;}}return ;
}
char ss[maxn];
void init()//数字与字母间的映射
{for(int i=0;i<25;i++){if(i<18)belong[i]=2+i/3;elsebelong[i]=2+(i-1)/3;}belong[25]=9;return ;
}
int main()
{init();int cnt=1;int n,m,t,num;scanf("%d",&t);while(t--){mm.clear();mm2.clear();scanf("%d",&n);while(n--){scanf("%s%d",ss,&num);insert_(ss,num);}scanf("%d",&m);printf("Scenario #%d:\n",cnt++);while(m--){scanf("%s",ss);string tmp="";int len=strlen(ss);for(int i=0;i<len-1;i++){tmp+=ss[i];//对于每个前缀直接输出if(!mm2.count(tmp)) printf("MANUALLY\n");else printf("%s\n",mm2[tmp].c_str());}printf("\n");}for(int i=0;i<tot;i++){sum[i]=0;for(int j=0;j<30;j++)tree[i][j]=0;}printf("\n");}return 0;
}