哈利波特在魔法学校的必修课之一就是学习魔咒。据说魔法世界有100000种不同的魔咒，哈利很难全部记住，但是为了对抗强敌，他必须在危急时刻能够调用任何一个需要的魔咒，所以他需要你的帮助。
给你一部魔咒词典。当哈利听到一个魔咒时，你的程序必须告诉他那个魔咒的功能；当哈利需要某个功能但不知道该用什么魔咒时，你的程序要替他找到相应的魔咒。如果他要的魔咒不在词典中，就输出“what?”
首先列出词典中不超过100000条不同的魔咒词条，每条格式为：
[魔咒] 对应功能
其中“魔咒”和“对应功能”分别为长度不超过20和80的字符串，字符串中保证不包含字符“[”和“]”，且“]”和后面的字符串之间有且仅有一个空格。词典最后一行以“@END@”结束，这一行不属于词典中的词条。
词典之后的一行包含正整数N（<=1000），随后是N个测试用例。每个测试用例占一行，或者给出“[魔咒]”，或者给出“对应功能”。
每个测试用例的输出占一行，输出魔咒对应的功能，或者功能对应的魔咒。如果魔咒不在词典中，就输出“what?”
以下借鉴了几位网友的思路和代码
[expelliarmus] the disarming charm
[rictusempra] send a jet of silver light to hit the enemy
[tarantallegra] control the movement of one's legs
[serpensortia] shoot a snake out of the end of one's wand
[lumos] light the wand
[obliviate] the memory charm
[expecto patronum] send a Patronus to the dementors
[accio] the summoning charm
@END@
4
[lumos]
the summoning charm
[arha]
take me to the sky
light the wand
accio
what?
what? 使用stl当中的map将对应的字符串建立一一映射。
代码如下:
1 #include<iostream>
2 #include<string>
3 #include<algorithm>
4 #include<cstdio>
5 #include<cstring>
6 #include<cmath>
7 #include<map>
8 using namespace std;
9 int main()
10 {
11 map<string,string>a;
12 int n,l,r;
13 string s,index,value;
14 while(getline(cin,s) && s!="@END@")
15 {
16 l=s.find('[');r=s.find(']');//找出左右括号所处的下表
17 index=s.substr(l+1,r-l-1);//在字符串中提取出魔咒，具体怎么计算的，可以自己选个测试用例在草稿纸上画画便一目了然
18 value=s.substr(r+2,s.size()-r);//提取出魔咒对应的内容
19 a[index]=value;//将魔咒作为索引
20 a[value]=index;//将内容作为索引
21 }
22 cin>>n;getline(cin,s);//读取走缓冲区中讨厌的回车键
23 for(int i=0;i<n;i++)
24 {
25 getline(cin,s);
26 if(s[0]=='[')
27 {
28 s.erase(s.size()-1,1);//如果以魔咒为索引，就把讨厌的左右中括号去掉
29 s.erase(0,1);
30 }
31 if(a.find(s)==a.end()) cout<<"what?"<<endl;//判断在map里是否有这个索引
32 else cout<<a[s]<<endl;
33 }
34 return 0;
35 }
题解：如果数据量小，每个字符串的长度小的话，直接使用map<string,string>轻松解决，但是数据量大，字符串的长度可能很长，这样会造成超时和超内存的问题，因此使用字符串hash和映射解决
1 #include<iostream>
2 #include<string>
3 #include<map>
4 #include<utility>
5
6 using namespace std;
7 typedef unsigned long long ull;
8 const int N=200010;
9 const ull p=1e9+13;
10 const ull mod=1e9+7;
11 string a[N];
12 map<ull,int>d;
13
14 ull hashstr(string s) //hash函数
15 {
16 ull v=0;
17 for(int i=0;s[i];i++)
18 v=(v*p+(int)s[i])%mod;
19 return v;
20 }
21
22 int main()
23 {
24 int k=0,n;
25 for(;;){
26 string s1,s2,s;
27 getline(cin,s);
28 int p1=s.find("[",0);
29 int p2=s.find("] ",p1+1);
30 if(p1==string::npos||p2==string::npos)
31 break;
32 s1=s.substr(p1+1,p2-p1-1);//s1为名字
33 s2=s.substr(p2+2);//s2为功能
34 a[++k]=s1;
35 ull v=hashstr(s2);
36 d.insert(make_pair(v,k));
37 a[++k]=s2;
38 v=hashstr(s1);
39 d.insert(make_pair(v,k));
40 }
41 scanf("%d",&n);
42 getchar();
43 for(int i=1;i<=n;i++){
44 string s;
45 getline(cin,s);
46 if(s[0]=='['){
47 s.erase(s.end()-1);
48 s.erase(s.begin());
49 }
50 ull v=hashstr(s);
51 if(d.find(v)!=d.end()){
52 int pos=(d.find(v))->second;;
53 cout<<a[pos]<<endl;
54 }
55 else
56 cout<<"what?"<<endl;
57 }
58 return 0;
59 }
思路
模拟赛上拉的题目，意思很简单，给你多行“【咒语】功能”以“@END@”结尾，最后输入字符串查询，要求输入的如果是功能输出咒语，如果是咒语输出功能，都不存在则输出“what？”，首先想到的就是直接用map映射但是数据量太大有10w想着肯定会超内存，就没有用后来想到用Hash+二分快速查找，但是没学会字符串Hash无奈只能对着字符串进行二分查找结果浪费很多时间还wa掉了，后来看榜单发现大家基本都写出来了，就猜肯定是hd数据弱果断暴力遍历着查找，虽然在数组范围上坑了几次，最后还是AC，果然是弱数据。赛完就赶紧学了字符串Hash把我比赛中没实现的想法给实现了，效率果然比暴力高了很多。就是将每一个串Hash一个值（这里用BKDRHash是java用的Hash算法可以达到10W数据无冲突hash值是32位整数），用结构体将这个Hash值与字符串的位置对应起来，来达到随机读取的目的，把输入的字典全部Hash后将这些Hash值排序，方便二分查找。
PS：后来有找来了几个10W的数据结果果断wa掉，看来不解决Hash冲突还是不行的，可能真的是hd数据水的没有冲突把，或者后来找到数据专门对几个Hash算法进行的针对，看来对于大数据的题目还是要解决问题
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <cmath>
5 #include <algorithm>
6 #define N 100005
7 using namespace std;
8 char spell[N][85];//储存功能
9 char magic[N][25];//储存咒语
10 int num=1;
11 struct node//Hash值对应的数组下标
12 {
13 int Hash;
14 int l;
15 } key[N],tail[N];//咒语和功能
16 int cmp(node a,node b)
17 {
18 return a.Hash<b.Hash;//按照Hash排序
19 }
20
21 unsigned int BKDRHash(char *str)//Hash算法
22 {
23 unsigned int seed = 131;
24 unsigned int hash = 0;
25
26 while (*str)
27 {
28 hash = hash * seed + (*str++);
29 }
30 return (hash & 0x7FFFFFFF);
31 }
32 void init()//初始化，计算所有串的Hash值
33 {
34 for(int i=1; i<num; i++)
35 {
36 key[i].Hash=BKDRHash(magic[i]);
37 key[i].l=i;
38 tail[i].Hash=BKDRHash(spell[i]);
39 tail[i].l=i;
40 }
41 sort(key,key+num,cmp);//按照Hash值排序，方便二分查找
42 sort(tail,tail+num,cmp);
43 }
44 int main()
45 {
46
47 while(scanf("%s",magic[num]))
48 {
49 if(!strcmp(magic[num],"@END@"))//终止条件
50 break;
51 getchar();//吞掉空格
52 gets(spell[num++]);//第二个串
53 }
54 init();//初始化
55 int n;
56 scanf("%d",&n);
57 getchar();//吞回车
58 while(n--)//n次查询
59 {
60 node tmp;
61 char str[120];
62 gets(str);
63 if(str[0]=='[')//是咒语
64 {
65 tmp.Hash=BKDRHash(str);//计算Hsah值
66 int mid=lower_bound(key,key+num,tmp,cmp)-key;二分查找位置（如果没找到，返回值为假设这个值存在应该在的位置）
67 if(key[mid].Hash!=tmp.Hash)//比较两者是否相同（是否存在）
68 printf("what?\n");
69 else
70 printf("%s\n",spell[key[mid].l]);//输出
71 }
72 else
73 {
74 tmp.Hash=BKDRHash(str);
75 int mid=lower_bound(tail,tail+num,tmp,cmp)-tail;
76 if(tail[mid].Hash!=tmp.Hash)
77 printf("what?\n");
78 else
79 {
80 int l=strlen(magic[tail[mid].l]);//处理咒语两边的方括号
81 magic[tail[mid].l][l-1]=0;
82 printf("%s\n",magic[tail[mid].l]+1);
83 }
84 }
85 }
86 return 0;
87 }
分析：
此题其实就是字符串哈希的模板题，将字符串s1映射到s2,输入s1求s2,输入s2求s1
第一反应是用STL，但此题用map会MLE或TLE，所以手写哈希表
字符串哈希的方法如下：
1.将前8位字母的ASCII码乘积作为key(用long long存），转换为数字的哈希问题
2.用数组和链表存储，key对应的字符串存在数组下标为key%c(c为常数）的地方
若key%c相同，则存在链表里,下图直观展示了该过程(图中数字为key) 
3.查找时先到key对应的数组，如果元素不对，则继续遍历链表，直到查到该元素
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 using namespace std;
5 const int c=10000;
6 struct myhash{//评测机上hash是关键字
7 struct node {
8 long long key;//若key%c相同辅助判重
9 string s1;//若key相同辅助判重
10 string s2;//要查找的东西,字符串s1对应的字符串s2
11 node* next;//链表用指针
12 }a[c+5];
13 void push(long long x,string s1,string s2) {//插入函数
14 if(a[x%c].key==0) {//如果数组x%c处没有元素，直接插入
15 a[x%c].key=x;
16 a[x%c].s1=s1;
17 a[x%c].s2=s2;
18 } else {//如果有，链表插入新节点（头插入）
19 node *tmp=new node();
20 tmp->key=x;
21 tmp->s1=s1;
22 tmp->s2=s2;
23 tmp->next=a[x%c].next;//此处相当于head
24 a[x%c].next=tmp;
25 }
26 }
27 string found(long long x,string s1) {//查找函数
28 if(a[x%c].key==x&&a[x%c].s1==s1) return a[x%c].s2;//如果字符串在数组里，直接返回对应的字符串s2
29 if(a[x%c].key==0) return "what?";//如果数组里没有元素，链表里肯定也没有，返回what?
30 else {
31 node* tmp=a[x%c].next;//遍历链表查找
32 while(tmp!=NULL) {
33 if(tmp->key==x&&tmp->s1==s1) return tmp->s2;
34 tmp=tmp->next;
35 }
36 return "what?";
37 }
38 }
39 };
40 myhash H1,H2;//H1存储名字对应的内容，H2存储内容对应的名字
41 long long to_num(string str){//前8位的乘积hash
42 long long ans=1;
43 int len=str.length();
44 if(len>8) len=8;
45 for(int i=0;i<len;i++) ans*=str[i];
46 return ans;
47 }
48 int main() {
49 int t;
50 string str,s1,s2;
51 while(1) {
52 int i;
53 getline(cin,str);//有空格，必须用getline
54 if(str=="@END@") break;
55 for(i=0; i<str.length(); i++) {
56 if(str[i]==']') break;//找到咒语名字和内容的分界点
57 }
58 s1=str.substr(0,i+1);
59 s2=str.substr(i+2,str.length()-i-1);
60 //将str分为两部分，s1是名字，s2是内容
61 H1.push(to_num(s1),s1,s2);
62 H2.push(to_num(s2),s2,s1);
63 }
64 cin>>t;
65 getchar();//输入一个换行符，否则换行符会被getline读入到str中,导致在哈希表中查找'\n'，多输出一个"what?"
66 while(t--){
67 getline(cin,str);
68 bool have_kuo=false;//区分输入的是内容还是名字
69 for(int i=0;i<str.length();i++){
70 if(str[i]==']'){
71 have_kuo=true;
72 break;
73 }
74 }
75 string tmp;
76 if(have_kuo) tmp=H1.found(to_num(str),str);
77 else tmp=H2.found(to_num(str),str);
78 if(tmp[0]=='['){
79 for(int i=1;i<tmp.length()-1;i++) cout<<tmp[i];//输出咒语名字时不带括号
80 cout<<endl;
81 }
82 else cout<<tmp<<endl;
83 }
84 }
转载于:https://www.cnblogs.com/jiamian/p/10634151.html