程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> 2013編程之美全國挑戰賽資格賽之傳話游戲

2013編程之美全國挑戰賽資格賽之傳話游戲

編輯:關於C語言

時間限制: 1000ms 內存限制: 256MB

描述

Alice和Bob還有其他幾位好朋友在一起玩傳話游戲。這個游戲是這樣進行的:首先,所有游戲者按順序站成一排,Alice站第一位,Bob站最後一位。然後,Alice想一句話悄悄告訴第二位游戲者,第二位游戲者又悄悄地告訴第三位,第三位又告訴第四位……以此類推,直到倒數第二位告訴Bob。兩位游戲者在傳話中,不能讓其他人聽到,也不能使用肢體動作來解釋。最後,Bob把他所聽到的話告訴大家,Alice也把她原本所想的話告訴大家。  由於傳話過程中可能出現一些偏差,游戲者越多,Bob最後聽到的話就與Alice所想的越不同。Bob聽到的話往往會變成一些很搞笑的東西,所以大家玩得樂此不疲。經過幾輪游戲後,Alice注意到在兩人傳話中,有些詞匯往往會錯誤地變成其他特定的詞匯。Alice已經收集到了這樣的一個詞匯轉化的列表,她想知道她的話傳到Bob時會變成什麼樣子,請你寫個程序來幫助她。

輸入

輸入包括多組數據。第一行是整數 T,表示有多少組測試數據。每組數據第一行包括兩個整數 N 和 M,分別表示游戲者的數量和單詞轉化列表長度。隨後有 M 行,每行包含兩個用空格隔開的單詞 a 和 b,表示單詞 a 在傳話中一定會變成 b。輸入數據保證沒有重復的 a。最後一行包含若干個用單個空格隔開的單詞,表示Alice所想的句子,句子總長不超過100個字符。所有單詞都只包含小寫字母,並且長度不超過20,同一個單詞的不同時態被認為是不同的單詞。你可以假定不在列表中的單詞永遠不會變化。

輸出

對於每組測試數據,單獨輸出一行“Case #c: s”。其中,c 為測試數據編號,s 為Bob所聽到的句子。s 的格式與輸入數據中Alice所想的句子格式相同。

數據范圍

1 ≤ T ≤ 100 小數據:2 ≤ N ≤ 10, 0 ≤ M ≤ 10  大數據:2 ≤ N ≤ 100, 0 ≤ M ≤ 100 

樣例輸入

  1. 4 3 
  2. ship sheep 
  3. sinking thinking 
  4. thinking sinking 
  5. the ship is sinking 
  6. 10 5 
  7. tidy tiny 
  8. tiger liar 
  9. tired tire 
  10. tire bear 
  11. liar bear 
  12. a tidy tiger is tired 

樣例輸出

  1. Case #1: the sheep is thinking 
  2. Case #2: a tiny bear is bear 
  代碼如下:
  1. #include <cstdio> 
  2. #include <cstring> 
  3. #include <cmath> 
  4. #include <string> 
  5. #include <iostream> 
  6. #include <map> 
  7.   
  8. using namespace std; 
  9.   
  10. map<string,string> mm; 
  11. char s1[30],s2[30],s[110],*p; 
  12. int t,m,n; 
  13.   
  14. void solve() 
  15.     int i; 
  16.     string str; 
  17.     str=p; 
  18.     for(i=1;i<n;i++)  
  19.     { 
  20.         if(mm.count(str)) 
  21.             str=mm[str]; 
  22.         else 
  23.             break; 
  24.     }  
  25.     cout<<str; 
  26.   
  27. int main() 
  28.     int i,cnt;scanf("%d%*c",&t); 
  29.     for(cnt=1;cnt<=t;cnt++) 
  30.     { 
  31.         mm.clear(); 
  32.         scanf("%d %d%*c",&n,&m); 
  33.         for(i=0;i<m;i++) 
  34.         { 
  35.             scanf("%s %s%*c",s1,s2); 
  36.             mm[s1]=s2; 
  37.         } 
  38.         gets(s); 
  39.         printf("Case #%d: ",cnt); 
  40.         p=strtok(s," "); 
  41.         solve(); 
  42.         while((p=strtok(NULL," "))) 
  43.         { 
  44.             cout<<" "; 
  45.             solve(); 
  46.         } 
  47.         cout<<endl; 
  48.     } 
  49.   
  50.     return 0; 
上述代碼來自:http://blog.sina.com.cn/s/blog_959bf1d30101evsx.html 另一組代碼:
  1. #include <stdio.h> 
  2. #include <cstring> 
  3. #include <vector> 
  4. #include <map> 
  5.   
  6. using namespace std; 
  7.   
  8.   
  9. //字符串分割函數 
  10.  std::vector<std::string> split(std::string str,std::string pattern) 
  11.  { 
  12.      std::string::size_type pos; 
  13.      std::vector<std::string> result; 
  14.      str+=pattern;//擴展字符串以方便操作 
  15.      int size=str.size(); 
  16.   
  17.      for(int i=0; i<size; i++) 
  18.      { 
  19.          pos=str.find(pattern,i); 
  20.          if(pos<size) 
  21.          { 
  22.              std::string s=str.substr(i,pos-i); 
  23.              result.push_back(s); 
  24.              i=pos+pattern.size()-1; 
  25.          } 
  26.      } 
  27.      return result; 
  28.  } 
  29.   
  30. void Update(vector<string> & str,map<string,string> & w_map) 
  31.     map<string,string>::iterator it; 
  32.     for(int i=0;i<str.size();i++) 
  33.     { 
  34.         it = w_map.find(str[i]); 
  35.         if(it != w_map.end()) 
  36.         { 
  37.             str[i]=it->second; 
  38.         } 
  39.     } 
  40.   
  41. int main() 
  42.     int T; 
  43.   
  44.     while(scanf("%d",&T) == 1) 
  45.     { 
  46.         for(int x=1;x<=T;x++) 
  47.         { 
  48.             int N,M; 
  49.             map<string,string> words_map; 
  50.             string s1,s2; 
  51.             string srcWords,tgtWords; 
  52.   
  53.             scanf("%d%d",&N,&M); 
  54.             for(int i=1;i<=M;i++) 
  55.             { 
  56.                 cin>>s1>>s2; 
  57.                 words_map.insert(make_pair(s1,s2)); 
  58.             } 
  59.             cin.get();//吃掉上一行換行符 
  60.             getline(cin,srcWords,'\n'); 
  61.             vector<string> singleWord = split(srcWords," "); 
  62.   
  63.   
  64.             for(int i=1;i<=N-1;i++) 
  65.             { 
  66.                 Update(singleWord,words_map); 
  67.             } 
  68.             printf("Case #%d: ",x); 
  69.             for(int i=0;i<singleWord.size()-1;i++) 
  70.                 cout<<singleWord[i]<<" "; 
  71.             cout<<singleWord[singleWord.size()-1]<<endl; 
  72.         } 
  73.   
  74.     } 
  75.     return 0; 
來自:http://blog.csdn.net/xihuanqiqi/article/details/8763444  

本文出自 “求學者Wenry” 博客,請務必保留此出處http://wenryxu.blog.51cto.com/6496375/1174144

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved