題目描述： 哈利波特在魔法學校的必修課之一就是學習魔咒。據說魔法世界有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?來源： 2008年浙江大學計算機及軟件工程研究生機試真題 [cpp] /********************************* * 日期：2013-2-18 * 作者：SJF0115 * 題號: 九度OJ 題目1029：魔咒詞典 * 來源：http://ac.jobdu.com/problem.php?pid=1029 * 結果：AC * 來源：2008年浙江大學計算機及軟件工程研究生機試真題 * 總結： **********************************/ #include<map> #include<string> #include<iostream> #include<string.h> #include <stdio.h> using namespace std; map<string,string> Map; int Function(string str){ int len=str.length(); int i; for(i = 0;i < len;i++) { if(str[i]==']') { break; } } //魔咒 string s1 = str.substr(0,i+1); //對應功能 string s2 = str.substr(i+2,len-i-2); //存儲在Map中 Map[s1] = s2; Map[s2] = s1; return 0; } int main() { char s[105]; int n,i; string str; //輸入數據 while(gets(s)){ str = s; if(str == "@END@") { break; } //分割魔咒及其對應功能 Function(str); } scanf("%d\n",&n); for(i = 0;i < n;i++){ gets(s); str = s; //尋找魔咒或者對應功能 if(Map.find(str) == Map.end()) { printf("what?\n"); } else { str = Map[str]; //輸出對應的功能 if(str[0] != '[') { cout<<str<<endl; } //輸出對應的魔咒 else { cout<<str.substr(1,str.length()-2)<<endl; } } }//for return 0; } /********************************* * 日期：2013-2-18 * 作者：SJF0115 * 題號: 九度OJ 題目1029：魔咒詞典 * 來源：http://ac.jobdu.com/problem.php?pid=1029 * 結果：AC * 來源：2008年浙江大學計算機及軟件工程研究生機試真題 * 總結： **********************************/ #include<map> #include<string> #include<iostream> #include<string.h> #include <stdio.h> using namespace std; map<string,string> Map; int Function(string str){ int len=str.length(); int i; for(i = 0;i < len;i++) { if(str[i]==']') { break; } } //魔咒 string s1 = str.substr(0,i+1); //對應功能 string s2 = str.substr(i+2,len-i-2); //存儲在Map中 Map[s1] = s2; Map[s2] = s1; return 0; } int main() { char s[105]; int n,i; string str; //輸入數據 while(gets(s)){ str = s; if(str == "@END@") { break; } //分割魔咒及其對應功能 Function(str); } scanf("%d\n",&n); for(i = 0;i < n;i++){ gets(s); str = s; //尋找魔咒或者對應功能 if(Map.find(str) == Map.end()) { printf("what?\n"); } else { str = Map[str]; //輸出對應的功能 if(str[0] != '[') { cout<<str<<endl; } //輸出對應的魔咒 else { cout<<str.substr(1,str.length()-2)<<endl; } } }//for return 0; }轉載 [cpp] #include <stdio.h> #include <string.h> #include <stdlib.h> struct dic { char wo[22]; char ex[82]; }a[10000],b[10000]; int cmp1(const void *a,const void *b) { return strcmp((*(struct dic *)a).wo,(*(struct dic *)b).wo); } int cmp2(const void *a,const void *b) { return strcmp((*(struct dic *)a).ex,(*(struct dic *)b).ex); } int main() { int i,k; int n,high,low,mid,tmp,ans; char s[104],c[82]; k=0; while(gets(s)&&strcmp(s,"@END@")) { int j=0; i=1; while(s[i]!=']') { a[k].wo[j]=s[i]; b[k].wo[j]=s[i]; j++; i++; } a[k].wo[j+1]='\0'; b[k].wo[j+1]='\0'; if(s[i]==']') i+=2; j=0; while(s[i]!='\0') { a[k].ex[j]=s[i]; b[k].ex[j]=s[i]; j++; i++; } a[k].ex[j+1]='\0'; b[k].ex[j+1]='\0'; k++; } qsort(a,k,sizeof(a[0]),cmp1); qsort(b,k,sizeof(b[0]),cmp2); scanf("%d",&n); getchar(); while(n--) { gets(c); ans=-1; low=0;high=k-1; if(c[0]=='[') { int len; len=strlen(c); for(i=0;i<len-2;i++) c[i]=c[i+1]; c[i]='\0'; while(low<=high) { mid=(low+high)/2; tmp=strcmp(c,a[mid].wo); if (tmp==0) {ans=mid;break;} else if(tmp>0) low=mid+1; else high=mid-1; } if(ans==-1) printf("what?\n"); else printf("%s\n",a[ans].ex); } else { while(low<=high) { mid=(low+high)/2; tmp=strcmp(c,b[mid].ex); if (tmp==0) {ans=mid;break;} else if(tmp>0) low=mid+1; else high=mid-1; } if(ans==-1) printf("what?\n"); else printf("%s\n",b[ans].wo); } } return 0; } #include <stdio.h> #include <string.h> #include <stdlib.h> struct dic { char wo[22]; char ex[82]; }a[10000],b[10000]; int cmp1(const void *a,const void *b) { return strcmp((*(struct dic *)a).wo,(*(struct dic *)b).wo); } int cmp2(const void *a,const void *b) { return strcmp((*(struct dic *)a).ex,(*(struct dic *)b).ex); } int main() { int i,k; int n,high,low,mid,tmp,ans; char s[104],c[82]; k=0; while(gets(s)&&strcmp(s,"@END@")) { int j=0; i=1; while(s[i]!=']') { a[k].wo[j]=s[i]; b[k].wo[j]=s[i]; j++; i++; } a[k].wo[j+1]='\0'; b[k].wo[j+1]='\0'; if(s[i]==']') i+=2; j=0; while(s[i]!='\0') { a[k].ex[j]=s[i]; b[k].ex[j]=s[i]; j++; i++; } a[k].ex[j+1]='\0'; b[k].ex[j+1]='\0'; k++; } qsort(a,k,sizeof(a[0]),cmp1); qsort(b,k,sizeof(b[0]),cmp2); scanf("%d",&n); getchar(); while(n--) { gets(c); ans=-1; low=0;high=k-1; if(c[0]=='[') { int len; len=strlen(c); for(i=0;i<len-2;i++) c[i]=c[i+1]; c[i]='\0'; while(low<=high) { mid=(low+high)/2; tmp=strcmp(c,a[mid].wo); if (tmp==0) {ans=mid;break;} else if(tmp>0) low=mid+1; else high=mid-1; } if(ans==-1) printf("what?\n"); else printf("%s\n",a[ans].ex); } else { while(low<=high) { mid=(low+high)/2; tmp=strcmp(c,b[mid].ex); if (tmp==0) {ans=mid;break;} else if(tmp>0) low=mid+1; else high=mid-1; } if(ans==-1) printf("what?\n"); else printf("%s\n",b[ans].wo); } } return 0; } #include<stdio.h> #include<string.h> #include<stdlib.h> typedef struct Str{ char name[22];//魔咒 char function[82];//對應功能 }Str; Str str[10001]; int main() { int n,i,j,index = 0,flag,start,k; char s[104]; //char command[104]; while (gets(s)){ //詞典最後一行以“@END@”結束，這一行不屬於詞典中的詞條 if(s[0] == '@'){ break; } else{ //輸入魔咒 for(i = 0;s[i] != ']';i++){ str[index].name[i] = s[i]; } str[index].name[i++] = ']'; str[index].name[i] = '\0'; //輸入對應功能 start = i+1; for(i = start,k = 0;s[i] != '\n';k++,i++){ str[index].function[k] = s[i]; } str[index].function[k] = '\0'; } index++; }//while scanf("%d\n",&n); for(i = 0;i < n;i++){ gets(s); flag = 0; //輸入的是魔咒輸出對應功能 if(s[0] == '['){ for(j = 0;j < index;j++){ //找到魔咒對應的功能 if(strcmp(s,str[j].name) == 0){ flag = 1; //輸出對應的功能 printf("%s\n",str[j].function); break; } } } //輸入的是魔咒的功能輸出魔咒 else{ for(j = 0;j < index;j++){ //找到對應的魔咒 if(strcmp(s,str[j].function) == 0){ flag = 1; //輸出對應的魔咒 for(k = 1;str[j].name[k] != ']';k++){ printf("%c",str[j].name[k]); } printf("\n"); break; } } } //沒有找到 if(flag == 0){ printf("what?\n"); } } return 0; } #include<stdio.h> #include<string.h> #include<stdlib.h> typedef struct Str{ char name[22];//魔咒 char function[82];//對應功能 }Str; Str str[10001]; int main() { int n,i,j,index = 0,flag,start,k; char s[104]; //char command[104]; while (gets(s)){ //詞典最後一行以“@END@”結束，這一行不屬於詞典中的詞條 if(s[0] == '@'){ break; } else{ //輸入魔咒 for(i = 0;s[i] != ']';i++){ str[index].name[i] = s[i]; } str[index].name[i++] = ']'; str[index].name[i] = '\0'; //輸入對應功能 start = i+1; for(i = start,k = 0;s[i] != '\n';k++,i++){ str[index].function[k] = s[i]; } str[index].function[k] = '\0'; } index++; }//while scanf("%d\n",&n); for(i = 0;i < n;i++){ gets(s); flag = 0; //輸入的是魔咒輸出對應功能 if(s[0] == '['){ for(j = 0;j < index;j++){ //找到魔咒對應的功能 if(strcmp(s,str[j].name) == 0){ flag = 1; //輸出對應的功能 printf("%s\n",str[j].function); break; } } } //輸入的是魔咒的功能輸出魔咒 else{ for(j = 0;j < index;j++){ //找到對應的魔咒 if(strcmp(s,str[j].function) == 0){ flag = 1; //輸出對應的魔咒 for(k = 1;str[j].name[k] != ']';k++){ printf("%c",str[j].name[k]); } printf("\n"); break; } } } //沒有找到 if(flag == 0){ printf("what?\n"); } } return 0; }
