题意
和手机的九键输入法一样。输入数据第一行给出有多少组测试数据，每组数据第一行给出w(0<=w<=1000)，接下来w行给出一个单词以及该单词的出现频率p(1<=p<=100)，每个单词的最大长度不超过100个字母；然后，给出一个整数m，接下来m行给出一个输入串，代表在手机上按了哪些键，每个输入串最多有100个字符，且以数字1作为结尾。要求根据给出输入串，输出在按这些键的过程中，输入法给出的首选项（即出现频率最高的单词），若没有对应输入的单词，则输出"MANUALLY"。
样例输入
2
5
hell 3
hello 4
idea 8
next 8
super 3
2
435561
43321
7
another 5
contest 6
follow 3
give 13
integer 6
new 14
program 4
5
77647261
6391
4681
26684371
77771
样例输出
Scenario #1:
i
id
hel
hell
hello
i
id
ide
idea
Scenario #2:
p
pr
pro
prog
progr
progra
program
n
ne
new
g
in
int
c
co
con
cont
anoth
anothe
another
p
pr
MANUALLY
MANUALLY
思路
以26个字母来建字典树，每个结点包含代表字母，频率，父节点以及一个指针数组。建树过程中，对于已存在的结点，频率要累加起来。查询的时候使用队列，先从树根的儿子里面找出第一个键所包含的各个字母的结点入队（如果该结点存在的话），并在入队的过程中找到频率最高的结点，依靠递归逆向输出。第二个键的时候，再从当前队列里的各个结点的儿子里找到对应第二个键包含的各个字母的结点入队（如果该结点存在的话），并在入队的过程中找到频率最高的结点，依靠递归逆向输出。以此类推...
注意点
1. 题目给出的单词库是按字典序排好的。
2. 输出每组样例之间有两个空行，一个空行是每个输入串后的，另一个空行是每组样例后的。
3. 当输入串只有一个1时，也要输出一个空行。
4. 用静态字典树的话记得初始化内存。
5. 频率是叠加起来的，例如这组数据
1
3
bbb 5
aaa 3
abc 3
1
21
输出的应该是a，而不是b。
1 #include <cstdio> 2 #include <string.h> 3 #include <queue> 4 using namespace std; 5 const char n2c[10][5] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; 6 struct TRIE 7 { 8 int chr, freq, father, Next[26]; 9 }trie[100000]; 10 int AMOUNT; 11 queue<int> q; 12 void Insert(char* str, int time) 13 { 14 int t, pos = 0; 15 for(int i=0; str[i]; ++i) 16 { 17 t = str[i] - 'a'; 18 trie[pos].freq += time; 19 if(!trie[pos].Next[t]) 20 { 21 trie[pos].Next[t] = ++AMOUNT; 22 memset(trie+AMOUNT, 0, sizeof(TRIE)); 23 trie[AMOUNT].father = pos; 24 pos = AMOUNT; 25 trie[pos].chr = str[i]; 26 } 27 else 28 pos = trie[pos].Next[t]; 29 } 30 trie[pos].freq += time; 31 } 32 void PrintStr(int x) 33 { 34 if(x) 35 { 36 PrintStr(trie[x].father); 37 printf("%c", trie[x].chr); 38 } 39 } 40 void Query(char* str) 41 { 42 int MAX, MAXTAG, t, num, pos; 43 q.push(0); 44 for(int i=0; str[i]!='1'; ++i) 45 { 46 t = str[i] - '0'; 47 num = q.size(); 48 MAX = MAXTAG = 0; 49 for(int j=0; j<num; ++j) 50 { 51 for(int k=0; n2c[t][k]; ++k) 52 { 53 pos = trie[q.front()].Next[ n2c[t][k] - 'a' ]; 54 if(pos) 55 { 56 q.push(pos); 57 if(trie[pos].freq > MAX) 58 MAX = trie[pos].freq, MAXTAG = pos; 59 } 60 } 61 q.pop(); 62 } 63 if(MAXTAG) 64 { 65 PrintStr(MAXTAG); 66 printf("\n"); 67 } 68 else 69 { 70 for(; str[i] != '1'; ++i) 71 printf("MANUALLY\n"); 72 break; 73 } 74 } 75 num = q.size(); 76 while(num--) 77 q.pop(); 78 printf("\n"); 79 } 80 int main(void) 81 { 82 char str[105]; 83 int kase, n, time; 84 scanf("%d", &kase); 85 for(int i=0; i<kase; ) 86 { 87 scanf("%d", &n); 88 AMOUNT = 0; 89 memset(trie, 0, sizeof(TRIE)); 90 for(int j=0; j<n; ++j) 91 { 92 scanf("%s %d", str, &time); 93 Insert(str, time); 94 } 95 printf("Scenario #%d:\n", ++i); 96 scanf("%d", &n); 97 for(int j=0; j<n; ++j) 98 { 99 scanf("%s", str); 100 Query(str); 101 } 102 printf("\n"); 103 } 104 return 0; 105 }
7 5 hell 3 hello 4 idea 5 next 8 super 3 2 787371 43321 7 another 5 contest 6 follow 3 give 13 integer 6 new 14 program 4 5 77647261 6391 4681 26684371 77771 7 gewel 5 hello 3 hell 2 rubmarine 4 ruper 4 suring 3 suesday 5 6 439351 435561 7826274631 787371 7874641 78373291 107 ab 2 aller 2 als 10 am 2 an 3 angerechnet 5 aus 2 begruessung 6 berichterstattung 13 bestehenden 13 bis 13 bislang 14 bitten 2 computing 2 dabei 10 darmstaedter 15 das 15 dass 8 dem 9 der 6 des 1 deutschland 9 diesem 6 eines 13 einzigen 12 entscheidet 2 erfolg 14 etwa 13 fachbereich 1 felix 15 findet 6 firma 8 fraikin 7 frankfurter 9 freuen 9 fuenf 10 fuer 4 gegeneinander 15 gelaende 5 gewinnen 1 gewinnt 12 gilt 5 hawaii 11 hinweis 14 informatikervereinigung 8 informatikwissen 12 innerhalb 6 jahr 15 koennen 7 konnte 8 kontakt 13 kryptographie 6 loesen 13 loest 2 loesung 3 machinery 6 merck 15 moechten 14 moeglich 7 moeglichst 3 muessen 15 nachmittags 15 nicht 1 november 6 prestigetraechtigen 11 programmiermeisterschaften 6 reicht 14 reines 15 reisen 5 rolle 10 seit 4 skandinavien 11 spielen 12 sporthalle 3 startschuss 6 statt 3 stattfindet 10 strafminuten 2 strasse 9 studierenden 8 teamfaehigkeit 9 teil 4 teilen 7 testierungssystem 5 ueber 9 veranstalter 4 veranstaltung 10 verbuchen 13 versuch 3 von 4 weltmeisterschaft 9 welttitelkaempfen 6 wer 8 werden 6 wettbewerb 5 wettkampf 6 wichtige 15 wie 2 wir 3 wird 13 wurde 8 zb 13 zeit 1 zeitmanagement 5 zu 9 zurueckgewiesene 4 zwar 15 10 721 5678381 57978647271 3224231 631 237834363361 3371 1 7877363278471 2378361 129 acm 9 alljaehrlich 13 am 2 anderem 8 anerkannt 6 angerechnet 5 antreten 9 aufgaben 8 ausschlag 13 beginnt 3 begruessung 6 beiden 14 beneluxstaaten 8 bereichen 15 berichterstattung 13 computing 2 darauf 4 darmstadt 7 darmstaedter 15 das 15 dass 8 den 15 der 6 des 1 die 2 diese 2 diesem 6 drei 12 dreierteams 4 eigentlichen 6 eine 2 einem 1 einer 15 email 6 erfolg 14 erreichen 3 erste 10 es 1 faellt 15 falk 13 fax 15 felix 15 finale 4 for 4 fraikin 7 frankfurter 9 gegeneinander 15 gelaende 5 gestellten 13 gewinnen 1 gewinnt 12 gilt 5 gleichstand 8 graphenalgorithmen 2 groessten 7 grossbritannien 10 gute 15 hinzuweisen 3 hoffen 7 informatik 13 informatikervereinigung 8 ist 1 kleinen 11 kniffliger 10 koennen 7 kostet 7 kryptographie 6 kurzer 10 leonhardt 8 loest 2 loesung 3 lokaler 4 merck 15 mit 15 moechten 14 moeglichst 3 muessen 15 nachmittags 15 nicht 1 nimmt 4 november 6 oder 10 philipp 9 programmieraufgaben 7 programmiermeisterschaften 6 rechnen 15 rechners 2 redaktionen 6 reines 15 reisen 5 rolle 10 samstag 3 seit 4 so 10 spannenden 8 spielen 12 sporthalle 3 stammen 14 startschuss 6 statt 3 strafminuten 2 strasse 9 studierenden 8 team 14 teamfaehigkeit 9 teilnehmer 10 tel 12 testierungssystem 5 testwettbewerb 14 thomas 14 tu 9 uhr 12 um 11 unter 4 veranstalter 4 verbuchen 13 versuch 3 viele 7 von 4 weltmeisterschaft 9 welttitelkaempfen 6 wer 8 werden 6 wettkampf 6 wie 2 wuerden 15 wurde 8 zu 9 zurueckgewiesene 4 29 35374353881 1 23431 8228431 67855776425731 672833842621 5666831 6381 662645436652731 26677841 1 438261 353648888621 621 77647261 61 5637361 8565444666831 338872452631 21 1 41 346371 36741 723448851 642481 4341 77435361 322234742673871 127 ab 2 aber 13 acht 11 acm 9 allen 11 als 10 am 2 an 3 antreten 9 auch 1 ausschlag 13 beginnt 3 begruessung 6 beneluxstaaten 8 bereichen 15 berichterstattung 13 bestehenden 13 bevorstehende 15 bislang 14 bitten 2 da 8 darauf 4 darmstadt 7 darmstaedter 15 das 15 dem 9 des 1 dreierteams 4 durfte 3 ein 2 eine 2 einen 1 einzigen 12 email 6 entspricht 10 erfolg 14 erreichen 3 es 1 fachbereich 1 fax 15 findet 6 firma 8 for 4 fraikin 7 frankfurter 9 freuen 9 fuenf 10 gestellten 13 gewinnt 12 graphenalgorithmen 2 groessten 7 grossbritannien 10 hawaii 11 im 3 informatik 13 innerhalb 6 internationalen 12 internet 2 ist 1 jeder 5 jeweils 15 kniffliger 10 koennen 7 konnte 8 kontakt 13 kostet 7 kurzer 10 leonhardt 8 loesen 13 loest 2 lokaler 4 lokales 7 machinery 6 maerz 2 moechten 14 moeglich 7 muessen 15 nachmittags 15 nimmt 4 nordwesteuropaeische 14 november 6 oder 10 prestigetraechtigen 11 programmiermeisterschaften 6 qualifizieren 15 raeumen 14 rechner 9 redaktionen 6 reihe 11 reines 15 reisen 5 rolle 10 schnuppern 12 seit 4 sie 3 skandinavien 11 spannenden 8 stammen 14 stattfindet 10 stringverarbeitung 11 studierende 15 studierenden 8 team 14 teamfaehigkeit 9 teil 4 teilen 7 teilnehmenden 4 testierungssystem 5 testwettbewerb 14 uhr 12 um 11 uns 14 veranstalter 4 veranstaltung 10 von 4 weltmeisterschaft 9 wettbewerb 5 wettbewerbs 1 wichtige 15 wieder 10 wir 3 wird 13 zb 13 zeitmanagement 5 zu 9 zurueckgewiesene 4 zwar 15 10 782883463381 1 8671 6465731 637877861 88567857631 5553682276351 22431 78641 222831 126 ab 2 acm 9 allen 11 aller 2 alljaehrlich 13 an 3 anerkannt 6 angerechnet 5 antreten 9 atlanta 2 aufgaben 8 ausgerichtet 12 ausschlag 13 automatisches 10 beginnt 3 begruessung 6 beiden 14 besten 4 bis 13 bitten 2 darmstaedter 15 das 15 dass 8 den 15 des 1 deutschland 9 die 2 diese 2 dreierteams 4 durfte 3 eigentlichen 6 eine 2 einem 1 einen 1 einer 15 eines 13 entscheidet 2 erfolg 14 erreichen 3 es 1 etwa 13 fachbereich 1 firma 8 for 4 frankfurter 9 gaertner 12 gegeneinander 15 gestellten 13 gewinnen 1 gewinnt 12 gleichstand 8 groessten 7 grossbritannien 10 hahn 1 hilfe 15 hinzuweisen 3 ihre 3 im 3 informatik 13 internationalen 12 jahr 15 kleinen 11 kniffliger 10 koennen 7 konnte 8 kontakt 13 korrekt 12 kurzer 10 lokaler 4 machinery 6 maerz 2 meisten 9 muessen 15 nachmittags 15 nicht 1 nimmt 4 november 6 ob 11 oder 10 programm 12 programmieraufgaben 7 qualifizieren 15 rechner 9 rechners 2 redaktionen 6 reihe 11 rolle 10 runde 5 samstag 3 schnuppern 12 sich 7 skandinavien 11 spannenden 8 spielen 12 sporthalle 3 stammen 14 startschuss 6 stattfindet 10 strafminuten 2 strasse 9 stringverarbeitung 11 studierende 15 stunden 1 teamfaehigkeit 9 teams 9 teil 4 teilen 7 teilnehmer 10 tel 12 testierungssystem 5 veranstalter 4 verbuchen 13 viele 7 vom 15 welttitelkaempfen 6 werden 6 wettbewerbs 1 wettkampfatmosphaere 15 wird 13 wuerden 15 zb 13 zeit 1 zu 9 zum 12 zur 3 zurueckgewiesene 4 30 55871 1 27843233576841 3668877481 73351 1 2363581 258453233661 25467248281 67357453856361 1 7383551 553221 5421 325551 441 44698934731 58667874282351 3431 31 432288536844481 778478561 4671 22287641 84438224826461 41 82383471 221 864365361 445328785821
Scenario #1: s su sup supe superh he ide ideaScenario #2: p pr pro prog progr progra programn ne newg in intc co con cont anoth anothe anotherp pr MANUALLY MANUALLYScenario #3: g ge gew gewe gewelg ge hel hell hellor ru rub rubm rubma rubmar rubmari rubmarin rubmariner ru rup rupe ruperr ru rup suri surin suringr ru sue sues suesd suesda suesdayScenario #4: s MANUALLYk ko MANUALLY MANUALLY MANUALLY MANUALLYk kr kry kryp krypt krypto kryptog kryptogr kryptogra kryptograpd da dab fach fachb fachbem meb be ber best beste besteh bestehe bestehen bestehend bestehende bestehendend de ders st str MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLYb be ber best beste MANUALLYScenario #5: d MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLYa be bei beidt MANUALLY MANUALLY MANUALLY MANUALLY MANUALLYm MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLYm MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLYk ko MANUALLY MANUALLY MANUALLY MANUALLYm me MANUALLYm mo MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLYa an com comp MANUALLY MANUALLY MANUALLYg ge MANUALLY MANUALLY MANUALLYd MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLYm nas sp pro prog progr progra programmk ko koe loes MANUALLY MANUALLYt MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLYd de MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLYagd ei ein eine einerd em for MANUALLYs sa MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLYm mi nic nich nichtg ge gegs sp spi spie spiel spiele spielend da MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLYScenario #6: s st sta stat statt stattf stattfi stattfin stattfind stattfinde stattfindett un unsm ni nim MANUALLY MANUALLY MANUALLYm od MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLYt MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLYk MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLYb ac ach MANUALLYs st MANUALLY MANUALLYb ac MANUALLY MANUALLY MANUALLYScenario #7: k kl MANUALLY MANUALLYa MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLYd fo MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLYs re red MANUALLYa be MANUALLY MANUALLY MANUALLY MANUALLYa al MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLYa al MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLYm MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLYs re MANUALLY MANUALLY MANUALLY MANUALLYk kl kle MANUALLY MANUALLYk MANUALLY MANUALLYd da MANUALLY MANUALLY MANUALLYg hig hi hin hinz hinzu hinzuw hinzuwe hinzuwei hinzuweis hinzuweisek ku MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLYd ei diedg ge MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLYs sp MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLYg in MANUALLYa ac MANUALLY MANUALLY MANUALLY MANUALLY MANUALLYt vi MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLYgt MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLYa act vo MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLYg hi hil hilf MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY MANUALLY
