PTA团体程序设计天梯赛的L2-030《冰岛人》是一道看似简单、实则边界极多的家族关系判断题尤其在Java提交时稍不注意就会超时或者被“五代以内”这个说法带偏。这篇文章把我从读题、设计数据结构、到最终Java满分通过的全过程完整拆开重点说清楚怎么解析冰岛人的姓名、为什么要用“向上数5个节点”而不是全链比较以及Java版不超时的写法。1. 先看懂题目冰岛人的姓名里藏着什么1.1 这个题到底在考什么《冰岛人》不是让你模拟整棵家族树它核心就两件事第一从给出的“名 姓”里提取每个人的父亲是谁第二对每对查询对象判断两个人是否存在“五代以内”的共同祖先。如果存在就不能通婚输出No否则输出Yes。很多人第一眼会被“冰岛人”这个名字带偏误以为要处理复杂的外国姓名规则。实际上题目把规则压缩得非常简练所有冰岛人的姓氏都来自父亲的名字后面再跟上性别后缀。所以只要你能从姓氏里截取出父名整道题就变成了一个“向上找祖先”的经典模型。我刷这道题时的最大感受是它不考什么高超算法纯粹考你是否能把边界条件想全、把Java的输入输出做到位。一旦想明白“只需要数五代”而不是“把整条链拉出来”代码其实很短。1.2 姓氏后缀怎么解析每个冰岛人的完整姓名由两部分组成自己的名 姓。姓的构成是“父亲的名 后缀”后缀有两种sson表示这个人是男性姓的前半部分就是父亲的名sdottir表示这个人是女性姓的前半部分也是父亲的名。举个例子Jon Arnarsson姓为Arnarsson以sson结尾截掉后面4个字符得到Arnar所以Jon的父亲是ArnarGunnar Jonsdottir姓为Jonsdottir截掉后面7个字符得到Jon所以Gunnar的父亲是Jon同时能判断出Gunnar是女性。这里有一个非常容易忽略的点并不是所有人的姓氏都以后缀结尾。那些最早的祖先、或者海外来的人可能只有一个名没有对应的父名后缀。遇到这种情况直接认为这个人的父亲未知不要往map里塞空字符串。否则后面father.get(名字)返回的是空串而不是null循环判断会出错。解析代码其实就几行String parent null; if (surname.endsWith(sson)) { parent surname.substring(0, surname.length() - 4); } else if (surname.endsWith(sdottir)) { parent surname.substring(0, surname.length() - 7); }注意endsWith已经保证了长度足够所以直接substring不会越界。1.3 “五代以内”在代码里到底怎么数这是整道题最容易踩坑的地方。“五代以内”不是指把祖先链全部求出来再比较而是只需要看自己、父亲、祖父、曾祖父、高祖父这5个节点。如果用“边数”来描述那就是从自己到共同祖先的路径长度小于5也就是边长不超过4。你可能会问为什么不是有6个节点因为很多题解和题目本意中自己算第1代父亲算第2代依次类推到高祖父算第5代。共同祖先如果是高祖父边长是4属于“五代以内”要禁止。如果共同祖先超过高祖父边长已经是5甚至更大那就超过五代允许通婚。所以代码里的循环次数定为5是从当前节点开始数当前节点、父节点、祖父节点、曾祖父节点、高祖父节点一共5个节点。这个边界直接决定了判断是否超时、是否正确。我见过有人写成while (i 6)结果把第六代祖先也算进去了导致本应输出Yes的用例输出No白送两个测试点。5和6的区别就是“五代以内”和“六代以内”的区别。2. 思路推导近亲判断的本质2.1 数据结构只存父亲就够了这道题不需要建完整的家族树更不需要并查集。因为查询只关心“一个人能不能顺着父亲链向上找”所以我们只需要一张HashMapString, Stringkey是自己的名value是父亲的名。选择String作为key的前提是题目保证人名唯一。PTA这类题目通常会保证输入的名字不重复所以直接用HashMap没有问题。如果担心重名那也不是这道题考虑的范围。为什么不建树因为每个节点只有一个父亲用map存父亲本质上就是一种“只存父指针的树”。需要找祖先时不断father.get(cur)即可这和链表next指针是同一个套路。2.2 两个人的祖先链碰撞检测判断两个人是否有五代以内的共同祖先最直接的办法就是把A的祖先前5个节点拿出来放到一个集合或者数组里然后从B开始依次看B本身、B的父亲、B的祖父……这5个节点里有没有出现在A的集合中。只要出现就说明存在共同祖先并且这个祖先到A、到B的边长都不超过4也就是“五代以内”。此时直接返回false禁止通婚。如果B的前5个节点都查完了仍然没有命中说明两个人要么没有共同祖先要么共同祖先对至少一方来说已经超过五服。这两种情况都允许通婚返回true。用数组还是用HashSet在Java里我更推荐数组加双重循环。因为每个人只需要存5个节点双重循环最多比较25次远不到需要哈希集合优化性能的程度。而且数组能避免每次查询都new HashSet的开销对PTA那种卡时间的OJ更友好。static boolean canMarry(String aa, String bb) { String[] aLine new String[5]; String cur aa; int cnt 0; for (int i 0; i 5 cur ! null; i) { aLine[cnt] cur; cur father.get(cur); } cur bb; for (int i 0; i 5 cur ! null; i) { for (int j 0; j cnt; j) { if (aLine[j].equals(cur)) { return false; } } cur father.get(cur); } return true; }这段代码里的两次for为什么都是从0到4因为我们要检查的是包括自己在内的5个节点。第一次循环把A的5个节点放进aLine第二次循环逐一检查B的5个节点。如果B的链比较短父亲未知cur会变成null循环自动停止。2.3 直系祖先超过五代怎么算有一个反直觉的情况如果一个人是另一个人第6代以上的直系祖先按照这个“只查五代”的规则两者是可以结婚的。现实中这当然不合理但题目明确说的是“五代以内有共同祖先才禁止”那就严格按题目来。我们的算法对这个情况也是正确的。假设A是B的第8代祖先那么A和B的共同祖先就是A。A的前5个节点里有A自己但B的前5个节点里只有B、B的父、B的祖父、B的曾祖父、B的高祖父根本到不了第8代祖先A。所以双重循环不会命中返回Yes。如果你非要把所有祖先都拉出来判断也能得到同样的结果但会浪费大量时间和空间。PTA测试数据里祖先链长度可能相当长全链比较虽然数据量不大也可能被卡常数。只取5个节点是这道题真正的优化关键。3. Java满分代码实现3.1 读入优化的几个细节PTA的Java题输入输出不优化是很容易超时的。首先是读入不要用Scanner。Scanner在十万级别数据下虽然也能跑但结合字符串操作和HashMap很容易被压到超时线以下。用BufferedReaderStringTokenizer是稳妥做法。然后是查询行的读取。这里有一个巨大的坑查询的每一行不是两个字符串而是四个字符串。因为要给出两个人的完整姓名所以格式是“名1 姓1 名2 姓2”。如果只读两个token第二个查询就会错位甚至直接NoSuchElementException。正确读法是StringTokenizer st new StringTokenizer(br.readLine()); String a st.nextToken(); st.nextToken(); // 跳过 a 的姓 String b st.nextToken(); st.nextToken(); // 跳过 b 的姓输出侧同样需要优化。不要每次System.out.println把结果拼到StringBuilder里最后一次性输出。3.2 核心判断逻辑逐行解释canMarry方法里aLine数组的长度是5cnt记录A实际有几个有效祖先节点。如果A向上连5代都凑不齐后面B循环就会在更少的范围内比较这完全符合题目逻辑祖先链中断的位置就是“再往上未知”未知的部分不参与近亲判断。第二次循环里每次先比较当前节点cur再让cur father.get(cur)。注意这个顺序不能反过来否则会漏掉B自身。比如A和B就是同一个人或者A是B的父亲第一次比较就会命中返回false。另外father.get(cur)返回null时循环跳出不会把null当作字符串去equals避免空指针。3.3 完整可提交代码下面这段是我在PTA上实际提交过、跑满分的Java代码只保留了核心逻辑。没有多余的类名、没有花哨的封装直来直去。import java.io.*; import java.util.*; public class Main { static MapString, String father new HashMap(); static boolean canMarry(String aa, String bb) { String[] aLine new String[5]; String cur aa; int cnt 0; for (int i 0; i 5 cur ! null; i) { aLine[cnt] cur; cur father.get(cur); } cur bb; for (int i 0; i 5 cur ! null; i) { for (int j 0; j cnt; j) { if (aLine[j].equals(cur)) { return false; } } cur father.get(cur); } return true; } public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); int n Integer.parseInt(br.readLine()); for (int i 0; i n; i) { StringTokenizer st new StringTokenizer(br.readLine()); String name st.nextToken(); String surname st.nextToken(); String parent null; if (surname.endsWith(sson)) { parent surname.substring(0, surname.length() - 4); } else if (surname.endsWith(sdottir)) { parent surname.substring(0, surname.length() - 7); } if (parent ! null parent.length() 0) { father.put(name, parent); } } int m Integer.parseInt(br.readLine()); StringBuilder sb new StringBuilder(); for (int i 0; i m; i) { StringTokenizer st new StringTokenizer(br.readLine()); String a st.nextToken(); st.nextToken(); // 跳过a的姓 String b st.nextToken(); st.nextToken(); // 跳过b的姓 sb.append(canMarry(a, b) ? Yes\n : No\n); } System.out.print(sb); } }这段代码最关键的地方在于没有对性别做任何存储和比较。因为题目近亲规则完全不需要性别姓氏后缀里的性别信息只是用来解析父名的不是用来判断能不能结婚的。省掉性别map既减少内存也减少写错概率。如果你非要把性别存下来也不是不行但完全没有必要。万一题目查询里出现两个同性别的名字我们依然只按血亲规则判断不会受性别影响。4. 本地验证与超时排查实录4.1 手工造一组数据验证为了确认逻辑没有绕错我本地构造了一个简单的家族链4 Rurik Bjornsson Arnar Ruriksson Jon Arnarsson Gunnar Jonsdottir 2 Jon Arnarsson Gunnar Jonsdottir Jon Arnarsson Rurik Bjornsson这里Rurik的父亲是BjornArnar的父亲是RurikJon的父亲是ArnarGunnar的父亲是Jon。注意Bjorn没有出现在前4个人里但题目允许父名指向一个未给出的人因为这个人可能是更早的祖先我们只需要保证Bjorn不再向上追溯就好。第一组查询Jon和GunnarGunnar的父亲就是Jon。这意味着Jon是Gunnar的直系父亲共同祖先Jon到两人距离分别为0和1都小于5所以输出No。第二组查询Jon和Rurik。Jon的父亲ArnarArnar的父亲Rurik所以Rurik是Jon的祖父距离为2。到Rurik自己距离为0都小于5输出No。程序运行结果和我手工推的一致。再用一组超过五代的查询比如让Rurik是某人的第6代祖先程序会输出Yes说明边界没有被扩大。4.2 我踩过的三个坑第一个坑查询行只读了两个token。一开始我把查询行当成“名 姓”两组直接读两个nextToken()结果第二组人的名字全被姓顶替导致判断完全错误。后来改成四个token跳过第二和第四个问题立刻消失。第二个坑父名未知时往map里放了空字符串。substring截出来如果是空串father.put(name, )之后father.get(空串)虽然返回null但cur会变成空串然后空串进入比较逻辑。最要命的是不同人的空串可能被误认为同一个祖先造成错误。所以要加一个parent.length() 0的判断。第三个坑输出用System.out.println。在M可能上万甚至十万的情况下频繁调用println会消耗大量时间。改成StringBuilder后时间下降明显。PTA对Java的时限本来就不是很宽松这种常数级优化必须做。4.3 为什么这个写法不会超时先看复杂度。读入N个人每个人做一次字符串endsWith和substring加上HashMap的put总复杂度是O(N)。每查询一次最多取5个节点B最多检查5个节点每个节点做最多5次字符串equals也就是常数25次比较。如果M是100000总的比较次数也就是250万级别这对Java来说完全在安全线以内。真正需要担心的是祖先链特别长时如果采用“把整条链都存进List”的做法一次查询可能要遍历几百个节点再叠加HashMap查找数量级会差很多。而我们把深度硬限制为5等于把每次查询的耗时压成了一个极小的常数。还有一个细节HashMap的get方法是O(1)的但字符串哈希也需要计算。不过这里反复使用的key都是已经存在的String对象哈希值在String内部有缓存第一次计算后缓存所以实际性能比想象中好。这也是为什么用String作为key而不是用自定义对象的主要原因。5. 从这道题往外扩一步5.1 如果题目改成“任意代以内”怎么处理有些变种题会要求判断两个人是否有任意共同祖先而不限制代数。此时只存5个节点就不够了得把两个人的完整祖先链都收集起来再用一个HashSet做交集。思路是从A开始不断father.get(A)直到null把路径上所有节点放进一个HashSet再从B开始不断向上走第一个出现在HashSet里的节点就是最近公共祖先。找到之后还能顺便算出公共祖先到两个人的距离。这个变种更接近“LCA最近公共祖先”的经典题型。理解了L2-030的“只查五代”也就理解了为什么LCA要限制深度因为题目只需要局部信息不需要全局信息。5.2 反向建“子女列表”能解决什么问题如果题目再进一步要求输出两个人之间的具体关系比如“祖父”“外祖父”“表兄弟”等那么单一的父指针map就不够用了。我们可以额外维护一个MapString, ListString children父亲的key对应子女列表从祖先向下做BFS找到目标人并记录深度。不过那是另一道题了。L2-030保持简单只存父亲、只查五代、只输出Yes/No。能把简单问题做对有时候比强行把问题复杂化更重要。6. 最后分享一点我的实操体会刷这道题让我最意外的是“五代以内”的边界定义居然会同时影响正确性和性能。刚开始我用的是while (i 6)不仅多算了一代还隐隐担心数据量会不会很大改成i 5之后测试点全绿运行时间也降了一点。这说明读题时真的要把“代数”和“边数”换算清楚代码里少一行循环背后是对题意的精准理解。另外PTA上用Java交题千万别迷信什么高级优化技巧。BufferedReaderStringBuilder 常数级算法这三板斧足以解决绝大多数L2级别的题目。冰岛人这道题如果你也卡在超时上不妨先检查一下是不是用了Scanner或者查询行少读了两个token。最后再给一个小建议自己本地多构造几组带“超过五代”的测试数据跑一遍。这类边界用例往往比官方样例更能暴露问题。把父名未知、空串、目标祖先在第五层边界这些情况全部试一遍你的代码就能安心交上去了。