POJ 1451辞書ツリー
この問題の意味は入力法に似ています.いくつかのボタンを押して、単語ライブラリの中で最も頻度の高い語彙を飛び出します.
まず、単語ライブラリが表示され、各単語に出現頻度があります.
そして、携帯電話でどのキーを押したかを表す文字列があり、最後に1で終わる質問があります.これらのボタンを押す過程で出てくる単語はどれですか.
考えは辞書の木だ.
携帯電話の8つのキーで8つのポインタを作って辞書の木を作ります.
各ノードにはポインタのほかに,最も頻度の高い単語が格納されている.
ツリーを作成するときは、同じ接頭辞ごとに1回しか挿入できません.そうしないと処理できません.
だから挿入する前に、同じ接頭辞の周波数値をすべて加算して、挿入するときに1回挿入すればいいので、最適値を更新するたびにいいです.
タイトルの入力はすでに順番に並んでいて、私たちがソートする時間を節約しました.接頭辞が同じのは必ず1つなので、隣同士で比較すればいいのですが、
まず、単語ライブラリが表示され、各単語に出現頻度があります.
そして、携帯電話でどのキーを押したかを表す文字列があり、最後に1で終わる質問があります.これらのボタンを押す過程で出てくる単語はどれですか.
考えは辞書の木だ.
携帯電話の8つのキーで8つのポインタを作って辞書の木を作ります.
各ノードにはポインタのほかに,最も頻度の高い単語が格納されている.
ツリーを作成するときは、同じ接頭辞ごとに1回しか挿入できません.そうしないと処理できません.
だから挿入する前に、同じ接頭辞の周波数値をすべて加算して、挿入するときに1回挿入すればいいので、最適値を更新するたびにいいです.
タイトルの入力はすでに順番に並んでいて、私たちがソートする時間を節約しました.接頭辞が同じのは必ず1つなので、隣同士で比較すればいいのですが、
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define eps 1e-5
#define MAXN 1111
#define MAXM 55555
#define INF 1000000000
using namespace std;
int c[1005][105], e;
char s[1005][105];
char tmp[105];
char dic[] = "22233344455566677778889999";
struct Trie
{
int next[8];
int num;
char s[105];
void init ()
{
memset(next, 0, sizeof(next));
num = 0;
}
} trie[MAXM];
void make_trie (char *str, int id)
{
int i = 0, index, u = 0;
while(str[i])
{
index = dic[str[i] - 'a'] - '2';
if(!trie[u].next[index]) trie[u].next[index] = ++e;
u = trie[u].next[index];
if(c[id][i] > trie[u].num)
{
trie[u].num = c[id][i];
for(int j = 0; j <= i; j++) trie[u].s[j] = s[id][j];
trie[u].s[i + 1] = '\0';
}
i++;
}
}
void match(char *str)
{
int i = 0, index, u = 0, flag = 0;;
while(str[i] && str[i] != '1')
{
index = str[i] - '2';
u = trie[u].next[index];
if(trie[u].num == 0 || u == 0 || flag) printf("MANUALLY
"), flag = 1;
else printf("%s
", trie[u].s);
i++;
}
}
int main()
{
int T, n, p, m, cas = 0;
scanf("%d", &T);
while(T--)
{
scanf("%d", &n);
memset(c, 0, sizeof(c));
for(int i = 0; i < n; i++)
{
scanf("%s%d", s[i], &p);
int len = strlen(s[i]);
for(int j = 0; j < len; j++) c[i][j] = p;
}
for(int i = 1; i < n; i++)
for(int j = 0; s[i][j] && s[i - 1][j]; j++)
{
if(s[i][j] == s[i - 1][j])
{
c[i][j] += c[i - 1][j];
c[i - 1][j] = 0;
}
else break;
}
for(int i = 0; i < MAXM; i++) trie[i].init();
e = 0;
for(int i = 0; i < n; i++) make_trie(s[i], i);
scanf("%d", &m);
printf("Scenario #%d:
", ++cas);
while(m--)
{
scanf("%s", tmp);
match(tmp);
printf("
");
}
printf("
");
}
return 0;
}