本文主要是介绍POJ 1451 T9 字典树+优先队列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目来源：POJ 1451 T9
题意：给你一些单词 和优先值 然后当你按下数字的时候首先会出现哪个单词 就是我们平时手机的按键
思路：建一颗字典树 因为按一个数字对应多个字母 那么就有多种情况 我们要输出权值最大的一个 我用了优先队列 这里每个前缀的优先值是所有单词优先值的和
例如abc 5 abd 6 acd 7 那么a这个前缀的优先值是18 ab的优先值是11
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int maxnode = 100010;
const int sigma_size = 26;
const int maxn = 1010;
int ch[maxnode][sigma_size];
int val[maxnode];
int sz;char s[maxn][110];
char id[12][6] = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
void init()
{sz = 1;memset(ch[0], 0, sizeof(ch[0]));
}
struct node
{int u, v, x;char str[110];node(){}node(int _u, int _v, int _x, char* s){u = _u;v = _v;x = _x;strcpy(str, s);}bool operator < (const node& rhs) const{if(v != rhs.v)return v > rhs.v;return x < rhs.x;}
};
int idx(char c)
{if(c >= 'a' && c <= 'c')return 2;if(c >= 'd' && c <= 'f')return 3;if(c >= 'g' && c <= 'i')return 4;if(c >= 'j' && c <= 'l')return 5;if(c >= 'm' && c <= 'o')return 6;if(c >= 'p' && c >= 's')return 7;if(c >= 't' && c <= 'v')return 8;if(c >= 'w' && c <= 'z')return 9;
}void insert(char *s, int v)
{int u = 0, n = strlen(s);for(int i = 0; i < n; i++){int c = s[i] - 'a';if(!ch[u][c]){memset(ch[sz], 0, sizeof(ch[sz]));val[sz] = 0;ch[u][c] = sz++;}u = ch[u][c];val[u] += v;}//val[u] += v;
}
void find(char *s)
{int u = 0, n = strlen(s);priority_queue <node> Q;Q.push(node(0, 0, 0, ""));for(int i = 0; i < n-1; i++){int c = s[i]-'0';while(!Q.empty()){node x = Q.top();if(x.v != i)break;Q.pop();u = x.u;for(int j = 0; id[c][j]; j++){int v = id[c][j] - 'a';//printf("%d\n", v);if(!ch[u][v])continue;v = ch[u][v];x.str[i] = id[c][j];x.str[i+1] = 0;//printf("%c\n", id[c][j]);Q.push(node(v, i+1, val[v], x.str));}}if(Q.empty()){puts("MANUALLY");}else{node x = Q.top();printf("%s\n", x.str);}}
}int main()
{int cas = 1;int T;scanf("%d", &T);while(T--){int n, m;scanf("%d", &n);init();for(int i = 0; i < n; i++){//char s[maxn];int x;scanf("%s %d", s[i], &x);insert(s[i], x);}printf("Scenario #%d:\n", cas++);scanf("%d", &m);while(m--){char str[210];scanf("%s", str);find(str);puts("");}puts("");}return 0;
}
这篇关于POJ 1451 T9 字典树+优先队列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
