hdu 1880 魔咒字典

https://vjudge.net/problem/HDU-1880

题意：略

思路：

一开始就是想到了正确的思路，但是代码写炸了，死活过不了。这题嘛，就是建议一个魔咒与咒语的双向映射。首先用字符串hash将魔咒与咒语的hash值给算出来，之后用两个map保存魔咒的hash与魔咒下标，咒语的hash与咒语的下标。hash用的是优秀的bkdr算法，好写而且不容易冲突。最后查询的时候有一个技巧，就是如果说以’[‘开头，那么肯定是魔咒，就输出咒语，反之输出魔咒。一开始确实是没有想到如果说魔咒的hash和咒语的hash冲突了怎么办，那么就用上面所说的那个技巧就可以完美解决。

代码：

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <map>
 4 using namespace std;
 5 
 6 const int maxn = 100005;
 7 int num = 0;
 8 
 9 char mz[maxn][50];
10 char zy[maxn][100];
11 
12 map<int,int> mpmz,mpzy;
13 
14 unsigned int myhash(char* s)
15 {
16     unsigned int seed = 131;
17     unsigned int h = 0;
18 
19     while (*s)
20     {
21         h = h * seed + (*s++);
22     }
23 
24     return (h & 0x7FFFFFFF);
25 }
26 
27 void init(void)
28 {
29     for (int i = 1;i < num;i++)
30     {
31         mpmz[myhash(mz[i])] = i;
32         mpzy[myhash(zy[i])] = i;
33 
34         //printf("%d**
",myhash(mz[num]));
35         //printf("%d**
",myhash(zy[num]));
36     }
37 }
38 
39 int main()
40 {
41     num = 1;
42 
43     while (1)
44     {
45         scanf("%s",mz[num]);
46 
47         if (mz[num][0] == '@') break;
48 
49         getchar();
50 
51         gets(zy[num]);
52 
53         //printf("%s$$
",zy[num]);
54 
55         num++;
56     }
57 
58     init();
59 
60     int n;
61 
62     scanf("%d",&n);
63 
64     getchar();
65 
66     while (n--)
67     {
68         char t[100];
69 
70         gets(t);
71 
72         if (t[0] == '[')
73         {
74             int tmp = mpmz[myhash(t)];
75 
76             //printf("%d**
",myhash(t));
77 
78             if (tmp == 0) printf("%s
","what?");
79             else printf("%s
",zy[tmp]);
80         }
81         else
82         {
83             int tmp = mpzy[myhash(t)];
84 
85             //printf("%d**
",tmp);
86 
87             if (tmp == 0) printf("%s
","what?");
88             else
89             {
90                 for (int j = 1;j < strlen(mz[tmp]) - 1;j++)
91                     printf("%c",mz[tmp][j]);
92 
93                 printf("
");
94             }
95         }
96     }
97 
98     return 0;
99 }