题目解析
给定n个人的姓名，求m组人名的关系。
题目保证不存在两个人是同名的。
孩子的姓等于父亲的名加后缀。
解题思路
在输入n个人的姓名时，通过
姓的性别后缀来判断是否为维京人后裔
- 后缀为
sson与sdottir，则为维京人后裔- 后缀为
m与f，则为其他人
--sson与m，表示男
--sdottir与f，表示女然后用名来存储，每个人的性别与姓
然后再判断m组人名的时候
先判断两个人是否都出现在名单中
- 未出现， 则输出
NA- 出现，则判断两个人性别是否相同
- 相同， 则输出
Whatever
- 最后判断两个人是否五代内有公共祖先
- 出现，则输出
No
- 未出现， 则输出
Yes
如何判断两个人是否五代以内呢？
- 因为
孩子的姓等于父亲的名- 所以可以通过判断当前这个人的姓往上找祖先
注： 本题我java过不去，最后一个数据怎么都是TLE
代码
import java.io.*;
import java.util.*;
public class Main
{
static TreeMap<String, edge> tr = new TreeMap<String, edge>();
static String check(String a, String b)
{
int cnt1 = 0; // a的第几代祖先了
while (!a.equals("")) // 如果a还有祖先
{
int cnt2 = 0; // b的第几代祖先了
String c = b; // b的第0代祖先为自己
while (!c.equals("")) // 如果b还有祖先
{
// 如果a的祖先与b的祖先相同，并且在5代以内
if (a.equals(c) && (cnt1 < 4 || cnt2 < 4)) return "No";
// 如果当前判断的a祖先与b祖先都超过了5代
if (cnt1 >= 4 && cnt2 >= 4) return "Yes";
c = tr.get(c).fname; // 替换b的祖先
cnt2++; // b的祖先代数增加
}
a = tr.get(a).fname; // 替换a的祖先
cnt1++; // a的祖先代数增加
}
return "Yes";
}
public static void main(String[] args)
{
int n = sc.nextInt();
while (n-- > 0)
{
String sname = sc.next(); // 名
String fname = sc.next(); // 姓
// 姓的长度
int len = fname.length();
// 姓中的带性别后缀
char op = fname.charAt(len - 1);
// 如果是维京人后裔的男
if (op == 'n') tr.put(sname, new edge(1, fname.substring(0, len - 4)));
// 如果是维京人后裔的女
else if (op == 'r') tr.put(sname, new edge(0, fname.substring(0, len - 7)));
// 如果是其他人的男
else if (op == 'm') tr.put(sname, new edge(1, ""));
// 如果是其他人的女
else if (op == 'f') tr.put(sname, new edge(0, ""));
}
int m = sc.nextInt();
while (m-- > 0)
{
String sname1 = sc.next();
String fname1 = sc.next();
String sname2 = sc.next();
String fname2 = sc.next();
// 判断两个人是否有一个人不在名单内
if (!tr.containsKey(sname1) || !tr.containsKey(sname2)) out.println("NA");
// 判断两个人是否同性
else if (tr.get(sname1).sex == tr.get(sname2).sex) out.println("Whatever");
else out.println(check(sname1, sname2));
}
out.flush();
out.close();
}
static class edge
{
int sex; // 性别
String fname; // 姓(也就是父亲的名)
public edge(int sex, String fname)
{
this.sex = sex;
this.fname = fname;
}
}
static Scanner sc = new Scanner(System.in);
static PrintWriter out = new PrintWriter(System.out);
}
c++
#include <iostream>
#include <unordered_map>
#define PIS pair<int, string>
using namespace std;
const int N = 1e5 + 10;
unordered_map<string, PIS> mp;
string check(string a, string b)
{
int cnt1 = 0;
while(a != "")
{
int cnt2 = 0;
string c = b;
while(c != "")
{
if(a == c && (cnt1 < 4 || cnt2 < 4)) return "No";
if(cnt1 >= 4 && cnt2 >= 4) return "Yes";
c = mp[c].second;
cnt2 ++;
}
a = mp[a].second;
cnt1 ++;
}
return "Yes";
}
int main()
{
int n; cin >> n;
while(n -- > 0)
{
string a, b; cin >> a >> b;
if(b.back() == 'n') mp[a] = {1, b.substr(0, b.size() - 4)};
else if(b.back() == 'r') mp[a] = {0, b.substr(0, b.size() - 7)};
else if(b.back() == 'm') mp[a] = {1, ""};
else if(b.back() == 'f') mp[a] = {0, ""};
}
int m; cin >> m;
while(m -- > 0)
{
string a, b, c, d; cin >> a >> b >> c >> d;
if(!mp.count(a) || !mp.count(c)) cout << "NA\n";
else if(mp[a].first == mp[c].first) cout << "Whatever\n";
else cout << check(a, c) << "\n";
}
return 0;
}