就是字典树加dfs
把所有操作封在结构体里面
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>using namespace std;const int maxn = 1e5 + ;char dic[][] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
int n, w, p, m, P;
char s[], num[], Find[], ans[];struct Trie
{
int pos;
int tree[maxn][];
int val[maxn]; void clear()
{
pos = ;
memset(tree[], , sizeof(tree[]));
memset(val, , sizeof(val));
} int idx(char c)
{
return c - 'a';
} void insert(char *s, int v)
{
int root = , n = strlen(s);
for(int i = ; i < n; i++)
{
int ch = idx(s[i]);
if(!tree[root][ch])
{
memset(tree[pos], , sizeof(tree[pos]));
tree[root][ch] = pos++;
} root = tree[root][ch];
val[root]+=v;
}
} void query(int cur, int len, int u)
{
if(cur == len && val[u] > P)
{
P = val[u];
for(int i = ; i < len; i++)
{
Find[i] = ans[i];
Find[len] = '\0';
}
return ;
}
int id = num[cur] - '';
for(int i = ; dic[id][i]; i++)
{
int c = idx(dic[id][i]);
if(!tree[u][c])
continue;
ans[cur] = dic[id][i];
query(cur+, len, tree[u][c]);
}
return ;
}
}trie;int main()
{
int flag = ;
int T;
scanf("%d", &T);
while(T--)
{
trie.clear();
printf("Scenario #%d:\n", flag++);
scanf("%d", &w);
for(int i = ; i < w; i++)
{
scanf("%s%d", s, &p);
trie.insert(s, p);
}
scanf("%d", &m);
for(int i = ; i < m; i++)
{
scanf("%s", num);
int len = strlen(num);
for(int j = ; j < len; j++)
{
P = ;
trie.query(, j, );
if(P>)
puts(Find);
else
puts("MANUALLY");
}
puts("");
}
puts("");
}
}