PTA天梯赛L2刷题复盘：模式匹配与数据结构要点

PTA天梯赛的题集，我断断续续刷过一遍之后，前阵子又完整回炉了一遍。这已经是这个系列的第二篇温故笔记，上一篇主要在处理L1的稳定拿分，这次把火力集中在L2区间。为什么单独拎出L2，原因很简单：在天梯赛里L1决定你的下限，L3决定天花板，而L2才是决定队伍真实排名的胜负手。尤其这轮复盘下来我确认了一件事：所谓模式匹配、字符串处理这些考点，从来不会在题面上直白地喊出来，需要你自己从题干里把“模式”这个概念扒出来。这篇文章会把我在L2上重做的题型、踩过的坑、总结出的判定顺序拆开讲一遍，适合正在备赛的队伍，也适合想补基础算法的同学翻一翻。

1. 第二遍刷L2，先做减法再做加法

1.1 L2在全卷里的真实分量

天梯赛的题目分为三个梯度：L1是基础操作，基本就是循环、数组、字符串、简单模拟，只要细心一点就能把分吃满；L3是那些需要复杂算法或高级数据结构的题，AC率常年不高，属于拉开顶尖队伍差距的区间；中间的L2卡着一大批人，因为它考的不是“会不会某个算法模板”，而是“能不能在题目包装下认出这个模板”。

我第一遍刷题的时候有个错觉，觉得L2比L3简单很多，应该轻松拿下。真上强度才发现，L2的代码量往往不大，但边界条件特别多，而且很多题只要忽略一个条件就满盘皆输。比如链表去重、彩虹瓶、简单计算器这几道题，算法难度约等于零，真正难的是把过程模拟得滴水不漏。说白了，L2考的是工程性思维：把一个流程拆成若干个状态，再把这些状态按正确顺序串起来。

所以第二遍温故，我的目标不是“再做一遍”，而是把每道题的核心坑位记成笔记。刷完之后回头看，真正反复出问题的并不是那些需要复杂算法的题，反而集中在几个通用的思路上。

1.2 我的题单分类法与优先级排序

第二轮我不再按题号顺序刷，而是把所有L2题按考察点分了类。下面这个表是我自己整理出来的大方向，不同年份题目编号会变，但考察点基本就这几类：

我建议的复习顺序是：模拟题优先，因为最好拿分且容易建立信心；然后是链表和树，这两类题套路固定，只要模板熟练基本能稳过；接着是并查集和连通性题目，难点在于“怎么把题面翻译成并查集操作”；字符串和较复杂的综合题放在最后。这个顺序说白了就是“先拿确定的分，再啃难啃的骨头”，比赛时也是这个策略。

优先级排序完成之后，我给自己定了一个规矩：第一遍刷的时候可以看题解，第二遍必须合上题解自己写。只有独立写出来的代码才代表你真的掌握了。后面几大节要讲的内容，基本就是从这张分类表里踩出来的经验。

2. 模式匹配题：题目从不直说“请用KMP”

2.1 L2-008 最长对称子串：一题两解，模板只是入口

先聊个题外话。不少人在PTA上搜“模式匹配”，搜出来的其实是数据结构教材里那道KMP作业题。但如果把天梯赛L2整个翻一遍，你会发现它几乎没有一道题会正儿八经地让你“实现KMP”，可字符串模式匹配的思想又无处不在。最典型的就是L2-008“最长对称子串”。

这题的要求很简单：给一个字符串，求最长回文子串的长度。字符串长度我记得体感上在几千级别的量级，所以O(n^2)的中心扩展法可以过，Manacher就更稳。很多人的第一反应是动态规划，dp[i][j]表示s[i..j]是不是回文，转移方程也不难：s[i]==s[j]且dp[i+1][j-1]为真时dp[i][j]为真。但这么写有两个问题：一是二维数组开起来占内存，二是转移顺序容易搞错，不小心就会在边界上翻车。

我第二遍用的是中心扩展法，思路特别好理解：把每个位置当作回文中心，向左向右扩展，直到两边字符不同为止。注意回文中心有两种，一种是单个字符，比如“aba”的中心是b；另一种是两个相同字符中间，比如“abba”的中心是bb之间。所以每个位置要分奇偶两次扩展。代码骨架长这样：

#include <bits/stdc++.h> using namespace std; int main() { string s; getline(cin, s); int n = s.size(); int ans = 1; for (int i = 0; i < n; i++) { // 奇数长度回文，中心为 i int l = i, r = i; while (l >= 0 && r < n && s[l] == s[r]) { ans = max(ans, r - l + 1); l--; r++; } // 偶数长度回文，中心在 i 和 i+1 之间 l = i, r = i + 1; while (l >= 0 && r < n && s[l] == s[r]) { ans = max(ans, r - l + 1); l--; r++; } } cout << ans << endl; return 0; }

这套写法的好处是空间O(1)，逻辑简单不容易错。唯一要留意的是用getline读整行，因为测试数据里的字符串可能含有空格，如果你用cin去读，会在空格处断掉，直接WA到怀疑人生。我第一遍刷这题就栽在这里。

如果你追求更极致的性能，可以用Manacher算法，维护一个当前最右回文边界mx和对应的中心id，利用对称性质减少重复比较。核心就是那个经典的d数组：d[i]表示以i为中心的最长回文半径，初始化时利用i关于id的对称点j直接继承d[j]，但又不能超过mx-i这个右边界。为什么要这样限定？因为mx之外的字符尚未验证，盲盒不能乱开，投机取巧反而会算错。Manacher写起来比中心扩展多几行，但属于“背下来就能秒杀回文题”的套路，值得练熟。

回文串本质上也是一个匹配问题：它要求子串的左右两边互为镜像。你理解了“镜像匹配”这个模式之后，再看别的字符串题就会习惯性地想“能不能匹配、匹配的边界在哪里”，这种题感就是平时刷题刷出来的。

2.2 字符串哈希在L2题目中的实用场景

除了回文这类显式匹配，L2里还有不少题目需要快速判断两个字符串或两个子串是否相等，这时候字符串哈希比KMP更好用。它的原理说白了就是把一个字符串映射成一个整数：设进制base，从左到右计算hash[i] = hash[i-1] * base + s[i]。这样任意子串s[l..r]的哈希值都能通过前缀和O(1)算出来，然后比较两个子串的哈希值就能判断它们是否相等。

我自己的习惯是用unsigned long long存哈希值，让它自然溢出取模2^64，这样省去手写大数取模。base取131或13331这类经验值，基本不会冲突。也有人担心哈希碰撞，说实话在PTA的数据强度下，单哈希完全够用，绝大多数题目根本不会构造碰撞数据。如果你实在不放心，可以上双哈希，用pair<ull, ull>当键值。

举一个实际场景：最长回文子串那道题，也可以用“哈希+二分”来解。枚举每个位置作为回文中心，然后二分半径长度，用哈希O(1)判断左右两侧的子串是否互为镜像。复杂度是O(n log n)，比中心扩展稍微快一点，而且思路特别适合写题时现场推演。我已经不记得我这套写法在PTA上跑了几次重提交，但每次提起来都想说一句：哈希真的是字符串题的万金油。

还有一个非常典型的用例是L2-030“冰岛人”。这道题本身不是字符串匹配，但题面里人名是一长串的英文，你需要先判断两个人能不能查族谱、能不能确定性别，这时候就离不开“把人名映射成编号”这步操作。用unordered_map或map存人名到编号的映射，再用编号去做关系判断，本质上就是一边存数据、一边用哈希结构加速匹配的过程。这道题综合了哈希映射、分类讨论和并查集思想，属于L2里难度靠前的一道，能吃透它，字符串处理和逻辑拆分的基本功就算过关了。

从这两类场景能看出一个规律：模式匹配在L2里不是一道独立题，而是一种底层能力。它可能藏在回文串里，可能藏在人名关系里，也可能藏在病毒溯源的路径比较里。刷题的时候如果只盯着“模板题”刷，碰到包装过的题目就会反应不过来。

3. 四类高频题型的复盘笔记

3.1 链表题：用数组模拟，别被链表名字唬住

L2-002“链表去重”和L2-022“重排链表”这两道题，看名字以为是考链表，实际上在C++里根本不用new结点、不用指针，直接开数组模拟就完事了。第一次刷链表题的人容易被“链表”两个字吓到，但实际上PTA的链表题有一个共同特征：它会给你每个结点的地址和下一个结点的地址，这时候只要用两个数组存键值和next指针即可。

具体到链表去重，题目会给头结点地址、结点总数，然后每个结点格式是“地址 键值 下址”。做法分几步走：第一步从给定头结点开始，沿着next数组把链表遍历一遍，只保留真正属于链表的结点；第二步用一个vis数组标记键值的绝对值是否出现过；第三步遍历过程中，没出现过的放进“去重后的链表”，出现过的放进“被删除的链表”。最后分别输出两条链表，注意每个结点地址都要补足5位，用printf("%05d")最省事。

这里面有两个坑特别常见。第一个坑是，输入里可能混着一些根本不在链表上的孤立结点，它们不影响结果，但如果你傻乎乎地按“结点总数”去循环，最后输出的链表可能包含多余的结点。解决办法是遍历结束后单独统计有效结点个数，而不是直接用输入的n。第二个坑是，被删除的链表也可能有多个结点，它们的next需要重新串联，很多人只记得给主链表续上，忘了给删除链表也改next，导致输出乱成一团。

重排链表那道题思路也差不多：先把链表拉平成数组，再按“最左一个、最右一个、次左一个、次右一个……”的顺序重排。输出格式同样是地址补零。这两道题难度不高，但特别考细心，我第一遍刷的时候都因为小坑返工过。把数组模拟链表的套路练熟之后，碰到这类题基本就是默写。

3.2 并查集与连通性：从家庭房产到红色警报

并查集在L2里出现频率很高，而且经常不是裸考，而是藏在一些场景化描述里。L2-007“家庭房产”是一个经典例子：给你若干条家庭成员关系，要求统计每个家族的人数、房产套数和总面积。这题的核心操作很简单，就是并查集union两个有关联的人。关键问题在于，合并之后你还要维护每棵树代表的集合信息，比如人数、套数、面积。

我的做法是开一个结构体数组，每个结点存父节点、人数、房产套数、总面积。在合并时，如果两个人的根不同，就把其中一个根的父节点指向另一个根，并把人数、套数、面积累加过去。这里有个细节：按题面要求，输出时家族编号要取整个集合里编号最小的成员，所以可以在每次union时把编号较大的根指向编号较小的根，让根自然成为最小成员。这个技巧能让自己少写一个查找最小值的循环。

还有一道很能打的题是L2-013“红色警报”。它给一张城市图，然后按顺序攻占一些城市，每次攻占后要判断“全国是否分裂成了更多不连通区域”，如果是就发出红色警报。我在第一遍看这个题时第一反应是“删除城市后动态维护图连通性”，这种操作正常来说要用到一些高级的数据结构。但比赛时间有限，我复盘后更推荐一个朴实无华的思路：每次删除后重新对整个图做一次DFS或BFS，统计当前连通块数量，和删除前的数量比较一下，就知道要不要报警。

为什么敢暴力重算？因为题目的数据范围并不大，城市数和边数都在可接受的量级，就算删K次，每次全图扫描一次，总复杂度也就O(k*(n+m))，在PTA的时限下完全扛得住。很多选手总觉得“题目看起来复杂，一定有什么隐藏高深解法”，于是开始想复杂了，其实暴力重算就是这道题最稳的解。关键点是判断条件：如果删除后连通块数量比删除前多，说明这个城市原本是连接若干区域的枢纽，它的丢失确实造成了分裂；如果连通块数量不变，那这个城市本来就是个孤点或边缘节点，不触发警报。还有个细节要注意，所有城市都消失之后还要额外输出一行Game Over，少写这行会丢掉最后一个测试点。

并查集的另一种相反思路是离线倒序：因为并查集只支持加边不支持删边，那就把“删除”倒过来看成“加入”，从最终状态开始反向加回被删的城市。这个思路在理论题里很有意思，不过在天梯赛这种时间紧的场合，我反而推荐DFS重算，理由很简单：写起来快、不容易错、调试直观。比赛不是炫技场，稳定拿分才是目的。

3.3 二叉树遍历：递归区间划分必须一次写对

树的题目里，L2-006“树的遍历”是绕不开的基础题。题目给出后序遍历和中序遍历，要求输出层序遍历结果。道理大家都懂：后序遍历的最后一个元素一定是当前子树的根；然后去中序遍历里找到这个根的位置，它左边是左子树的中序序列，右边是右子树的中序序列；根据左子树的长度，可以回头把后序遍历也切成左右两段，递归处理。

难点就在于切区间的下标记不准。我见过很多同学上课听懂了原理，自己一写就区间越界。这里送大家一个我自己常用的写法：递归函数build(int inL, int inR, int postL, int postR)表示当前处理中序的[inL, inR]和后序的[postL, postR]，中序根的位置是pos，那么左子树长度为len = pos - inL，左子树的中序区间是[inL, pos-1]，右子树中序区间是[pos+1, inR]；后序区间怎么切呢？左子树后序是[postL, postL+len-1]，右子树后序是[postL+len, postR-1]。这样把四个区间全部定死，递归就清晰多了。

建树完成后，层序遍历用queue实现，先根入队，每次弹出一个结点的同时把它的左右孩子入队，顺序输出就是层序。这里提醒一句，不要用递归写层序，层序天然就是迭代过程，硬写成递归只会给自己添乱。输出格式上题目通常要求末尾没有多余空格，我习惯先输出第一个结点的值，之后每输出一个前面补一个空格，这种“标志位控制”的办法屡试不爽。

同样套路的还有L2-011“玩转二叉树”，它给的是前序和中序，要求输出镜面反转后的层序。镜面反转说白了就是把每个结点的左右子树交换，代码上只需要在建树过程中把“先递归左再递归右”改成“先递归右再递归左”，或者建完树之后层序遍历时先右后左，效果一样。这两道题能熟练写出来后，二叉树的递归划分基本就不会慌了。

3.4 栈模拟题：判定顺序决定成败

L2-032“彩虹瓶”我愿称之为L2模拟题里最容易写错的一道。题目背景是：有一堆按1到N编号的球，生产顺序是给定的一个序列，需要用栈把球按1、2、3……的顺序装进彩虹瓶，栈有容量上限M。过程抽象出来就是：

维护一个变量need表示当前期望放入瓶子的编号。遍历生产序列，如果当前生产的球编号正好等于need，就直接放入瓶子，need++，随后还要不断检查栈顶是不是新的need，如果是就继续弹出。如果当前生产的球不是need，那就只能往栈里压，压栈之前要检查栈是否已经满了，如果满了就说明没办法处理，整组失败。遍历结束后，如果栈里还有球或者need没走到N+1，也说明失败。

我第一遍写这题时犯的错误是：没有在“压栈前检查满”这个时机上控制好，导致该判NO的时候漏判。另外还要注意，就算某个球被压入了栈，后续每一步生产后都要立刻尝试从栈顶弹出需要的球，这个“生产后清栈”的动作不能省。打个比方，栈就像一个缓冲区，生产线每吐出一个球，你都要先看看能不能直接出货，不能出货才考虑临时存起来。这个判定顺序理清了，代码其实不到四十行能写完。

L2-033“简单计算器”也是栈模拟，但它的坑在操作数顺序上。题面会给N个数字和N-1个运算符，数字和运算符分别压入两个栈，每次从数字栈取两个数、符号栈取一个运算符，算完再把结果压回数字栈。因为栈是后进先出，先弹出的那个数其实是后入栈的，在运算符左侧还是右侧是个大坑。我回忆自己的代码，每次是先后弹出两个数a和b，然后算b op a，而不是a op b。为什么？因为当初入栈时先入栈的数字才是左操作数，而后入栈的是右操作数，弹出顺序正好相反。要是不信，拿“1 2 3”和两个运算符自己手推一遍就明白了。

另外这道题的除法要额外小心，一旦发现除数为0，要按题目要求输出错误的表达式并结束，不能再继续算。而且题目里的除法是整数除法还是带余除法，要以题面为准，PTA的题面一般说得很清楚，不要自己想当然。栈模拟题写得多之后，你会发现它们都是在考“状态的先后顺序”，顺序对，代码就稳。

4. 踩坑实录与问题排查速查表

4.1 输入输出与STL的常见翻车点

温故L2这一遍下来，我把翻车最多的问题整理成了一组速查，每次现场比赛前都扫一眼：

第一，cin和scanf混用。天梯赛数据量不大，cin不至于太慢，但只要你用了cin，最好在main开头加上ios::sync_with_stdio(false)和cin.tie(nullptr)，这句话能避免很多无意义的IO损耗。如果不加，碰到字符串密集的题可能平白无故被卡常。

第二，getline和cin混用。最常见的是先cin读一个整数，再用getline读字符串，结果getline把之前行尾的换行符读走了，字符串变成空的。解决办法是在cin读完之后调用一次getline把残留换行吃掉，或者用cin.ignore()。这个问题我在最长对称子串那道题上踩过一次之后，现在就条件反射了。

第三，格式化输出补零。地址类题目动不动就要求“%05d”，用cout则要配合setfill('0')和setw(5)。我习惯直接printf，原因很简单：补零格式串写起来比cout那套简洁得多，而且不容易忘记恢复填充字符。

第四，STL容器选择。unordered_map在PTA的题面上不一定被卡哈希，但为了稳妥起见，凡是能map解决的我就用map，毕竟map的log复杂度在这种数据量下完全够快。只有明确需要极高性能的时候才考虑手写哈希表。

4.2 边界条件自查清单

边界条件是L2最容易翻车的角落，我把自己踩过以及别人常翻车的几个坑列在这里：

这些不是空话，每一个我都付出过罚时的代价。比如回文串那道题，如果整个字符串就一个字符，中心扩展法初始答案如果是0，最后就会输出0，直接扣分。这种低级错误最伤人，因为算法完全正确，败在一个初始值上。

4.3 为什么你的代码会“超时”而不是“错误”

超时和错误是两回事，错误说明你的逻辑有bug，超时说明你的代码在数据面前跑得不够快。我在温故过程中发现，不少“超时”其实是算法复杂度的问题，而不是常数问题。举几个典型的：

第一个是字符串处理时不停用substr或string拼接。substr每次要拷贝新字符串，循环里这么干时间复杂度轻松变成O(n^2)，数据一大就卡死。正确做法是只记录下标区间，需要用的时候再取值。

第二个是图类题目里每个城市被删除后都重新跑一次全图DFS。前面说的红色警报为什么可以这么干？因为你算过总复杂度，确认在时限内。如果没算过就开始暴力，数据范围一大就超时。所以暴力不是不行，是要“先算账再动手”。

第三个是用了不必要的高复杂度容器。比如明明可以数组存状态，偏要用map，明明可以普通队列，偏要用priority_queue。在简单场景里杀鸡用牛刀，可能不至于超时，但会给你带来额外的调试负担。

我排查超时题目的步骤一般是：先看数据范围，估算自己代码的复杂度是否在最坏情况下可接受；如果算法没问题，再看是不是STL操作频繁导致常数过大；最后看有没有多余的临时拷贝或重复计算。按这个顺序排查，基本能在几分钟内定位问题。比赛的时候时间就是分数，别在超时问题上钻牛角尖，换个更直接的做法有时反而更快。

5. 一点自己的复习心法

这轮温故让我比较有体感的一件事是：刷题数量真的不是关键，关键是你对每类题的“坑位”熟不熟。我第一次刷L2的时候，很多题是看题解之后照着重写，当时觉得自己会了，一个月后再做几乎忘光。第二轮我改成手写笔记，每题只记三行——核心思路、判定顺序、坑位在哪。效果比刷三遍还显著。

另外我也体会到，模式匹配这类字符串题很容易让人陷入模板崇拜，觉得背了KMP就天下无敌。实际上天梯赛L2更考验的是“在场景里认出模式”的能力，模板只是最后一步的工具。把回文串、哈希、映射这些手段用熟，远比背死一个算法更能应对题目变化。

如果离比赛只剩两周，我会建议大家只做三件事：把L2的分类题单过一遍，把链表和树的几个模板默写一遍，把输入输出和边界条件这些坑点记一遍。这三件事做完，L2的分数基本就稳了。我自己踩过不少弯路，写这篇笔记也算是个总结，希望能给正在刷题集的人省下一点试错的时间。