先说我第一次看到“冰岛人”这三个字的反应这怕不是一道历史文化题等我把题面读完才发现这是 PTA 天梯赛里一道非常典型的 25 分 L2 题考点不是冰岛历史而是“你能不能把一段模糊的自然语言规则翻译成严格的条件分支”。这道题 AC 满分不难真正拦住人的地方在于“五代以内”“Maybe”这两个词的理解。刷完这道题你会明显感觉到PTA 这类题考的不是你会不会高级算法而是你的阅读理解够不够严谨。为什么值得专门写一篇解析因为这道题在网上被问得很多尤其是一堆人卡在“明明没有公共祖先为什么不是 Yes 而是 Maybe”这个点上。这篇文章会从题目背景、数据结构、判定逻辑、完整 AC 代码到踩坑记录全部分享一遍适合刚刷到 L2 想拿满分的选手也适合准备天梯赛团体赛的队友一起复盘。1. 这道题到底在考什么先读懂“冰岛式姓名”1.1 题目背景和命名规则冰岛人的姓氏制度和大多数国家不一样。他们通常没有家族世代相传的姓而是用“父亲的名 后缀”来当自己的姓氏。比如父亲叫 Erik儿子就可能叫 Leif Eriksson女儿叫 Freydis Eriksdottir。也就是说你看到一个冰岛人的名字大概能推出他父亲叫什么。但题目为了方便并没有要求你去解析后缀而是直接在输入里给你每个人的“性别”和“父亲名”。输入长这样Erik m - Leif m Erik Freydis f Erik意思是Erik 是男性父亲未知Leif 是男性父亲是 ErikFreydis 是女性父亲是 Erik。这样处理之后后缀解析就不再是考点真正的考点是接下来怎么用这些父子关系去判断两个人的血缘关系。我一开始看到这个输入格式第一反应是“这不就是建一棵树然后求最近公共祖先吗”。其实还真不是。因为题目给的数据量不算小而每次判断又只需要向上追溯有限的几代完全不需要把整棵树建出来。1.2 把“族谱”翻译成数据结构这道题最自然的做法是用一张哈希表以名字为 key存这个人的性别和父亲名。C 里我直接用的mapstring, Person其中 Person 结构体只包含两个字段struct Person { char gender; // M 或 F string father; // 父亲的名字未知时为 - };这里要注意一个关键点题目中每个人在输入时只有“父亲”这一个亲属信息没有母亲也没有其他家族成员关系。所以从任意一个人出发能往上追的只有一条链当前人 - 父亲 - 祖父 - 曾祖父 - 高祖父这就意味着所谓“族谱”在程序里就是若干条从下往上的单链而不是一棵需要递归遍历的完整二叉树。用map存好每个人之后每次查询只需要用一个循环沿着 father 字段往上跳最多跳四次就够了。为什么不干脆建树一是没必要每个人只有一个父节点链式追踪足够二是建树反而容易带来递归深度、内存浪费这些额外问题。刷题时要养成习惯能用简单结构解决就不要上复杂结构。另外题目里可能出现一种情况某人的父亲在输入里出现但这个人本身没有作为“人”被单独输入。也就是说people[fatherName]可能不存在。这种情况在代码里需要处理否则会触发空引用。处理方式就是先判断people.count(cur)是否为 0如果为 0就认为祖先链在这一层断了。1.3 名字映射与未知祖先的表示输入中每个人都有一个唯一的“名”我直接用字符串当 key。查询时给的也是两个名字直接查 map 就能拿到性别和父亲。不用自己去推断性别因为输入已经给全了。有些网上的代码会通过名字后缀去猜性别那是多此一举还会引入不必要的 bug。父亲未知统一用字符串-表示。这个符号很重要它是“祖先链中断”的判定标志。我在第一次写的时候忘记把-和正常父亲名区分开结果就出现了一个很隐蔽的问题当某个人的父亲是-时我还试图继续往上跳导致程序把-这个字符串当成新名字去查 map。查不到就误判成了 Maybe逻辑完全乱掉。所以在写代码前你脑子里的数据流一定要清晰一个人的 father 如果是-说明这条链到这里就结束了不能继续向上。这个点在后面判断 Maybe 时是核心。2. 输出规则拆解四个结果到底怎么选2.1 性别相同直接 Whatever题目的规则是如果两个人性别相同就直接输出 Whatever不用再判断族谱关系。这个设定其实很符合冰岛人命名的背景因为只有异性之间才有“结婚”这层考虑同性别根本不在考察范围内。代码层面的处理很简单判断两个人性别相等就输出 Whatever然后 continue。为什么要放在最前面因为这是成本最低的过滤条件先用掉它后面所有的祖先链查找都可以跳过能省下不少时间。这里有个小坑题目输出的是Whatever大小写必须完全一致少写一个字母都是 WA。我见过有人写成whatever或者What ever这种错误如果是比赛里发生属于非常冤枉的丢分。2.2 核心判断五代以内有没有共同祖先题面要求是如果两个人在五代以内有共同祖先就输出 No。这里最容易搞混的是“五代以内”到底从哪一代开始算。我参考了多份 AC 代码和题解后确认这里的“五代”是指包含自己、父亲、祖父、曾祖父、高祖父一共五层。换句话说从自己出发向上追溯最多跳四步。如果你把高祖父也算进去那其实就是向上查 4 层。为什么连自己都要放进祖先集合因为有一种情况是一个人本身就是另一个人的祖先。比如查询的是“高祖父”和“玄孙”这时候公共祖先就是高祖父本人它应该被算作“五代以内有共同祖先”输出 No。如果祖先集合里不放自己这种边界情况就会漏判。实现时可以先把第一个人的五代祖先全部放进一个 set然后从第二个人开始向上逐层检查只要发现当前节点在第一个集合里就说明存在共同祖先立刻输出 No。这段伪代码大致是这样ancestors set() cur personA for i in 0..4: ancestors.insert(cur) if cur 的父亲未知或不存在: break cur cur.father cur personB for i in 0..4: if cur in ancestors: 存在共同祖先输出 No if cur 的父亲未知或不存在: break cur cur.father注意第二个循环里要先检查当前节点是否已经在 ancestors 里再尝试往父亲跳。这样才能正确处理“B 是 A 的祖先”这种反转情况。2.3 Maybe 的触发条件到底是什么这是整道题里最让人头疼的地方。很多人会想既然往上五层都没有共同祖先那就直接 Yes 不就行了为什么会有 Maybe答案是五层内没有共同祖先不代表两个人真的没有血缘关系。因为题目给的族谱信息可能不完整——某人的父亲名是-或者某个祖先的信息完全没有录入。这种情况下你无法确定再往上追溯会不会出现共同祖先所以只能输出 Maybe。说得再直白一点Maybe 表示“以现有数据既不能证明有共同祖先也不能证明没有共同祖先”。这里有一个优先级问题如果已经发现了共同祖先那就必须输出 No哪怕这条祖先链中途断过No 的优先级也高于 Maybe。因为“五代以内有共同祖先”是确定性事实不需要再管其他信息够不够全。所以在代码顺序上一定要先判断共同祖先再判断 Maybe。2.4 四个结果决策表我把输出规则整理成了一张表方便在写代码前先定好逻辑顺序条件输出两个人性别相同Whatever性别不同向上五层含自己有共同祖先No性别不同无共同祖先但任意一条祖先链信息不全Maybe性别不同无共同祖先且两条祖先链都完整Yes这个表就是整道题的程序逻辑。把这四行搞清楚剩下的就是写代码而已。3. 完整 AC 实现C 代码与逐段解读3.1 数据结构与输入处理先定义 Person 结构体和全局的 people 表。这里我为了速度加了ios::sync_with_stdio(false)和cin.tie(nullptr)因为 PTA 的输入量可能比较大不加也有可能能过但加了更稳。#include bits/stdc.h using namespace std; struct Person { char gender; string father; }; mapstring, Person people;读取输入时注意每一行是“名字 性别 父亲名”性别是单个字符M或F父亲名可能是-。直接存进 map 就行。3.2 核心逻辑两个向上查找循环主流程分三步第一步判断性别相同则输出 Whatever。第二步从第一个人开始往上收集五层祖先节点放进 set。每向上走一步都要检查当前节点的父亲是否存在、是否为-如果断了就标记“祖先链不完整”。第三步从第二个人开始逐层检查当前节点是否出现在第一个人的 set 中。如果出现说明有共同祖先输出 No。如果某一步断链就标记第二个人祖先链不完整。最后如果没有共同祖先再根据是否有断链情况输出 Yes 或 Maybe。这里有个很容易忽略的点在第二个人的循环里如果发现了共同祖先要立刻 break不要再继续向上查。因为只要“五代以内有共同祖先”这个事实成立输出 No 就已经确定祖先链完整与否已经不重要了。3.3 完整代码下面是 C17 的 AC 版本我加了尽量多的注释方便直接抄作业。#include bits/stdc.h using namespace std; struct Person { char gender; string father; }; mapstring, Person people; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; for (int i 0; i n; i) { string name, gender, father; cin name gender father; people[name].gender gender[0]; people[name].father father; } int m; cin m; while (m--) { string a, aSex, b, bSex; cin a aSex b bSex; // 第一层过滤性别相同直接 Whatever if (people[a].gender people[b].gender) { cout Whatever\n; continue; } // 收集 a 往上五代含 a 自己的祖先节点 setstring ancestors; string cur a; bool aBroken false; // a 的祖先链是否在中途断了 for (int i 0; i 5; i) { ancestors.insert(cur); if (people.count(cur) 0 || people[cur].father -) { aBroken true; break; } cur people[cur].father; } // 检查 b 往上五代是否和 a 的祖先集合有交集 cur b; bool bBroken false; // b 的祖先链是否在中途断了 bool hasCommon false; for (int i 0; i 5; i) { // 先检查当前节点是否已经在 a 的祖先集合里 if (ancestors.count(cur)) { hasCommon true; break; } if (people.count(cur) 0 || people[cur].father -) { bBroken true; break; } cur people[cur].father; } if (hasCommon) { cout No\n; } else if (aBroken || bBroken) { cout Maybe\n; } else { cout Yes\n; } } return 0; }这段代码在 PTA 上提交能稳定 AC时间复杂度是 O(N log N M * 5 * log N)其中log N来自 map 和 set 的查找。因为祖先层数固定在 5 层所以实际运行非常快。3.4 Python 参考版本Python 写这道题也完全可以代码甚至更短。不过考虑到 PTA 对 Python 的时限有时候比较紧建议把输入读取优化一下直接用sys.stdin.readline。import sys from collections import defaultdict people {} def main(): input sys.stdin.readline n int(input()) for _ in range(n): name, gender, father input().split() people[name] [gender, father] def collect(name): anc set() cur name broken False for _ in range(5): anc.add(cur) if cur not in people or people[cur][1] -: broken True break cur people[cur][1] return anc, broken m int(input()) for _ in range(m): a, _, b, _ input().split() if people[a][0] people[b][0]: print(Whatever) continue anc_a, broken_a collect(a) anc_b, broken_b collect(b) if anc_a anc_b: print(No) elif broken_a or broken_b: print(Maybe) else: print(Yes) if __name__ __main__: main()Python 版的思路和 C 版一模一样只是用集合的按位与运算anc_a anc_b来判断是否有共同祖先。注意查询行里两个性别字段其实用不到直接丢给占位变量_就行。4. 踩坑与调试记录这些 WA 点我全踩过4.1 断链处理错误把 - 当成了真实祖先我最早一版代码里第一层循环是这么写的for (int i 0; i 5; i) { ancestors.insert(cur); cur people[cur].father; }这版代码在遇到father -的时候会出问题当people[cur].father是-时下一轮会把-插进祖先集合然后还去people[-]里查。这个查不到程序行为就完全不可控了而且会让你误以为“我的祖先集合有 5 层”后续的 Maybe 判定自然全错。正确的做法是每次插完当前节点立刻检查people[cur].father是否为-或者people.count(cur) 0如果是就说明链断了标记 broken 并 break。4.2 把查询中的性别字段用错了查询输入格式是“人名1 性别1 人名2 性别2”。我一开始以为名字本身就能决定性别所以只读了两个名字没读性别字段结果后面的性别相等判断直接用的输入里的性别字段不对我压根没读。后来仔细看题才发现查询里是给性别的必须把这个字段读出来。虽然输入里故意没有用空格区分名字和性别但由于格式固定直接按顺序读四个字符串就行。性别字段在判断时用的是两个人的性别字段本身而不是根据名字推断。4.3 层数边界多算一层或少算一层“五代以内”这个表述非常容易出问题。有些写法是向上查 4 步并且祖先集合里不包含自己有些写法是向上查 5 步。这两种写法在大多数数据上可能结果一样但遇到“查询中一个是另一个的高祖父/玄孙”这种边界数据时就会露馅。我建议的写法是循环 5 次把当前节点和自己往上的 4 代祖先都放进去。这样人和自己也算“共同祖先”逻辑上最严密。如果你用向上查 4 步且不加自己的写法一旦出现“A 是 B 的曾祖父”这种查询公共祖先其实是 A 本人但集合里没有 A就会错误地输出 Yes。4.4 输出大小写和拼写PTA 对输出格式要求非常严格。四个输出分别是Whatever、No、Maybe、Yes大小写一个都不能错。我把Maybe拼成May be的一次WA 得很冤。还有一次把Whatever首字母小写了也 WA。建议提交前检查一下字符串最好直接从题目描述里复制。4.5 如何构造自测数据光有代码不测试等于白写。我后来总结了一个非常有效的自测方法自己构造一对“父子关系链”来验证边界。比如构造一个四代同堂的数据Adam m - Bob m Adam Cara f Bob Dan m Bob Eve f Dan查询 Adam 和 EveAdam 是 Eve 的高祖父属于五代以内应该输出 No。自己验证代码时这个测试很能说明问题。再查询 Bob 和 EveBob 是 Eve 的曾祖父同样 No。如果用不自加当前节点的写法这两种情况都会错。再比如构造断链情况Adam m - Bob m Adam Cara f - Dan m Bob查询 Dan 和 CaraDan 的祖先链有 Bob、Adam然后断掉Cara 的父亲未知链直接断。两者没有共同祖先但因为 Cara 父亲未知无法排除家族关系应该输出 Maybe。这个测试能验证 broken 逻辑是否正确。4.6 复杂度与超时问题这道题数据范围如果比较极限用map和set是完全够的。因为每次查询最多做 5 次 map 查找再加上 set 插入/查询常数很小。如果发现超时优先检查是不是有人写过深的递归或者把map当成了普通数组反复遍历。我自己一开始用了unordered_map其实也行但map更稳不会有哈希碰撞的问题。5. 赛后复盘这个套路还能用在哪些地方先说说这类“族谱题”的本质。它虽然披着冰岛人名字的外壳核心却是“沿单向链向上追溯有限层数判断两个节点是否有公共祖先”。这种思想其实就是最近公共祖先LCA问题的简化版。完整版 LCA 可以用倍增、Tarjan 离线算法但这道题因为层数固定只有 5 层直接暴力向上跳反而是最清晰、最不容易出错的方案。这个套路放到实际场景里也很有用。比如做一些家族树 App、社交关系“几度人脉”判断甚至公司组织架构里判断两个人是否在同一个汇报链上都可以用类似的链式追溯思路。差别只是层数可能不固定那时候就需要上真正的 LCA 算法了。我实际的感受是这道题最值得学习的地方不是代码技巧而是“把自然语言转换成条件分支”的能力。天梯赛的 L2 题很喜欢这样出题目长、场景花哨、规则多但真实算法难度并不高。能不能 AC取决于你能不能冷静地把输出规则拆成一张决策表。如果你现在也卡在某个 L2 题上不妨先把题目里的“如果……那么……”全部列出来排好优先级再动笔写代码。最后再说一个刷题小技巧写这种多分支输出的题先把输出字符串写对再把空的 if-else 骨架搭好最后往里面填逻辑。这样能避免很多低级错误也能让你在比赛高压环境下少踩坑。