魔咒词典
Time Limit: 8000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 9735 Accepted Submission(s): 2499
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?
开始用map,怎么弄都超内存了。
/* HDU 1880 字符串映射? */ #include<iostream> #include<stdio.h> #include<string> #include<map> using namespace std; map<string,string> mm; string s1; char str1[21],str2[81]; int main() { int n,k,i; // freopen("test.txt","r",stdin); while(scanf("%s",str1)) { if(str1[0]=='@') break; getchar(); gets(str2); //cout<<str1<<"???"<<str2<<"**"<<endl; mm[str1]=str2; mm[str2]=str1; } scanf("%d",&n);getchar(); while(n--) { gets(str2); if(mm.find(str2)==mm.end()) { cout<<"what?"<<endl; } else { s1=mm[str2]; //cout<<s2<<endl; if(s1[0]=='[') s1=s1.substr(1,s1.length()-2); cout<<s1<<endl; } } return 0; }
后来看别人的代码 借的快排+二分
#include"stdio.h" #include"string.h" #include"stdlib.h" #define N 100001 struct A { char str[21]; int index; }ss1[N]; struct B { char str[81]; int index; }ss2[N]; int z; int cmp1(const void *a,const void *b) { A *c,*d; c=(A *)a; d=(A *)b; return strcmp(c->str,d->str); } int cmp2(const void *a,const void *b) { B *c,*d; c=(B *)a; d=(B *)b; return strcmp(c->str,d->str); } int main() { int j,k,i,flag,temp,low,mid,up,n;; char str[105],str1[105],str2[105]; // freopen("test.txt","r",stdin); z=0; while(gets(str),strcmp(str,"@END@")) { for(j=0,k=1;str[k]!=']';k++,j++) str1[j]=str[k]; str1[j]='\0'; for(j=0,k+=2;str[k];k++,j++) str2[j]=str[k]; str2[j]='\0'; strcpy(ss1[z].str,str1); strcpy(ss2[z].str,str2); ss1[z].index=z; ss2[z].index=z; z++; } qsort(ss1,z,sizeof(ss1[0]),cmp1); for(i=0;i<z;i++) ss2[ss1[i].index].index=i; qsort(ss2,z,sizeof(ss2[0]),cmp2); for(i=0;i<z;i++) ss1[ss2[i].index].index=i; scanf("%d",&n); getchar(); while(n--) { flag=0; gets(str); if(str[0]=='[') { flag=1; for(j=0,k=1;str[k]!=']';k++,j++) str[j]=str[k]; str[j]='\0'; } low=0;up=z-1; mid=(low+up)/2; if(flag) { while(low<=up) { temp=strcmp(str,ss1[mid].str); if(temp>0) low=mid+1; else up=mid-1; mid=(low+up)/2; } if(strcmp(ss1[low].str,str)==0) printf("%s\n",ss2[ss1[low].index].str); else printf("what?\n"); } else { while(low<=up) { temp=strcmp(str,ss2[mid].str); if(temp>0) low=mid+1; else up=mid-1; mid=(low+up)/2; } if(strcmp(ss2[low].str,str)==0) printf("%s\n",ss1[ss2[low].index].str); else printf("what?\n"); } } return 0; }