http://acm.hdu.edu.cn/showproblem.php?pid=1298
题意:
模拟手机9键,给出每个单词的使用频率。现在给出按键的顺序,问每次按键后首字是什么(也就是要概率最大的)。
思路:
先建立字典树算出每个前缀出现的概率,然后dfs每种情况,选择概率大的。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = *+; char s[],ans[],tmp[]; int n, num = , p;
int pheno[][] = {{,,},{,,},{,,},{,,},{,,},{,,,},{,,},{,,,}};
int key[] = {,,,,,,,}; struct Trie
{
int son[];
int cnt;
}t[maxn]; void init(int x)
{
t[x].cnt = ;
memset(t[x].son,,sizeof(t[x].son));
} void insert(char* s, int d)
{
int u = , n = strlen(s);
for(int i=;i<n;i++)
{
int c = s[i]-'a';
if(!t[u].son[c])
{
num++;
init(num);
t[u].son[c] = num;
}
u = t[u].son[c];
t[u].cnt += d;
}
} void dfs(int cur, int u, int len, char* s)
{
if(cur == len)
{
if(t[u].cnt > p)
{
p = t[u].cnt;
for(int i=;i<len;i++) ans[i] = tmp[i];
ans[len] = '\0';
}
return;
}
int k = s[cur]-'';
for(int i=;i<key[k];i++)
{
int c = pheno[k][i];
if(!t[u].son[c]) continue;
tmp[cur] = 'a'+ c;
dfs(cur+, t[u].son[c], len, s);
}
} int main()
{
//freopen("in.txt","r",stdin);
int T;
scanf("%d",&T);
int kase = ;
while(T--)
{
init();
scanf("%d",&n);
for(int i =;i<n;i++)
{
scanf("%s%d",s,&p);
insert(s,p);
}
printf("Scenario #%d:\n",++kase);
int q; scanf("%d",&q);
while(q--)
{
scanf("%s",&s);
int len = strlen(s);
for(int i=;i<len-;i++)
{
p = ;
dfs(,,i+,s);
if(p) printf("%s\n",ans);
else puts("MANUALLY");
}
if(q) puts("");
}
printf("\n\n");
}
return ;
}