Problem Description
哈利波特在魔法学校的必修课之一就是学习魔咒。据说魔法世界有100000种不同的魔咒，哈利很难全部记住，但是为了对抗强敌，他必须在危急时刻能够调用任何一个需要的魔咒，所以他需要你的帮助。
给你一部魔咒词典。当哈利听到一个魔咒时，你的程序必须告诉他那个魔咒的功能；当哈利需要某个功能但不知道该用什么魔咒时，你的程序要替他找到相应的魔咒。如果他要的魔咒不在词典中，就输出“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?
Author
ZJU
真的是模板题啊。。直接套模板就好了。。。。处理的时候，因为存储的时候用2位2位的存，取相邻的对应的字符串地址就可以直接用 h(id^1)位运算来做了。。但要注意是需要从0或偶数位置开始记录。
/*
* @author ipqhjjybj
* @date 20130703
*
*/ #include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime> #include <iostream>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <utility> #include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <string>
using namespace std; #define inf 0x3f3f3f3f
#define MAXN 210000
#define MOD 100007
#define clr(x,k) memset((x),(k),sizeof(x))
#define clrn(x,k) memset((x),(k),(n+1)*sizeof(int))
#define cpy(x,k) memcpy((x),(k),sizeof(x))
#define Base 10000 typedef vector<int> vi;
typedef stack<int> si;
typedef vector<string> vs;
#define sz(a) int((a).size())
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define rep(i,n) for(int i = 0;i < n;++i)
#define foreach(it,c) for(vi::iterator it = (c).begin();it != (c).end();++it) #define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b)) struct node{
node* next;
char s[81];
}hash[MAXN],*h[MOD],*cur; //hash指哈系值跟字符串的对应。 h[mod]是记录的存放的地址.
int n;
/// @brief BKDR Hash Function
/// @detail 本 算法由于在Brian Kernighan与Dennis Ritchie的《The C Programming Language》一书被展示而得 名，是一种简单快捷的hash算法，也是Java目前采用的字符串的Hash算法（累乘因子为31）。
template<class T>
size_t BKDRHash(const T *str)
{
register size_t hash = 0;
while (size_t ch = (size_t)*str++)
{
hash = hash * 131 + ch;
}
return (hash&0x7fffffff)%MOD;
}
int getID(const char* s){
int code = BKDRHash(s);
node * p = h[code];
while(p){
if(!strcmp(p->s,s))
return p-hash;
else
p=p->next;
}
strcpy(cur->s,s);
cur->next=h[code]; //移到了next里.
h[code]=cur++;
return cur-1-hash;
}
int find(const char *s){
int code=BKDRHash(s);
node *p=h[code];
while(p){
if(!strcmp(s,p->s))
return p-hash;
else p=p->next;
}
return -1;
}
int main(){
// freopen("1080.in","r",stdin);
char s[100],*p;
int id;
cur=hash;
clr(h,0);
while(scanf("%s",s)&&s[0]!='@'){
getID(s);
getchar();
gets(s);
getID(s);
}
scanf("%d",&n);getchar();
while(n--){
gets(s);
id=find(s);
if(id==-1){
puts("what?");
continue;
}
p = hash[id^1].s;
if(p[0]!='['){
puts(p);
}else{
while(*(++p) != ']')
putchar(*p);
printf("\n");
}
}
return 0;
}