日本搞逼视频_黄色一级片免费在线观看_色99久久_性明星video另类hd_欧美77_综合在线视频

國內最全IT社區平臺 聯系我們 | 收藏本站
阿里云優惠2
您當前位置:首頁 > 互聯網 > hdu 1298 T9(字典樹+DFS)

hdu 1298 T9(字典樹+DFS)

來源:程序員人生   發布時間:2014-11-04 08:53:30 閱讀次數:2584次

題目連接:hdu 1298 T9

題目大意:摹擬手機打字的料想功能,根據幾率,每按1個按鍵,輸出可能性最高的串。先給定N個單詞,和頻率,

然后是Q次詢問,每次詢問給定1個按按鍵的順序,以1為終止。

解題思路:對單詞表建立字典樹,每一個節點有1個經過的頻率,這個頻率是根據所有經過該節點的單詞頻率總和。然后

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; } }
生活不易,碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
程序員人生
------分隔線----------------------------
分享到:
------分隔線----------------------------
關閉
程序員人生
主站蜘蛛池模板: 91免费国产视频 | 日韩欧美在 | 成人在线一区二区 | 日韩一区二区在线免费观看 | 久久国产精品精品 | 激情欧美日韩一区二区 | 国产精品久久亚洲 | 久久精品1 | 三级www| 日本乱偷中文字幕 | 加勒比不卡| 97av精品| 欧美成人毛片 | 国产亚洲一区二区三区 | 四虎影院最新网址 | 91精品久久久久久久久99蜜臂 | 在线观看国产视频 | 日韩精品1区| 日韩精品视频在线播放 | a黄色片 | 日韩午夜免费视频 | 中文字幕第九页 | 亚洲福利一区二区 | 三级免费网站 | 国内 美女 主播 精品 视频 | 中文在线中文a | 中文字幕一区二区三区在线播放 | 欧美成人一区二区 | 精品伊人久久久久7777人 | 一区二区三区四区不卡 | 欧美日韩成人 | 欧美福利在线观看 | 在线成人一区 | 国产精品99久久久 | 久久精品a | 日韩av网址大全 | 在线看亚洲| 92久久 | 国产高清一级毛片在线不卡 | 欧美成人免费在线视频 | 色综合视频一区二区三区 |