題目連接：hdu 1298 T9
題目大意：摹擬手機打字的料想功能，根據(jù)幾率，每按1個按鍵，輸出可能性最高的串。先給定N個單詞，和頻率，
然后是Q次詢問，每次詢問給定1個按按鍵的順序，以1為終止。
解題思路：對單詞表建立字典樹，每一個節(jié)點有1個經(jīng)過的頻率，這個頻率是根據(jù)所有經(jīng)過該節(jié)點的單詞頻率總和。然后
DFS搜索1遍，將答案保存在ans中。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 100005;
const int maxm = 105;
const int sigma_size = 26;
const char dir[15][10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
struct Tire {
int sz, g[maxn][sigma_size], val[maxn];
void init();
int idx(char ch);
void insert(char *s, int x);
}T;
int N, Q, c[maxm];
char ans[maxm][maxm], w[maxm], r[maxm];
void dfs (int d, int u) {
if (d) {
if (T.val[u] > c[d]) {
c[d] = T.val[u];
strncpy(ans[d], r, d);
}
}
if (w[d] == 0 || w[d] == '1')
return;
int x = w[d] - '0';
for (int i = 0; dir[x][i]; i++) {
int v = dir[x][i] - 'a';
if (T.g[u][v] == 0)
continue;
r[d] = dir[x][i];
dfs(d + 1, T.g[u][v]);
}
}
int main () {
int cas;
scanf("%d", &cas);
for (int kcas = 1; kcas <= cas; kcas++) {
T.init();
scanf("%d", &N);
int x;
for (int i = 0; i < N; i++) {
scanf("%s%d", w, &x);
T.insert(w, x);
}
printf("Scenario #%d:
", kcas);
scanf("%d", &Q);
for (int i = 0; i < Q; i++) {
scanf("%s", w);
memset(c, 0, sizeof(c));
dfs(0, 0);
for (int x = 1; w[x-1] != '1'; x++) {
// printf("<%c> %d:", w[x], c[x]);
if (c[x] == 0)
printf("MANUALLY
");
else {
for (int j = 0; j < x; j++)
printf("%c", ans[x][j]);
printf("
");
}
}
printf("
");
}
printf("
");
}
return 0;
}
void Tire::init() {
sz = 1;
val[0] = 0;
memset(g[0], 0, sizeof(g[0]));
}
int Tire::idx(char ch) {
return ch - 'a';
}
void Tire::insert(char* s, int x) {
int u = 0, n = strlen(s);
for (int i = 0; i < n; i++) {
int v = idx(s[i]);
if (g[u][v] == 0) {
g[u][v] = sz;
memset(g[sz], 0, sizeof(g[sz]));
val[sz++] = 0;
}
u = g[u][v];
val[u] += x;
}
}
程序員人生，我編程，我富裕，記住wfuyu網(wǎng)，php教程，php學(xué)習(xí)，php手冊，CMS模版制作
聲明：本站大部分內(nèi)容是作者原創(chuàng)，少部分收集于互聯(lián)網(wǎng)供大家一起學(xué)習(xí)，原版權(quán)很多不明，如有侵權(quán)請聯(lián)系本站，謝謝！
粵ICP備14040726號-1?? 2015-2020 程序員人生 版權(quán)所有
