L2-030 冰岛人 (25分)
这道题需注意的是,题中说 “五代以内无公共祖先”是指两人的公共祖先(如果存在的话)必须比任何一方的曾祖父辈分高。
所以即使一个人的父亲是另一个人的曾曾曾曾曾曾曾曾。。。祖父,那他们也是不可以!!
我写的答案测试点三错误,测试点六超时。。。
不想再改了,,,,
原题:
2018年世界杯,冰岛队因1:1平了强大的阿根廷队而一战成名。好事者发现冰岛人的名字后面似乎都有个“松”(son),于是有网友科普如下:
冰岛人沿用的是维京人古老的父系姓制,孩子的姓等于父亲的名加后缀,如果是儿子就加 sson,女儿则加 sdottir。因为冰岛人口较少,为避免近亲繁衍,本地人交往前先用个 App 查一下两人祖宗若干代有无联系。本题就请你实现这个 App 的功能。
输入格式:
输入首先在第一行给出一个正整数 N(1<N≤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;
map<string,int> vis[100005];
int n,flag,it;
map<string,string> v;
map<string,int> sex;//1表示男性,2表示女性
void findd(string s,int x)
{
string fa = v[s];
if(vis[it][s]==3)
{
if(x<4)
flag = 1;
return;
}
vis[it][s] = 3;//做标记
if(sex[fa]==0)//没有父亲
return;
findd(fa,x+1);
return;
}
int main()
{
cin>>n;
string s1,s2;
for(int i = 0;i<n;i++)
{
getchar();
cin>>s1>>s2;
int len = s2.length();
if(s2[len-1]=='m')
{
string s3 = s2.substr(0,len-1);//截取s2中从0开始,长度为len-1的字符串
v[s1] = s3;
sex[s1] = 1;
}
else if(s2[len-1]=='f')
{
string s3 = s2.substr(0,len-1);
v[s1] = s3;
sex[s1] = 2;
}
else if(s2[len-1]=='n')
{
string s3 = s2.substr(0,len-4);
v[s1] = s3;
sex[s1] = 1;
}
else if(s2[len-1]=='r')
{
string s3 = s2.substr(0,len-7);
v[s1] = s3;
sex[s1] = 2;
}
}
int m;
cin>>m;
string s3,s4;
for(int i = 0;i<m;i++)
{
getchar();
cin>>s1>>s2>>s3>>s4;
if(sex[s1]==0||sex[s3]==0)
{
cout<<"NA"<<endl;
}
else if(sex[s1]==sex[s3]){
cout<<"Whatever"<<endl;
}
else{
flag = 0;
findd(s1,0);
findd(s3,0);
if(flag==1)
cout<<"No"<<endl;
else cout<<"Yes"<<endl;
}
it++;
}
}