点我看题
题意:给出一系列的单词作为字典,这些单词有着自己对应的出现概率对于有相同前缀的,前缀概率为包含的所有单词的概率相加,然后对应手机拼音九键的输入法规则且概率大的先输出,输入按下的键值,要求输出对应的系列字母,如果字典中不存在,则输出"MANUALLY". 分析:百度看了一下题解,发现还是用指针写的多,我还是想用数组实现.用字典树存储输入的单词,字典树的结构为child[10000][26]+value[10000].查询的时候用深搜TrieSearch(rt,cur,deep),具体看注释. 参考代码:
#include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<iostream> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)) int w,m; char word[105];//输入的单词 int pro;//输入单词对应值 char query[105];//按键 //TrieTree int child[10000][26];//结点 int node;//记录结点的个数 int value[10000];//记录结点的值 //按键记录 int press[10] = {0,0,3,3,3,3,3,4,3,4};//每个键具有的字母个数 char key[10][5] ={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};//每个键对应的字母 char ans[105];//记录查到的结果 char fi[105];//最终ans int tmp;//查找过程中记录临时value //初始化 void init() { mem(child[0],0); node = 1; mem(value,0); } //单词插入到树中 void TrieInsert( char word[], int pro) { int rt = 0; int p = 0; while( word[p] != '\0') { int id = word[p]-'a'; if( !child[rt][id]) { mem(child[node],0); value[node] = 0; child[rt][id] = node++; } value[child[rt][id]] += pro; rt = child[rt][id]; p++; } } void TrieSearch( int rt, int cur, int deep) { if( cur == deep) { if( value[rt] > tmp) { tmp = value[rt]; for( int i = 0; i <= deep; i++) fi[i] = ans[i]; fi[deep+1] = '\0'; } return; } int len = press[query[cur+1]-'0'];//键包括的字母长度 for( int i = 0; i < len; i++) { int id = key[query[cur+1]-'0'][i]-'a'; if( child[rt][id]) { ans[cur+1] = 'a'+id; ans[cur+2]='\0'; TrieSearch(child[rt][id],cur+1,deep); } } } int main() { int T; scanf("%d",&T); while( T--) { init(); scanf("%d",&w); for( int i = 1; i <= w; i++) { scanf("%s%d",word,&pro); TrieInsert(word,pro); } static int cas = 1; printf("Scenario #%d:\n",cas++); scanf("%d",&m); for( int i = 1; i <= m; i++) { scanf("%s",query); for( int i = 0; query[i] != '1'; i++) { tmp = 0; TrieSearch(0,-1,i); if( tmp) printf("%s\n",fi); else puts("MANUALLY"); } puts(""); } puts(""); } return 0; }