HDU1880 저주 사전(문자열 해시 + 2점)

HDU1880 저주 사전(문자열 해시)
Description 해리포터는 마법 학교에서 필수 과목 중 하나가 주문을 배우는 것이다.마법의 세계에는 10만 가지의 다른 주문이 있다고 한다. 해리는 모두 기억하기는 어렵지만, 강적에 대항하기 위해서는 위급할 때 필요한 주문을 모두 사용해야 하기 때문에 당신의 도움이 필요하다.마주사전 하나 줄게.해리가 주문을 들었을 때, 너의 프로그램은 반드시 그에게 그 주문의 기능을 알려줘야 한다.해리가 어떤 기능을 필요로 하지만 어떤 주문을 써야 할지 모르겠을 때, 당신의 프로그램은 그를 대신해서 그에 상응하는 주문을 찾아야 한다.만약 그가 원하는 주문이 사전에 없다면, "what?"를 출력하십시오.Input은 먼저 사전에서 10만 개를 넘지 않는 서로 다른 저주 단어를 열거했다. 각 격식은 [마주] 대응 기능이고 그 중에서'마주'와'대응 기능'은 각각 길이가 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?
제목의 뜻
사전을 주어 조회 기능을 실현하다.읽은 문자열을 해시 처리한 다음 구조체에 저장해서 정렬하고, 마지막으로 2분 동안 검색하고, 찾으려는 문자열을 출력합니다.찾을 수 없으면 what? 을 출력합니다.

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include 
#include
#include
#define lowbit(x) ((x)&-(x));
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=1e5+10,NN=2e3+10,INF=0x3f3f3f3f;
const ll MOD=1e9+7;
const ull seed=31;
int sum,q;
char str1[N][30],str2[N][90],cnt[100];
struct Node{
	ull num;
	int id;
	bool friend operator<(const Node &a,const Node &b){
		return a.num<b.num;
	}
}Hash1[N],Hash2[N],temp;
ull Hashstr(char *str){
	ull key=0;
	while(*str) key=key*seed+(*str++);
	return key;
}
void init(){
	sum=0;
}
int main(){
	init();
	while(~scanf("%s",str1[++sum])){
		if(str1[sum][0]=='@'){
			--sum;
			break;
		}
		getchar();
		gets(str2[sum]);
		ull key;
		key=Hashstr(str1[sum]);
		Hash1[sum].num=key;
		Hash1[sum].id=sum;
		key=Hashstr(str2[sum]);
		Hash2[sum].num=key;
		Hash2[sum].id=sum;
	}
	sort(Hash1+1,Hash1+sum+1);
	sort(Hash2+1,Hash2+sum+1);
	scanf("%d",&q);
	getchar();
	while(q--){
		gets(cnt);
		if(cnt[0]=='['){
			ull key=Hashstr(cnt);
			temp.num=key;
			int n=lower_bound(Hash1+1,Hash1+sum+1,temp)-Hash1;
			if(Hash1[n].num==key) printf("%s
",str2[Hash1[n].id]);
			else printf("what?
");
		}
		else{
			ull key=Hashstr(cnt);
			temp.num=key;
			int n=lower_bound(Hash2+1,Hash2+sum+1,temp)-Hash2;
			if(Hash2[n].num==key){
				int len=strlen(str1[Hash2[n].id]);
				for(int i=1;i<=len-2;i++) printf("%c",str1[Hash2[n].id][i]);
				puts("");
			}
			else printf("what?
");
		}
	}
}