2018年世界杯，冰岛队因1:1平了强大的阿根廷队而一战成名。好事者发现冰岛人的名字后面似乎都有个“松”（son），于是有网友科普如下：

冰岛人沿用的是维京人古老的父系姓制，孩子的姓等于父亲的名加后缀，如果是儿子就加 sson，女儿则加 sdottir。因为冰岛人口较少，为避免近亲繁衍，本地人交往前先用个 App 查一下两人祖宗若干代有无联系。本题就请你实现这个 App 的功能。

输入首先在第一行给出一个正整数 N（1> x; //记录所有人的性别 if(x.back() == 'm') sex[m] = 1; else if(x.back() == 'f') sex[m] = 2; else if(x.back() == 'n')//记录维京人的父亲 { sex[m] = 1; fa[m] = x.substr(0,x.size() - 4); } else { sex[m] = 2; fa[m] = x.substr(0,x.size() - 7); } } cin >> n; while(n--) { string x1,m1,x2,m2; cin >> m1 >> x1 >> m2 >> x2; //在哈希表中插入一个键，若不赋值，数值型默认为0，字符串则为空串 if(!sex[m1] || !sex[m2]) puts("NA");//因为我们记录了所有人的性别，所以可以通过查询性别判断是否在名单中 else if(sex[m1] == sex[m2]) puts("Whatever"); else if(check(m1,m2)) puts("Yes"); else puts("No"); } return 0; } //测试点3和6所谓“五代以内无公共祖先”是指两人的公共祖先（如果存在的话）必须比任何一方的曾祖父辈分高。3 6 不行 //测试点4 是关于NA的 //测试点2 只需记录维京家族的父辈，每个维京家族的起源人都是男性 二刷代码： #include #include #include #include #include using namespace std; const int N = 100010; unordered_map ha; int f[N],sex[N],st[N],idx; int check(int p1,int p2) { memset(st,0,sizeof st); for(int i = p1,j = 1;i;i = f[i],j++) st[i] = j; for(int i = p2,j = 1;i;i = f[i],j++) if(st[i])//第一个公共祖先 { if(st[i] >= 5 && j >= 5) return 1; else return 0; } return 1; } void test(string name) { int t = ha[name]; cout x; if(!ha[m]) ha[m] = ++idx; int t = ha[m]; if(x.back() == 'm') sex[t] = 1; else if(x.back() == 'f') sex[t] = 2; else if(x.back() == 'n') { sex[t] = 1; string fm = x.substr(0,x.size() - 4); if(!ha[fm]) ha[fm] = ++idx; f[t] = ha[fm]; } else { sex[t] = 2; string fm = x.substr(0,x.size() - 7); if(!ha[fm]) ha[fm] = ++idx; f[t] = ha[fm]; } //test(m); } int m = 0; cin >> m; while(m--) { string m1,x1,m2,x2; cin >> m1 >> x1 >> m2 >> x2; //test(m1);test(m2); if(!sex[ha[m1]] || !sex[ha[m2]]) puts("NA"); else if(sex[ha[m1]] == sex[ha[m2]]) puts("Whatever"); else { if(check(ha[m1],ha[m2])) puts("Yes"); else puts("No"); } } return 0; } 结果：