http://ac.jobdu.com/problem.php?pid=1029魔咒詞典

題目當中每個魔咒用一對括號[? ] 來包含，測試數據在一對括號當中會有空格，這個小問題導致一直是WA，應該首先把一行字符串都讀進來，然后在分別提取出魔咒和對應的功能。

方法一：

//使用雙map來實現 #include<iostream> #include<map> #include<cstdio> #include<string> using namespace std;map<string,string>map_magic,map_funtion; int main(void) {int n,k;string str1,str2,str,temp_str;map_magic.clear();map_funtion.clear();while(getline(cin,temp_str)){if(temp_str=="@END@")break;k=temp_str.find("]");str1=temp_str.substr(0,k+1);str2=temp_str.substr(k+2,temp_str.size()-k-2);map_magic[str1]=str2;map_funtion[str2]=str1;}scanf("%d",&n);getchar();while(n--){getline(cin,str);if(str[0]=='['){if(map_magic.count(str))cout<<map_magic[str]<<endl; //由魔咒來選擇功能elsecout<<"what?"<<endl;}else{if(map_funtion.count(str)){temp_str=map_funtion[str]; //由功能來選擇魔咒cout<<temp_str.substr(1,temp_str.size()-2)<<endl;}elsecout<<"what?"<<endl;}}return 0; }

方法二：

//字符串哈希的時間最快，只需要10 MS #include<iostream> #include<cstdio> #include<cstring> using namespace std;#define N 100100 #define M 100100const char *end = "@END@"; char word[N][25], expr[N][85]; int magic[M], funtion[M];unsigned int bkdrHash(char *str) {unsigned int seed = 131;unsigned int hash = 0;while(*str){hash = hash * seed + *str++;}return (hash & 0x7FFFFFFF) % M; }int setPos(int idx, int arr[]) {int i = 1;while(arr[idx]) //哈希地址沖突的時候{idx = (idx + i * i) % M; //處理哈希沖突的方法，二次探測再散列i++;}return idx; } int getPos(int idx, int arr[], int type, char *str) {int i = 1, k = 0;while(arr[idx]){if(type == 0 && strcmp(word[arr[idx]], str) == 0){k = magic[idx]; //找到魔咒在字典中的位置break;}else if(type && strcmp(expr[arr[idx]], str) == 0){k = funtion[idx]; //找到功能在字典中的位置break;}else{idx = (idx + i * i) % M;i++;}}return k; } int main(void) {char str[128];int i, j, k, n;k = 1;memset(magic, 0, sizeof(magic));memset(funtion, 0, sizeof(funtion));while(gets(str)){if(strcmp(str, end) == 0)break;for(i=0;str[i]!= ']';i++)word[k][i]=str[i]; //保存魔咒word[k][i]=str[i];i++;word[k][i++]='\0';j = setPos(bkdrHash(word[k]), magic);magic[j] = k;j = 0;for(;str[i]!='\0';i++)expr[k][j++]=str[i]; //保存功能expr[k][j]='\0';j = setPos(bkdrHash(expr[k]), funtion);funtion[j] = k;k++;}scanf("%d", &n);getchar();while(n--){gets(str);if(str[0] == '['){j = getPos(bkdrHash(str), magic, 0, str);if(j) //查詢成功puts(expr[j]);else //查詢失敗printf("what?\n");}else{j = getPos(bkdrHash(str), funtion, 1, str);if(j){k = strlen(word[j]);for(i = 1; i < k-1; i++)printf("%c", word[j][i]);printf("\n");}elseprintf("what?\n");}}return 0; }方法三：

//二分查找 #include<iostream> #include<algorithm> #include<vector> #include<cstdio> #include<string> using namespace std;struct Word {string magic;string funtion; }word;vector<Word> dic1,dic2;int my_binary_search(int low, int high,string key,int i) {int mid;if(i==1) //查找魔咒{while(low<=high){mid=(low+high)>>1;if(key<dic1[mid].magic)high=mid-1;else if(key==dic1[mid].magic)return mid;elselow=mid+1;}}else if(i==2) //查找功能{while(low<=high){mid=(low+high)>>1;if(key<dic2[mid].funtion)high=mid-1;else if(key==dic2[mid].funtion)return mid;elselow=mid+1;}}return -1; //查找失敗 }bool cmp1(const Word &a,const Word &b) {return a.magic<b.magic; } bool cmp2(const Word &a,const Word &b) {return a.funtion<b.funtion; }int main(void) {int n,k;string str,temp_str;while(getline(cin,temp_str)){if(temp_str=="@END@")break;k=temp_str.find("]");word.magic=temp_str.substr(0,k+1);word.funtion=temp_str.substr(k+2,temp_str.size()-k-2);dic1.push_back(word);dic2.push_back(word);}sort(dic1.begin(), dic1.end(), cmp1); //按照魔咒的字典序進行排序sort(dic2.begin(), dic2.end(), cmp2); //按照功能的字典序進行排序scanf("%d",&n);getchar();vector<Word>::iterator iter; //vector的迭代器while(n--){getline(cin,str);if(str[0]=='[') //由魔咒來選擇功能{k=my_binary_search(0, dic1.size()-1,str,1);if(k!=-1)cout<<dic1[k].funtion<<endl;elsecout<<"what?"<<endl;}else{k=my_binary_search(0, dic2.size()-1 ,str,2);if(k!=-1){temp_str=dic2[k].magic;cout<<temp_str.substr(1,temp_str.size()-2)<<endl;}elsecout<<"what?"<<endl;}}return 0; }

方法四： （可能會導致超時）

//使用一個map來實現，反過來用迭代器查詢 #include<iostream> #include<map> #include<cstdio> #include<string> using namespace std;map<string,string>map_magic; int main(void) {int n,k;string str1,str2,str,temp_str;map_magic.clear();while(getline(cin,temp_str)){if(temp_str=="@END@")break;k=temp_str.find("]");str1=temp_str.substr(0,k+1);str2=temp_str.substr(k+2,temp_str.size()-k-2);map_magic[str1]=str2;}scanf("%d",&n);getchar();map<string,string>::iterator iter; //map的迭代器while(n--){getline(cin,str);if(str[0]=='['){if(map_magic.count(str))cout<<map_magic[str]<<endl; //由魔咒來選擇功能elsecout<<"what?"<<endl;}else{for(iter=map_magic.begin();iter!=map_magic.end();iter++){if((*iter).second==str){temp_str=(*iter).first;cout<<temp_str.substr(1,temp_str.size()-2)<<endl;break;}}if(iter==map_magic.end())cout<<"what?"<<endl;}}return 0; }

http://ac.jobdu.com/problem.php?id=1030??畢業(yè)bg

/* 題目實質是01背包問題，不過加了幾方面的限制 將bg當作物品，離開時間當作重量，快樂度當作價值，則與01背包不同的是物品放入的順序是有先后順序的 所以需要排序 */ #include<iostream> #include<algorithm> #include<cstdio> using namespace std; #include<memory.h>struct Node {int happy;int last;int time; }node[31];bool cmp(const Node &a,const Node &b) {return a.time<b.time; }int dp[1000];int ZeroOnePack(int n) {int i,j,max=-1,p;memset(dp,0,sizeof(dp));for(i=0;i<n;i++) //動態(tài)規(guī)劃{if(node[i].time>max)max=node[i].time;for(j=node[i].time;j>=node[i].last;j--) //j表示背包的大小，從最后離開的時間到持續(xù)時間dp[j] = dp[j]>dp[j-node[i].last]+node[i].happy? dp[j]:dp[j-node[i].last]+node[i].happy;}p=-1;for(i=1;i<=max;i++){if(dp[i]>p)p=dp[i];}return p; }int main(void) {int i,n;while(scanf("%d",&n)!=EOF){if(n<0)break;for(i=0;i<n;i++)scanf("%d %d %d",&node[i].happy,&node[i].last,&node[i].time);sort(node,node+n,cmp); //按最后離開的時間從小到大排序printf("%d\n",ZeroOnePack(n));}return 0; }

?

?

總結

以上是生活随笔為你收集整理的2008年浙江大学计算机及软件工程研究生机试真题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。