ZJM 与霍格沃兹（字符串哈希）测试龙征天的博客-

问题描述

ZJM 为了准备霍格沃兹的期末考试，决心背魔咒词典，一举拿下咒语翻译题
题库格式：[魔咒] 对应功能
背完题库后，ZJM 开始刷题，现共有 N 道题，每道题给出一个字符串，可能是 [魔咒]，也可能是对应功能
ZJM 需要识别这个题目给出的是 [魔咒] 还是对应功能，并写出转换的结果，如果在魔咒词典里找不到，输出 “what?”

Input

首先列出魔咒词典中不超过100000条不同的咒语，每条格式为：

[魔咒] 对应功能

其中“魔咒”和“对应功能”分别为长度不超过20和80的字符串，字符串中保证不包含字符“[”和“]”，且“]”和后面的字符串之间有且仅有一个空格。魔咒词典最后一行以“@END@”结束，这一行不属于词典中的词条。
词典之后的一行包含正整数N（<=1000），随后是N个测试用例。每个测试用例占一行，或者给出“[魔咒]”，或者给出“对应功能”。

Output

每个测试用例的输出占一行，输出魔咒对应的功能，或者功能对应的魔咒。如果在词典中查不到，就输出“what?”

Sample input

[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 

Sample output

light the wand accio what? what? 

解题思路

这个题为了卡空间，真的太狠了。首先，最基本的map<string,string>是绝对不可能过的。一定要用字符串哈希。我是用的unsigned int自然溢出处理的。最后map使用map<unsigned,int>就可以了。

对于这道题，我们建立两个map<unsigned,int>，unsigned对应的是字符串的哈希值，int对应的是这个字符串存储的位置。然后查找的时候直接将要查找的字符串哈希一下，看看int是否为0即可，如果是0，就是找不到，否则就去存储咒语 / 对应功能的数组里面找。

但是，如果你用了字符串哈希，你存储咒语和对应功能的数组是用的string[maxn]，那么也会MLE。所以你必须使用两个二维char来存。

最后，我还是wa了，然后把seed从131改成17就过了。。。哈希的风险第一次做题就碰到了，爱了爱了。 我错了，不是seed的问题，我开始的hash函数有一点错误，改正后131也能过。

完整代码

//#pragma GCC optimize(2) //#pragma G++ optimize(2) #include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <string> #include <climits> #include <algorithm> #include <queue> #include <vector> #include <map> using namespace std; const int maxn=1000000+10; char s1[maxn][25],s2[maxn][85]; int cnt; map<unsigned,int> mp; unsigned hashstring(string _s){//BKDR哈希 unsigned int seed=17,_hash=0; for (int i=0; i<_s.size(); i++)         _hash=_hash*seed+(unsigned)(_s[i]); return _hash; } void split(string _s){     string _s1,_s2; for (int i=1; i<_s.size(); i++){ if(_s[i]==']'){             _s1=_s2;             _s2.clear();             i++; continue; }         _s2+=_s[i]; }     cnt++;     mp[hashstring(_s1)]=cnt; strcpy(s1[cnt],_s1.c_str());     mp[hashstring(_s2)]=cnt; strcpy(s2[cnt],_s2.c_str()); } void find(string _s){ if(_s[0]=='['){         string snew; snew.clear(); for (int i=1; i<_s.size()-1; i++)             snew+=_s[i]; unsigned _hash=hashstring(snew); if(mp[_hash]==0){ printf("what?n"); return; } printf("%sn",s2[mp[_hash]]); return; } else { unsigned _hash=hashstring(_s); if(mp[_hash]==0){ printf("what?n"); return; } printf("%sn",s1[mp[_hash]]); return; } } int getint(){ int x=0,s=1; char ch=' '; while(ch<'0' || ch>'9'){ ch=getchar(); if(ch=='-') s=-1;} while(ch>='0' && ch<='9'){ x=x*10+ch-'0'; ch=getchar();} return x*s; } int main(){ //ios::sync_with_stdio(false); //cin.tie(0); while(true){         string s; getline(cin,s); if(s=="@END@") break; split(s); } int n; scanf("%d",&n); getchar(); while(n--){         string s; getline(cin,s); find(s); } return 0; }