冰岛人[天梯赛]

文章目录

• 题目描述
• 思路
• AC代码

题目描述

输入样例 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

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33

思路

模拟

存储结构
1.结构体存储每个人的信息，包括父亲的姓名（只针对维京人后裔）以及每个人的性别
2.用map存储每个人姓名到其结构体信息的映射

具体流程
1.判断两人是否都存在 – 一定要首先判断
2.判断两人性别是否相同
3.判断两人是否五代内有公共祖先
①依次遍历每个人的祖先，判断五代内是否有公共祖先，如果超出五代，或者祖先不足5代（不管相同还是不用），则可以交往；否则不可以交往

AC代码

#include using namespace std; typedef struct { char sex; string family_name; }person; map<string, person> mp; bool judge(string a, string b) { int cnta = 1; //统计A祖先的代数 for(string A = a; A.size(); A = mp[A].family_name) { int cntb = 1; //统计B祖先的代数 for(string B = b; B.size(); B = mp[B].family_name) { if(cnta >= 5 && cntb >= 5) return true; //五代之内没有祖先 if(A == B && (cnta < 5 || cntb < 5)) return false; //五代之内有相同祖先 cntb ++; } cnta ++; } return true; //不够五代 } int main() { int n; cin >> n; for(int i = 0; i < n; i ++) { string s1, s2; cin >> s1 >> s2; if(s2.find("sson") != -1) //维京人后裔 男性 { int pos = s2.find("sson"); mp[s1] = {'m', s2.substr(0, pos)}; } else if(s2.find("sdottir") != -1) //维京人后裔 女性 { int pos = s2.find("sdottir"); mp[s1] = {'f', s2.substr(0, pos)}; } else { int len = s2.size(); if(s2[len - 1] == 'm') mp[s1].sex = 'm'; else if(s2[len - 1] == 'f') mp[s1].sex = 'f'; } } int m; cin >> m; while(m --) { string name1, family_name1, name2, family_name2; cin >> name1 >> family_name1 >> name2 >> family_name2; if(mp.find(name1) == mp.end() || mp.find(name2) == mp.end()) cout << "NA" << endl; else if(mp[name1].sex == mp[name2].sex) cout << "Whatever" << endl; else { if(judge(name1, name2)) cout << "Yes" << endl; else cout << "No" << endl; } } return 0; }

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51
• 52
• 53
• 54
• 55
• 56
• 57
• 58
• 59
• 60
• 61
• 62
• 63
• 64
• 65

欢迎大家批评指正！！！