HRBUST 1314 火影忍者之~纲手【MAP】

(20) 2024-03-30 17:01:03

火影忍者之~纲手

 
Time Limit: 3000 MS Memory Limit: 65536 K
Total Submit: 246(78 users) Total Accepted: 101(69 users) Rating:HRBUST 1314 火影忍者之~纲手【MAP】 (https://mushiming.com/)  第1张HRBUST 1314 火影忍者之~纲手【MAP】 (https://mushiming.com/)  第1张HRBUST 1314 火影忍者之~纲手【MAP】 (https://mushiming.com/)  第1张 Special Judge: No
Description

因为大蛇丸的捣乱,木叶忍者村痛失了和蔼的三代火影,所以身为三代火影徒弟之一的纲手不得不接受木叶村火影的职务~,因为刚刚上任,所以纲手大人需要对木叶村主要忍者的实力有个了解,以方便以后分配任务,所以我们需要统计一下每个忍者的实力高低,作为刚刚通过公务员选拔的你,这可是个很好的表现机会~你需要做的是将所有给定忍者部分实力高低关系,然后在需要的时候能够快速的查找到.

HRBUST 1314 火影忍者之~纲手【MAP】 (https://mushiming.com/)  第4张

Input
给出一个整数n,然后n行每行给出两个名字,表示前一个忍者强于后一个,然后是一个整数m,表示m个查找,然后是m行,每行也是两个名字。输入到文件尾。忍者的个数在1000以内,名字不长于20n<1000000,m<=1000
Output
对于每个查找,输出两个忍者的强弱关系,如果前一个强于后一个,输出“win”,如果前一个弱于后一个,输出”lose”,如果不能确定或查找不到,输出”unknown”(强弱关系不能传递。)
Sample Input

3

abc bcd

def fgh

def abc

2

bcd fgh

fgh def

Sample Output

unknown

lose

Source
2012 Spring Contest 3 - STL
Author
拂晓

原本觉得应该是并查集,。。。然后发现没有强弱关系传递。。。嗯,,,还是想麻烦了。。

但这题还是一个很好的思路题。。

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
#include<map>
using namespace std;

int vis[1005][1005];///记录比赛情况,就是记录谁和谁比赛过

int main()
{

    char namea[25];
    char nameb[25];

    map<string,int>m;///确立map对立关系

    int n;
    while(cin>>n)
    {
        m.clear();///别忘清空
        memset(vis,0,sizeof(vis));

        int flag=0;

        for(int i=0; i<n; i++)
        {
            scanf("%s %s",namea,nameb);

            if(!m[namea])
            {
                m[namea]=flag++;///如果没有比赛过,就自增。
            }
            if(!m[nameb])
            {
                m[nameb]=flag++;
            }
            vis[m[namea]][m[nameb]]=1;
        }
        int n2;
        scanf("%d",&n2);

        while(n2--)
        {

            scanf("%s %s",namea,nameb);
            /*
            unknow情况有以下几种
            !m[namea]||!m[nameb] 代表两者都没有去比赛
            vis[m[namea]][m[nameb]]&&vis[m[nameb]][m[namea]]  代表A战胜了B B又战胜了A,互相矛盾
            vis[m[namea]][m[nameb]]==0&&vis[m[nameb]][m[namea]]==0  代表两者没有必过赛
            */


            if(!m[namea]||!m[nameb]||(vis[m[namea]][m[nameb]]&&vis[m[nameb]][m[namea]])||(vis[m[namea]][m[nameb]]==0&&vis[m[nameb]][m[namea]]==0))
            {
                printf("unknown\n");
            }
            else if(vis[m[namea]][m[nameb]])
            {
                printf("win\n");
            }
            else if(vis[m[nameb]][m[namea]])
            {
                printf("lose\n");
            }

        }
    }
    return 0;
}

THE END

发表回复