当前位置:   article > 正文

POJ 1451 T9 (字典树好题)

poj 1451 t9

背景:为了方便九宫格手机用户发短信,希望在用户按键时,根据提供的字典(给出字符串和频数),给出各个阶段最有可能要打的单词。

题意: 首先给出的是字典,每个单词有一个出现频率。然后给出的是询问,每个询问有一个数字字符串,代表在手机上按了哪些键,以1结束。问按键的过程中最可能出现的单词分别是哪些。

思路:搞了很久.......一开始总想着以字母为各结点如何建树,询问......还是太年轻了。

以手机8个键作为字典树各节点,每个结点映射3-4对应的字母。每个结点存频率最高的串,询问的时候也可以方便的直接询问了。

还是太年轻了.........理解题意为具有相同前缀的串的频率是高的覆盖低的........其实是叠加...........一直没看出来。

题目是按照字典序升序给出字典的,所以可以把相同的前缀频率相加,这样只是插入一次了。

接下来就是基本字典树的写法了


  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iostream>
  4. using namespace std;
  5. char book[] = {"22233344455566677778889999"}; //映射
  6. char str[1111][111];
  7. int cou[1111][111];
  8. struct trie {
  9. trie *next[12];
  10. char word[105];
  11. int num;
  12. trie() {
  13. num = 0;
  14. memset(next,0,sizeof(next));
  15. memset(word,0,sizeof(word));
  16. }
  17. }*root;
  18. void insert(char *key,int i) {
  19. trie *p = root;
  20. char tmp[105];
  21. int ind = 0;
  22. int j = 0;
  23. while(key[j]) {
  24. int t = book[key[j] - 'a'] - '0';
  25. tmp[ind++] = key[j];
  26. if(p->next[t] == NULL) {
  27. p->next[t] = new trie();
  28. }
  29. p = p->next[t];
  30. tmp[ind] = '\0';
  31. if(p->num < cou[i][j]) {
  32. p->num = cou[i][j];
  33. strcpy(p->word,tmp);
  34. }
  35. j++;
  36. }
  37. }
  38. void query(char *key) {
  39. trie *p = root;
  40. int flag = 0;
  41. while(*key) {
  42. int t = *key - '0';
  43. if(p->next[t] == NULL || flag) { //用flag标记一下,有可能会有前一个单词不存在,后面单词存在字典中,此时应该输出这个的
  44. printf("MANUALLY\n");
  45. key++;
  46. flag = 1;
  47. continue;
  48. }
  49. p = p->next[t];
  50. printf("%s\n",p->word);
  51. key ++;
  52. }
  53. }
  54. void free(trie *p) { //释放内存而已
  55. for(int i=0; i<=9; i++) {
  56. if(p->next[i] != NULL) free(p->next[i]);
  57. }
  58. delete p;
  59. }
  60. int main() {
  61. #ifndef ONLINE_JUDGE
  62. freopen("in.txt","r",stdin);
  63. freopen("D:\\hehe.txt","w",stdout);
  64. #endif
  65. int T,cnt;
  66. cin >> T;
  67. int casee = 1;
  68. while(T --) {
  69. root = new trie();
  70. int n,i;
  71. scanf("%d",&n);
  72. for(i=0; i<n; i++) {
  73. scanf("%s%d",str[i],&cnt);
  74. int len = strlen(str[i]);
  75. for(int j=0; j<len; j++) {
  76. cou[i][j] = cnt;
  77. }
  78. }
  79. for(i=1; i<n; i++) //相同前缀频率相加,堆在一起算
  80. for(int j=0; str[i][j] && str[i - 1][j]; j++) {
  81. if(str[i][j] == str[i-1][j]) {
  82. cou[i][j] += cou[i-1][j];
  83. cou[i-1][j] = 0;
  84. }
  85. else break;
  86. }
  87. for(i=0; i<n; i++) {
  88. insert(str[i],i);
  89. }
  90. printf("Scenario #%d:\n",casee ++);
  91. int m;
  92. scanf("%d",&m);
  93. char str1[111],st[111];
  94. for(i=0; i<m; i++) {
  95. scanf("%s",st);
  96. int len = strlen(st);
  97. strncpy(str1,st,len-1);
  98. str1[len-1] = '\0';
  99. query(str1);
  100. puts("");
  101. }
  102. puts("");
  103. free(root);
  104. }
  105. return 0;
  106. }


声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Li_阴宅/article/detail/774804
推荐阅读
相关标签
  

闽ICP备14008679号