鱼C论坛

 找回密码
 立即注册
查看: 2624|回复: 1

[技术交流] 045:产生冠军

[复制链接]
发表于 2018-2-17 23:59:26 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
Description
有一群人,打乒乓球比赛,两两捉对撕杀,每两个人之间最多打一场比赛。
球赛的规则如下:
如果A打败了B,B又打败了C,而A与C之间没有进行过比赛,那么就认定,A一定能打败C。
如果A打败了B,B又打败了C,而且,C又打败了A,那么A、B、C三者都不可能成为冠军。
根据这个规则,无需循环较量,或许就能确定冠军。你的任务就是面对一群比赛选手,在经过了若干场撕杀之后,确定是否已经实际上产生了冠军。

Input
输入含有一些选手群,每群选手都以一个整数n(n<1000)开头,后跟n对选手的比赛结果,比赛结果以一对选手名字(中间隔一空格)表示,前者战胜后者。如果n为0,则表示输入结束。

Output
对于每个选手群,若你判断出产生了冠军,则在一行中输出“Yes”,否则在一行中输出“No”。

Sample Input
3
Alice Bob
Smith John
Alice Smith
5
a c
c d
d e
b e
a d
0

Sample Output
Yes
No

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2018-2-18 00:03:21 | 显示全部楼层
map<string,int> M;  //定义一个完成从string到int映射的map
M.clear();  //清空一个map
M.find(a);  //确定是否保存string对象b的映射,若没有函数返回M.end();
M[a]=idx;  //you know!

  1. #include<cstdio>
  2. #include<vector>
  3. #include<map>
  4. #include<cstring>
  5. #include<iostream>
  6. #include<queue>

  7. using namespace std;
  8. map<string,int> M;
  9. int in[2002];
  10. int main()
  11. {
  12.         int n;
  13.         while(scanf("%d",&n)!=EOF&&n!=0)
  14.         {
  15.                 memset(in,0,sizeof(in));
  16.                 M.clear();
  17.                 int idx=0;
  18.                 for(int i=0;i<n;i++)
  19.                 {
  20.                         char str1[50],str2[50];
  21.                         scanf("%s%s",&str1,&str2);
  22.                         string a=str1,b=str2;
  23.                         int idxa,idxb;
  24.                         if(M.find(a)==M.end())
  25.                         {
  26.                                 idxa=idx;
  27.                                 M[a]=idx++;
  28.                         }
  29.                         else        idxa=M[a];
  30.                         if(M.find(b)==M.end())
  31.                         {
  32.                                 idxb=idx;
  33.                                 M[b]=idx++;
  34.                         }
  35.                         else        idxb=M[b];
  36.                         in[idxb]++;
  37.                 }
  38.                 int cnt=0;
  39.                 for(int i=0;i<idx;i++)
  40.                         if(in[i]==0)
  41.                                 cnt++;
  42.                 puts(cnt==1?"Yes":"No");
  43.         }
  44.         return 0;
  45. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 1 反对 0

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 20:11

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表