PTA天梯赛L2-031冰岛人题解：五代祖先判断与字符串处理实战

PTA天梯赛的L2-031“冰岛人”是我当年在赛场上差点翻车的一道题。第一次读题的时候被那一堆“sson”“sdóttir”和五代以内的判断绕得头晕甚至在纸上画了半天“到底谁是爸爸”。后来冷静下来把逻辑拆开才发现它其实是“看着唬人、做起来有套路”的典型代表最后AC满分也就二十多分钟的事。今天就把这道25分题的完整思路、核心代码和踩坑记录整理出来想帮正在刷天梯赛的朋友少走点弯路。1. 题目背景与核心考点分析1.1 冰岛人的命名规则与题目建模先说文化背景。冰岛人的姓不是我们熟悉的“家族固定姓”而是父名制一个男孩的姓氏是“父亲的名字 sson”女孩的姓氏是“父亲的名字 sdóttir”。举个例子如果父亲叫Eric那他的儿子可能叫Leif Eriksson女儿可能叫Freya Eriksdóttir。也就是说看见一个人的姓氏你就能反推出他爸爸的名字。题目输入时会给每一个人的名、姓、性别m/f。如果姓以“sson”结尾说明这个人是男性且前面那一段就是父亲的名如果姓以“sdóttir”结尾说明这个人是女性前面那一段同样是父亲的名。如果姓不是这两种后缀说明题目没有提供这个人的父名信息那他就是一个“祖先节点”家谱关系到他这里就断了。所以这道题的数据结构非常清晰每个人只需要记录性别和一个指向父亲的指针。虽然冰岛人的称呼里“名”才是个人标识但建关系时其实是在建一棵棵“只往上看”的树。一个人可能有多个孩子但父亲只有一个这种结构用map存父亲名字就足够完全不需要建图、不用邻接表、不用遍历整棵树。这里有个值得强调的细节不要把“姓”当成普通的家族姓氏去处理。很多刚开始刷这道题的人会下意识地把姓当成一个家族的标志结果发现两个人姓氏不同也可能有亲戚关系姓氏相同反而可能没关系。想明白“父名制”之后才会意识到这题的本质是“顺着父亲链向上找人”。1.2 这道题到底在考什么按照PTA天梯赛的难度分布L2的题一般不会硬啃复杂算法更侧重考查把实际问题转化成代码的能力。“冰岛人”的考点很集中字符串后缀判断与截取。基于“父亲指针”的祖先链查询。边界条件的完整判断尤其是“信息不全”时怎么输出Maybe。它看起来像是一道图论题因为“家谱”“祖先”“五代以内”这些词很容易让人想到LCA、并查集之类的算法。但比赛时不能一上来就套高级数据结构。题目只要求判断五代以内每个人向上最多走5步那直接用循环就能解决根本没有必要做什么倍增、树剖。这种“读题被吓到实际做法很朴素”的特点正是天梯赛L2的典型风格。2. 解题思路拆解从题意到可运行算法2.1 “五代以内”的精确定义题目说的“五代以内有共同祖先”需要先定清楚。按照冰岛人的传统从一个人自己开始算第一代父母是第二代祖父母是第三代曾祖父母是第四代高祖父母是第五代。举个具体的例子第1代我 第2代父亲 第3代祖父 第4代曾祖父 第5代高祖父所以判断两个人五代以内是否有共同祖先其实就是把这两个人各自的这5个节点分别列出来看两个集合有没有交集。有交集说明在五代以内有共同祖先不能结婚没有交集且信息完整说明可以结婚。这里我特别想提醒一个容易踩的坑祖先节点集合一定要包含“自己”。为什么因为题目里没有排除“一方是另一方五代以内的直系祖先”这种情况。比如查询A和B如果A是B的高祖父那么B的祖先链里有AA的祖先链里第一项就是A自己两边一碰撞就发现共同祖先是A直接输出No。这个逻辑只有在你把“自己”也放进集合里时才是对的。如果不包含自己那就漏掉了这种直系血缘在五代内的情况输出结果就会错误。2.2 查询的完整判断流程每一个查询给出的格式是“名字1 姓1 名字2 姓2”姓在这里其实可以忽略因为人的关系是靠名字唯一标识的。完整的判断流程分三步第一步判断性别。如果两个人性别相同直接输出“Whatever”因为冰岛不允许同性结婚。这个判断必须放在最前面。如果把性别判断放后面很可能在两个人性别相同但又有共同祖先时输出No那就不符合题目的输出优先级了。第二步分别取两个人在五代以内的祖先链。具体做法是从当前名字开始不断向上找father最多找5个节点。在找的过程中要记录一个标志位表示祖先链是否完整。如果向上找的过程中还没找满5个节点某个人的father就已经为空了说明信息到此中断标志位置为不完整如果恰好找满了5个节点即使第5代祖先的father为空也不影响因为五代以内已经全部覆盖不需要再往上看了。第三步把第一个人的祖先节点放进一个哈希集合然后遍历第二个人的祖先节点。只要发现某个节点在集合里就说明两人在五代以内有共同祖先输出No。如果遍历完没有任何交集再看标志位任意一方的祖先链不完整就输出Maybe因为信息不足以判断更早的祖先关系如果双方祖先链都完整说明五代以内确实没有共同祖先输出Yes。这个流程看起来简单但“标志位”的细节一定要写对。很多变式写法里会把“第5代祖先的father为空”也算作不完整这是不对的。我们只需要五代以内第5代就是边界边界之外的信息没必要知道。判断条件应该写成如果循环还没走到第5步i小于4时father就为空标记不完整如果已经取了5个节点就算father为空也没关系。2.3 复杂度和数据结构选型每次查询最多取10个节点做一次哈希集合插入和一次哈希集合查找时间复杂度是O(1)级别的常数操作。建树时每个人需要插入一次map复杂度是O(n log n)。题目给的n最大也就1e5量级完全跑得动。有人可能会纠结用map还是unordered_map。我的建议是用map就够了代码更稳不需要纠结字符串哈希会不会被卡。因为查询阶段每个人最多做常数次查找哪怕map的log因子也不会造成性能压力。用unordered_map也不是不行但没必要为了这点性能增加不确定性。做题稳是第一位的。3. 核心代码实现与踩坑点3.1 数据结构与建树代码一个人需要保存的信息就两个性别、父亲名字。用结构体表示struct Person { char sex; // m 或 f string father; // 父亲的名字空串表示没有信息 };整体用mapstring, Person把名字映射到个人信息。读入时先存性别再根据姓氏后缀判断父亲。建树的代码长这样#include bits/stdc.h using namespace std; struct Person { char sex; string father; }; mapstring, Person people; bool hasSuffix(const string s, const string suffix) { return s.size() suffix.size() s.compare(s.size() - suffix.size(), suffix.size(), suffix) 0; } int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin n; for (int i 0; i n; i) { string name, surname, sex; cin name surname sex; people[name].sex sex[0]; if (hasSuffix(surname, sson)) { people[name].father surname.substr(0, surname.size() - 4); } else if (hasSuffix(surname, sdóttir)) { people[name].father surname.substr(0, surname.size() - 6); } else { people[name].father ; } } // 查询部分后续补上 return 0; }注意这里处理“sdóttir”时用的是hasSuffix来判断而截取父亲名字时我写的是surname.size() - 6。这就要说到一个非常隐蔽的坑见3.4节。先继续说正常逻辑。3.2 祖先链获取函数祖先链函数是整道题的灵魂它会返回最多5个节点并告诉调用方这5个节点是不是完整覆盖了五代以内。代码写出来长这样vectorstring getAncestors(const string name, bool complete) { vectorstring anc; complete true; string cur name; for (int i 0; i 5; i) { auto it people.find(cur); if (it people.end()) { complete false; break; } anc.push_back(cur); if (it-second.father.empty()) { if (i 4) { complete false; } break; } cur it-second.father; } return anc; }这段代码里有几个关键判断值得细说。第一for循环最多跑5次对应自己、父亲、祖父、曾祖父、高祖。第二如果某一次在map中找不到当前节点说明这个人的信息缺失这属于异常情况标记complete false稳妥一点。第三如果father为空就要看当前是第几代。如果已经取到第5个节点也就是i 4时第五代已经覆盖完整不需要再往上找了所以complete保持true如果是更早的代数就断了比如取到祖父这一代时发现祖父的father为空那就无法继续判断更早的祖先complete置为false。3.3 查询主逻辑有了祖先链函数查询部分就非常直接了int m; cin m; while (m--) { string n1, s1, n2, s2; cin n1 s1 n2 s2; if (people[n1].sex people[n2].sex) { cout Whatever\n; continue; } bool c1 false, c2 false; vectorstring anc1 getAncestors(n1, c1); vectorstring anc2 getAncestors(n2, c2); unordered_setstring st(anc1.begin(), anc1.end()); bool hasCommon false; for (const string name : anc2) { if (st.count(name)) { hasCommon true; break; } } if (hasCommon) { cout No\n; } else if (!c1 || !c2) { cout Maybe\n; } else { cout Yes\n; } }有个细节值得注意查询输入里会给出两个人的姓但代码里完全没用它。因为一个人的身份通过名字就可以定位。如果你担心有重名问题可以考虑用“名姓”一起去map里查但原题的数据保证不会出现这种歧义直接用名字索引就够了。3.4 字符串后缀的UTF-8陷阱这一节是全文最想提醒大家的部分。可能很多人看到“sdóttir”里的ó没什么感觉但它在C的std::string里并不像人眼看到的“一个字母”那么简单。ó在UTF-8编码下占两个字节所以字符串sdóttir在C里的size()不是7而是8。如果你用固定长度去截取父名比如写成surname.substr(0, surname.size() - 7)那截出来的父亲名字末尾就会多出一个奇怪的字节查询时永远匹配不上正确的人结果全错。这个问题在本地测试时很难发现因为编译和运行都不会报错只会让你对着错误输出发呆。正确做法是不要写死长度而是先定义好后缀字符串然后用后缀字符串的size()去截取。比如上面的代码可以先在读取时这样处理string suffix sdóttir; if (hasSuffix(surname, suffix)) { people[name].father surname.substr(0, surname.size() - suffix.size()); }这样无论sdóttir在内存里占几个字节都能得到正确的前缀。至于sson是全ASCII字符长度固定是4直接用size() - 4没有风险。这就是我在代码里只对“sson”写死、对“sdóttir”用变量长度的原因。在评论区或者题解里你还会看到有人用ends_with来判断后缀那是C20的写法。天梯赛的编译器不一定支持保险起见还是自己写一个hasSuffix函数兼容性最好。4. 常见问题与调试经验4.1 为什么总是在“Maybe”和“Yes”之间纠结很多同学写完代码测样例发现“Maybe”的情况总是拿不准。这里我提供一个近乎万能的判断标准一个查询如果最后没有输出No那么只要两个人的祖先链中任意一条“没走满5代就断了”就输出Maybe只有两条链都完整地走到了第5代才输出Yes。举个例子A的祖先链只到祖父就断了B的祖先链完整且两人在五代内没有交集。这时候虽然B的信息很全但A往上第4代、第5代的信息未知你无法保证A的高祖会不会恰好和B的高祖是同一人所以只能输出Maybe。这个逻辑想通之后代码里就是!c1 || !c2一个条件的事。4.2 性别判断放后面会有什么问题题目要求同性输出“Whatever”这个输出优先级是高于血缘判断的。假如两个男生正好五代内有共同祖先如果你先做了血缘判断就会输出No但题目期望的是Whatever。所以性别判断一定要放在最前面这一点没有任何商量余地。我在第一次写的时候就是因为先判断了血缘导致一组同性数据挂了。后来debug时才发现输出顺序和预期不一致。这种错误不属于算法难度纯粹是读题不仔细。4.3 本地测试样例怎么构造刷题遇到这种容易出细节问题的题目一定要会自己造数据。我建议按三个维度构造测试用例常规的祖先关系比如兄弟、堂兄弟、祖孙验证No。祖先链在第2代或第3代就断掉的情况验证Maybe。两条完整链但五代内无交集验证Yes。一个可以跑通的简单样例7 A Bsson m B Csson m C D m E Fsson m F Gsson m G H m I J m 1 A E Even?当然这个样例只是演示性质的实际要根据你自己的代码去设计。重点是覆盖“同性”“五代内共同祖先”“祖先链中断”三种核心分支。4.4 不要用递归DFS去遍历祖先有些人一看到“家谱”就想到递归建树、DFS统计深度。这道题完全没必要因为每个节点只有一个父亲而且向上最多只需要5层一个5次的for循环就能解决。递归反而会带来两个问题一是代码变复杂二是极端数据下可能栈溢出。天梯赛是团队赛现场时间紧张能用循环就不要用递归。这道题的考察点不在树的遍历上把精力浪费在写一个花哨的DFS上完全没必要。5. 现场做题的一点体会这道题在L2里属于“读题劝退、实操友好”的类型。比赛的时候如果一开始看懵了建议先跳过去做后面分值更稳的题最后留十分钟回来慢慢捋。我个人习惯是先在草稿纸上写出输入样例对应的父子链把“名 - 父亲名”的对应关系列清楚再动手写代码。画完那几条链之后思路基本就通了。另外说一个实战小技巧代码里对“sdóttir”这种含非ASCII字符的后缀最好提前在本地编译器里验证一下size()到底是多少。不要想当然地按肉眼看到的字符数去写截取长度。这类字符串编码问题在天梯赛里不算罕见多留个心眼能少浪费很长时间。如果能耐下心把这道题的“五代以内”“信息不全”两个点彻底搞透以后再遇到类似的树上祖先判断题目你会发现套路都是一样的确定步数上限循环向上找用集合判交集用标志位处理未知情况。希望这篇解析能帮你少踩几个坑顺利AC拿满25分。