L2-030 冰岛人 (25 分)
L2-030 冰岛人 (25 分)
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
输出样例:
Yes
No
No
Whatever
Whatever
NA
解法:耐心读懂题意就好了。注意这句话----“所谓“五代以内无公共祖先”是指两人的公共祖先(如果存在的话)必须比任何一方的曾祖父辈分高。”,意思就是说两人的公共祖先不能是任何一人的上三代以内(包括第三代也包括自己)。
做起来的话,因为需要存储每个人的父亲,首先需要给每个人编号,另外寻找父亲的话,由于不能用n^2的方法遍历找父亲(会超时),因此可以用两个map容器来存每个人对应的编号,一个map存名另一个存姓(因为后续查询时的姓是不带后缀的因此可以提取姓后缀子串得到姓)作为键,该人对应的编号作为值。还可以预处理一下每个人的性别,方便后面直接判断。在查询的时候,也可以用一个map来存储祖先编号和祖先代数,这样就可以在发现存在共同祖先的时候,直接通过判断祖先代数来得到答案。
坑点:给定查询的两个人,有可能某个人是另一个人的直系祖先;如果两个人存在公共祖先,公共祖先是一个人的上10代祖先,是另一个人的上1代祖先,那么也是No的。(测试点3、6答案错误)
把cin改成scanf的输入。(测试点6超时)
代码:
#include<bits/stdc++.h>
using namespace std;
int n, t, pre[100010], sex[100010];
string s1[100010], s2[100010], fn1, ln1, fn2, ln2;
map<string, int> firstname, lastname;
int main() {
scanf("%d", &n);
getchar();
for(int i = 1; i <= n; i++) {
cin >> s1[i] >> s2[i];
firstname[s1[i]] = i;
if(s2[i].size() > 4 && s2[i].substr(s2[i].size()-4, s2[i].size()) == "sson") {
sex[i] = 1;
lastname[s2[i].substr(0, s2[i].size()-4)] = i;
} else if(s2[i].size() > 7 && s2[i].substr(s2[i].size()-7, s2[i].size()) == "sdottir") {
lastname[s2[i].substr(0, s2[i].size()-7)] = i;
} else if(s2[i][s2[i].size()-1] == 'm') {
sex[i] = 1;
lastname[s2[i].substr(0, s2[i].size()-1)] = i;
} else {
lastname[s2[i].substr(0, s2[i].size()-1)] = i;
}
}
for(int i = 1; i <= n; i++) {
if(s2[i].size() > 4 && s2[i].substr(s2[i].size()-4, s2[i].size()) == "sson") {
if(firstname[s2[i].substr(0, s2[i].size()-4)] != 0) pre[i] = firstname[s2[i].substr(0, s2[i].size()-4)];
else
pre[i] = -1;
} else if(s2[i].size() > 7 && s2[i].substr(s2[i].size()-7, s2[i].size()) == "sdottir") {
if(firstname[s2[i].substr(0, s2[i].size()-7)] != 0) pre[i] = firstname[s2[i].substr(0, s2[i].size()-7)];
else
pre[i] = -1;
} else {
pre[i] = -1;
}
}
scanf("%d", &t);
getchar();
while(t--) {
cin >> fn1 >> ln1 >> fn2 >> ln2;
if(!firstname[fn1] || !firstname[fn2] || !lastname[ln1] || !lastname[ln2]) printf("NA\n");
else if(sex[firstname[fn1]] == sex[firstname[fn2]]) printf("Whatever\n");
else {
map<int, int> f;
int d = 1, flag = 0, now = pre[firstname[fn1]];
f[firstname[fn1]] = 1;
while(now != -1) {
d++;
if(now == firstname[fn2]) {//2是1的直系
flag = 1;
break;
} else {
f[now] = d;
}
now = pre[now];
}
d = 1;
now = pre[firstname[fn2]];
while(now != -1 && !flag) {
d++;
if(f[now] > 0 && (f[now] < 5 || d < 5)) {//存在公共祖先,且是某一方的上三代以内
flag = 1;
break;
}
now = pre[now];
}
if(flag) printf("No\n");
else
printf("Yes\n");
}
}
return 0;
}