2013编程之美全国挑战赛资格赛之传话游戏

简介:

时间限制: 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; 
另一组代码:
 
  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; 
目录
相关文章
|
计算机视觉
教你如何玩转Modelscope (一、图片编辑与描述生成)
本文通过一个有趣的图片处理例子,教你如何利用modelscope强大且多样的模型能力去解锁你专属的图片编辑能力。
3415 1
教你如何玩转Modelscope (一、图片编辑与描述生成)
|
安全 搜索推荐 数据挖掘
什么是TikTok机房?有什么用?
TikTok机房是专为高效管理多个TikTok账号设计的系统或场所,配备大量硬件设备和海外代理IP,可模拟真实用户行为,提升内容推广效率。通过自动化工具批量操作,不仅能规避账号关联风险,还能实现精准营销并优化数据分析。使用时需注意合规性、安全性和数据保护。
|
9月前
|
数据采集 数据可视化 索引
Pandas数据应用:股票数据分析
本文介绍了如何使用Pandas库进行股票数据分析。首先,通过pip安装并导入Pandas库。接着,从本地CSV文件读取股票数据,并解决常见的解析错误。然后,利用head()、info()等函数查看数据基本信息,进行数据清洗,处理缺失值和重复数据。再者,结合Matplotlib和Seaborn进行数据可视化,绘制收盘价折线图。最后,进行时间序列分析,设置日期索引、重采样和计算移动平均线。通过这些步骤,帮助读者掌握Pandas在股票数据分析中的应用。
358 5
|
11月前
|
Python
蓝桥杯常用函数基础 | 模块及常用内置函数
蓝桥杯常用函数基础 | 模块及常用内置函数
|
11月前
|
弹性计算 监控 安全
阿里云服务器自带多少DDoS防护?小编为你详细揭秘!
阿里云服务器自带多少DDoS防护?小编为你详细揭秘!
|
网络协议 网络安全 数据库
|
SQL 分布式计算 关系型数据库
分布式系统详解 -- Hive1.2.1 安装
分布式系统详解 -- Hive1.2.1 安装
240 1
|
Web App开发 缓存 JavaScript
前端(四)——vue.js、vue、vue2、vue3
前端(四)——vue.js、vue、vue2、vue3
3767 0
|
机器学习/深度学习 传感器 人工智能
纯视觉3D检测综述!一文详解3D检测现状、趋势和未来方向!(下)
基于图像的3D目标检测是自动驾驶领域的一个基本问题,也是一个具有挑战性的问题,近年来受到了业界和学术界越来越多的关注。得益于深度学习技术的快速发展,基于图像的3D检测取得了显著的进展。特别是,从2015年到2021年,已经有超过200篇研究这个问题的著作,涵盖了广泛的理论、算法和应用。然而,到目前为止,还没有一个调查来收集和组织这方面的知识。本文首次对这一新兴的不断发展的研究领域进行了全面综述,总结了基于图像的3D检测最常用的流程,并对其各个组成部分进行了深入分析。此外,作者还提出了两个新的分类法,将最先进的方法组织成不同的类别,以期提供更多的现有方法的系统综述,并促进与未来作品的公平比较。
纯视觉3D检测综述!一文详解3D检测现状、趋势和未来方向!(下)
|
消息中间件 缓存 前端开发
同步转异步处理|学习笔记
快速学习同步转异步处理
456 0
同步转异步处理|学习笔记