L2-030 冰岛人 (25 分)

L2-030 冰岛人 (25 分)

2018年世界杯,冰岛队因 \(1:1\) 平了强大的阿根廷队而一战成名。好事者发现冰岛人的名字后面似乎都有个“松”(son),于是有网友科普如下:
L2-030 冰岛人 (25 分)
冰岛人沿用的是维京人古老的父系姓制,孩子的姓等于父亲的名加后缀,如果是儿子就加 sson,女儿则加 sdottir。因为冰岛人口较少,为避免近亲繁衍,本地人交往前先用个 \(App\) 查一下两人祖宗若干代有无联系。本题就请你实现这个 \(App\) 的功能。

输入格式:

入首先在第一行给出一个正整数 \(N \; (1 \leq N \leq 10^{5})\),为当地人口数。随后 \(N\) 行,每行给出一个人名,格式为:名 姓(带性别后缀),两个字符串均由不超过 \(20\) 个小写的英文字母组成。维京人后裔是可以通过姓的后缀判断其性别的,其他人则是在姓的后面加 m 表示男性、f 表示女性。题目保证给出的每个维京家族的起源人都是男性。
随后一行给出正整数 \(M\),为查询数量。随后 \(M\) 行,每行给出一对人名,格式为:名1 姓1 名2 姓2。注意:这里的姓是不带后缀的。四个字符串均由不超过 \(20\) 个小写的英文字母组成。
题目保证不存在两个人是同名的。

输出格式:

对每一个查询,根据结果在一行内显示以下信息:

  • 若两人为异性,且五代以内无公共祖先,则输出 Yes
  • 若两人为异性,但五代以内(不包括第五代)有公共祖先,则输出 No
  • 若两人为同性,则输出 Whatever
  • 若有一人不在名单内,则输出 NA

所谓“五代以内无公共祖先”是指两人的公共祖先(如果存在的话)必须比任何一方的曾祖父辈分高。

输入样例:

15
chris smithm
adam smithm
bob adamsson
jack chrissson
bill chrissson
mike jacksson
steve billsson
tim mikesson
april mikesdottir
eric stevesson
tracy timsdottir
james ericsson
patrick jacksson
robin patricksson
will robinsson
6
tracy tim james eric
will robin tracy tim
april mike steve bill
bob adam eric steve
tracy tim tracy tim
x man april mikes

输出样例:

Yes
No
No
Whatever
Whatever
NA

参考代码:

#include<bits/stdc++.h>
using namespace std;
int n,m;
string a,b,s;
struct it{char sex;string fa;};
unordered_map<string,it>who;
inline bool check(string a,string b)
{
    int x=1,y;
    for(string i=a;i.size();i=who[i].fa,x++)
    {
        y=1;
        for(string j=b;j.size();j=who[j].fa,y++)
        {
            if(x>=5&&y>=5)break;
            if(i==j)return 0;
        }
    }
    return 1;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a>>b;
        if(b.back()=='n')who[a]={'m',b.substr(0,b.length()-4)};
        else if(b.back()=='r')who[a]={'f',b.substr(0,b.length()-7)};
        else who[a].sex=b.back();
    }
    cin>>m;
    while(m--)
    {
        cin>>a>>s>>b>>s;
        if(who.find(a)==who.end()||who.find(b)==who.end())cout<<"NA"<<endl;
        else if(who[a].sex==who[b].sex)cout<<"Whatever"<<endl;
        else if(check(a,b))cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}
上一篇:Android双击退出


下一篇:3.3 自定义控件基础 之 View的绘制