字典树+DFS。
#include<cstdio> #include<cstring> #include<cmath> #include<string> #include<algorithm> using namespace std; struct shu{ int value, nn[27]; }node[250010]; int n, q, i, ii, v, zz, tott, anss, tt, ttt; const int INF = 0x7FFFFFFF; char s[1000], sc[1000], vc[1000], ljb[10][10]; void ljbb() { ljb[2][0] = 3; ljb[2][1] = 'a'; ljb[2][2] = 'b'; ljb[2][3] = 'c'; ljb[3][0] = 3; ljb[3][1] = 'd'; ljb[3][2] = 'e'; ljb[3][3] = 'f'; ljb[4][0] = 3; ljb[4][1] = 'g'; ljb[4][2] = 'h'; ljb[4][3] = 'i'; ljb[5][0] = 3; ljb[5][1] = 'j'; ljb[5][2] = 'k'; ljb[5][3] = 'l'; ljb[6][0] = 3; ljb[6][1] = 'm'; ljb[6][2] = 'n'; ljb[6][3] = 'o'; ljb[7][0] = 4; ljb[7][1] = 'p'; ljb[7][2] = 'q'; ljb[7][3] = 'r'; ljb[7][4] = 's'; ljb[8][0] = 3; ljb[8][1] = 't'; ljb[8][2] = 'u'; ljb[8][3] = 'v'; ljb[9][0] = 4; ljb[9][1] = 'w'; ljb[9][2] = 'x'; ljb[9][3] = 'y'; ljb[9][4] = 'z'; } void dfs(int ff, int zzz, int gl) { int i; if (ff == ttt) { if (node[zzz].value > anss) { anss = node[zzz].value; sc[gl] = ' '; strcpy(vc, sc); } return; } if (s[ff] == '1') dfs(ff + 1, zzz, gl); for (i = 1; i <= ljb[s[ff] - '0'][0]; i++) { if (node[zzz].nn[ljb[s[ff] - '0'][i] - 'a'] != -1) { sc[gl] = ljb[s[ff] - '0'][i]; dfs(ff + 1, node[zzz].nn[ljb[s[ff] - '0'][i] - 'a'], gl + 1); } } } int main() { ljbb(); int sb, bs; scanf("%d", &sb); for (bs = 1; bs <= sb; bs++) { scanf("%d", &n); for (i = 0; i <= 250000; i++) { node[i].value = 0; memset(node[i].nn, -1, sizeof(node[i].nn)); } tott = 1; for (ii = 0; ii < n; ii++) { scanf("%s%d", s, &v); zz = 0; for (i = 0; s[i]; i++) { if (node[zz].nn[s[i] - 'a'] == -1) { node[zz].nn[s[i] - 'a'] = tott; tott++; } zz = node[zz].nn[s[i] - 'a']; node[zz].value += v; } } scanf("%d", &q); printf("Scenario #%d: ", bs); for (ii = 0; ii < q; ii++) { scanf("%s", s); tt = strlen(s); for (i = 1; i < tt; i++) { anss = -INF; ttt = i; dfs(0, 0, 0); if (anss == -INF) printf("MANUALLY "); else printf("%s ", vc); } printf(" "); } printf(" "); } return 0; }