浙江财经大学
信息管理与工程学院

HDU 2094 产生冠军(拓扑排序||乱搞)

本文由 Ocrosoft 于 2016-07-14 13:29:02 发表

产生冠军

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 14134    Accepted Submission(s): 6463

Problem 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
 

Solution

没输过的人只有一个,则YES。

代码1、2、3都是这样想的,但是实现方法不同,看喜欢哪种。

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <list>
#include <stack>
#include <string>
#include <vector>
#include <cstring>
#include <cctype>
#include <queue>
#include <set>
#include <map>
#include <climits>
#define ms(a) memset(a,0,sizeof(a))
using namespace std;
string rd(string &s)
{
    cin>>s;
    return s;
}
int main()
{
    int n;
    string s;
    while(cin>>n&&n)
    {
        map<string,int> mp;
        for(int i=0;i<n;i++)
        {
            if(!mp.count(rd(s)))mp[s]=1;//如果没有出现过,那么标记为1
            mp[rd(s)]=0;//输的人标记为0
        }
        int cnt=0;
        for(map<string,int>::iterator it=mp.begin();it!=mp.end()&&cnt<=1;it++)
            if(it->second==1)cnt++;
        printf("%s\n",cnt==1?"Yes":"No");
    }
    return 0;
}

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <list>
#include <stack>
#include <string>
#include <vector>
#include <cstring>
#include <cctype>
#include <queue>
#include <set>
#include <map>
#include <climits>
#define ms(a) memset(a,0,sizeof(a))
using namespace std;
int main()
{
    int n;
    string s;
    while(cin>>n&&n)
    {
        set<string> st;
        set<string> all;
        for(int i=0; i<n; i++)
        {
            cin>>s;
            all.insert(s);
            cin>>s;
            all.insert(s);
            st.insert(s);
        }
        if(all.size()-st.size()==1)printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <list>
#include <stack>
#include <string>
#include <vector>
#include <cstring>
#include <cctype>
#include <queue>
#include <set>
#include <map>
#include <climits>
#define ms(a) memset(a,0,sizeof(a))
using namespace std;
int main()
{
    int n;
    string s;
    while(cin>>n&&n)
    {
        int in[1001]={0},k=0;
        map<string,int> mp;
        for(int i=0;i<n;i++)
        {
            cin>>s;
            if(!mp.count(s))mp[s]=k++;
            cin>>s;
            if(!mp.count(s))mp[s]=k++;
            in[mp[s]]++;
        }
        int cnt=0;
        for(int i=0;i<k&&cnt<=1;i++)if(!in[i])cnt++;
        printf("%s\n",cnt==1?"Yes":"No");
    }
    return 0;
}

 

欢迎转载,请保留出处与链接。Ocrosoft » HDU 2094 产生冠军(拓扑排序||乱搞)

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址