2018年世界杯,冰岛队因1:1平了强大的阿根廷队而一战成名。好事者发现冰岛人的名字后面似乎都有个“松”(son),于是有网友科普如下:
冰岛人沿用的是维京人古老的父系姓制,孩子的姓等于父亲的名加后缀,如果是儿子就加 sson,女儿则加 sdottir。因为冰岛人口较少,为避免近亲繁衍,本地人交往前先用个 App 查一下两人祖宗若干代有无联系。本题就请你实现这个 App 的功能。
输入格式:
输入首先在第一行给出一个正整数 N(1<N≤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
输出样例:
1. Yes 2. No 3. No 4. Whatever 5. Whatever 6. NA
思路:因为是字符串之间的关系,所以才unordered_map嵌套结构体存储关系
#include<iostream> #include<unordered_map> using namespace std; struct node { string fa; int sex; }; unordered_map<string,node>ans; int check(string a,string b)//判断五代以内有无公共祖先 { int i=1; for(string A=a;!A.empty();i++,A=ans[A].fa) { int j=1; for(string B=b;!B.empty();j++,B=ans[B].fa) { if(i>=5&&j>=5) return 1; if(A==B&&(i<5||j<5)) return 0; } } return 1; } int main() { int n; cin>>n; for(int i=0;i<n;i++) { string a,b; cin>>a>>b; if(b[b.size()-1]=='m') ans[a].sex=1; else if(b[b.size()-1]=='f') ans[a].sex=2; else if(b[b.size()-1]=='n') { string ss=b.substr(0,b.size()-4); ans[a].sex=1; ans[a].fa=ss; } else if(b[b.size()-1]=='r') { string ss=b.substr(0,b.size()-7); ans[a].sex=2; ans[a].fa=ss; } } int k; cin>>k; while(k--) { string a,b,c,d; cin>>a>>b>>c>>d; if(!ans[a].sex||!ans[c].sex) cout<<"NA\n"; else if(ans[a].sex==ans[c].sex) cout<<"Whatever\n"; else if(check(a,c)) cout<<"Yes\n"; else cout<<"No\n"; } return 0; }