一键安装网站运行环境,低价网站建设联系方式,网站篡改搜索引擎js,wordpress文章文件作者 陈越
单位 浙江大学
2018年世界杯#xff0c;冰岛队因1:1平了强大的阿根廷队而一战成名。好事者发现冰岛人的名字后面似乎都有个“松”#xff08;son#xff09;#xff0c;于是有网友科普如下#xff1a; 冰岛人沿用的是维京人古老的父系姓制#xff0c;孩子的姓…作者 陈越
单位 浙江大学
2018年世界杯冰岛队因1:1平了强大的阿根廷队而一战成名。好事者发现冰岛人的名字后面似乎都有个“松”son于是有网友科普如下 冰岛人沿用的是维京人古老的父系姓制孩子的姓等于父亲的名加后缀如果是儿子就加 sson女儿则加 sdottir。因为冰岛人口较少为避免近亲繁衍本地人交往前先用个 App 查一下两人祖宗若干代有无联系。本题就请你实现这个 App 的功能。
输入格式
输入首先在第一行给出一个正整数 N1N≤105为当地人口数。随后 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
题目说了只要查维京家族的祖上所以我们只存维京家族的族谱就行。
但维京家族的族谱很乱所以要用双层循环去遍历是否有同一个人出现。
最后再判断就结束了
#includebits/stdc.h
using namespace std;
typedef long long ll;
#define endl \nll n,m;
string s,ss,sx,sy;
mapstring,pairbool,string mp;//本人姓名,性别(1为男,0为女),父亲姓名bool find(string x ,string y){//以x家族为基准,遍历两个家族 ll cx 0,cy;while(x ! ){//x只往上4代,y往上遍历所有人 cy 0;s y;//每次y家族从头开始 while(s ! ){if(cx 4 cy 4)return 1;if(x s (cx 4 || cy 4) )return 0;smp[s].second;cy;}xmp[x].second;//x往上一代 cx;}return 1;//防止两家都没有4代人情况出现
}void solve(){cin n;while(n --){//记录族谱 cin s ss;if(ss.back() n)mp[s]{1,ss.substr(0,ss.size()-4)};if(ss.back() r)mp[s]{0,ss.substr(0,ss.size()-7)};if(ss.back() m)mp[s].first1;if(ss.back() f)mp[s].first0;}cin m;while(m --){cin sx s sy s;if(!mp.count(sx) || !mp.count(sy))cout NA endl;else if(mp[sx].first mp[sy].first)cout Whatever endl;else if(find(sx,sy))cout Yes endl;else cout No endl;}return ;
}int main(){ll t1;//cin t;while(t--)solve();return 0;
}
