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