很久没更新了，题刷了不少，但是一直没怎么总结先贴一篇
1 /*
2 * SOUR:pku 1451
3 * ALGO:trie
4 * DATE: 2009年 08月 17日 星期一 13:29:46 CST
5 * COMM:3
6 * */
7 #include<iostream>
8 #include<cstdio>
9 #include<cstdlib>
10 #include<cstring>
11 #include<algorithm>
12 using namespace std;
13 #define inf 0x7fffffff
14 #define debug 1
15 const int N = 1000 * 11;
16 int mov[10][5] =
17 { {-1}, {-1}, {0, 1, 2, -1}, {3, 4, 5, -1}, {6, 7, 8, -1}, {9, 10, 11, -1},
18 {12, 13, 14, -1}, {15, 16, 17, 18, -1}, {19, 20, 21, -1}, {22, 23, 24, 25, -1}
19 };
20
21 struct Trie {
22 int c;
23 Trie *next[26];
24 Trie() {
25 c = 0;
26 memset(next, 0, sizeof(next));
27 }
28 void insert(char *s, int f);
29 void getMax(char *s, int step, int len);
30 } *root, pool[N];
31 int pt;
32 void Trie::insert(char *s, int f)
33 {
34 c += f;
35 if (*s == 0)
36 return;
37 if (next[*s - 'a'] == NULL) {
38 next[*s - 'a'] = &pool[pt++];
39 }
40 next[*s - 'a']->insert(s + 1, f);
41 }
42
43 char tmp[61], res[61];
44 int freq;
45 void Trie::getMax(char *s, int step, int len)
46 {
47 if (step >= len) {
48 tmp[len] = 0;
49 if (c > freq) {
50 //strcpy(res, tmp);
51 for (int i = 0; i <= len; i++) {
52 res[i] = tmp[i];
53 }
54 freq = c;
55 }
56 return;
57 }
58
59 int idx;
60 for (int i = 0; mov[*s - '0'][i] >= 0; i++) {
61 idx = mov[*s - '0'][i];
62 if (next[idx] != NULL) {
63 tmp[step] = idx + 'a';
64 next[idx]->getMax(s + 1, step + 1, len);
65 }
66 }
67 }
68
69 int main()
70 {
71 int i, k, C, D, f;
72 char buf[30];
73 scanf("%d", &C);
74 for (k = 1; k <= C; k++) {
75 root = &pool[0];
76 pt = 1, memset(pool, 0, sizeof(pool));
77 printf("Scenario #%d:\n", k);
78 scanf("%d", &D);
79 while (D-- > 0) {
80 scanf("%s %d", buf, &f); //哥一开始buf开小了，报了stack smashing 。。。。。。。。
81 root->insert(buf, f);
82 }
83 scanf("%d", &D), getchar();
84 while (D-- > 0) {
85 scanf("%s", buf);
86 buf[strlen(buf) - 1] = 0;
87
88 int len = strlen(buf);
89 for (i = 1; i <= len; i++) {
90 freq = 0;
91 root->getMax(buf, 0, i);
92 if (freq > 0) {
93 printf("%s\n", res);
94 } else {
95 puts("MANUALLY");
96 }
97 }
98 printf("\n");
99 }
100 printf("\n");
101 }
102 return 0;
103 }
104