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题按考察点分了类。下面这个表是我自己整理出来的大方向不同年份题目编号会变但考察点基本就这几类类别代表题型核心工具模拟彩虹瓶、简单计算器、包装机栈、队列、状态机思维链表链表去重、重排链表数组模拟链表、格式化输出图论红色警报、部落、紧急救援并查集、DFS/BFS、最短路树树的遍历、玩转二叉树、小字辈递归建树、层次遍历字符串最长对称子串、冰岛人中心扩展、Manacher、哈希排序贪心月饼、抢红包、人以群分结构体排序、贪心证明我建议的复习顺序是模拟题优先因为最好拿分且容易建立信心然后是链表和树这两类题套路固定只要模板熟练基本能稳过接着是并查集和连通性题目难点在于“怎么把题面翻译成并查集操作”字符串和较复杂的综合题放在最后。这个顺序说白了就是“先拿确定的分再啃难啃的骨头”比赛时也是这个策略。优先级排序完成之后我给自己定了一个规矩第一遍刷的时候可以看题解第二遍必须合上题解自己写。只有独立写出来的代码才代表你真的掌握了。后面几大节要讲的内容基本就是从这张分类表里踩出来的经验。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[i1][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 和 i1 之间 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的数据强度下单哈希完全够用绝大多数题目根本不会构造碰撞数据。如果你实在不放心可以上双哈希用pairull, 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*(nm))在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]右子树中序区间是[pos1, inR]后序区间怎么切呢左子树后序是[postL, postLlen-1]右子树后序是[postLlen, postR-1]。这样把四个区间全部定死递归就清晰多了。建树完成后层序遍历用queue实现先根入队每次弹出一个结点的同时把它的左右孩子入队顺序输出就是层序。这里提醒一句不要用递归写层序层序天然就是迭代过程硬写成递归只会给自己添乱。输出格式上题目通常要求末尾没有多余空格我习惯先输出第一个结点的值之后每输出一个前面补一个空格这种“标志位控制”的办法屡试不爽。同样套路的还有L2-011“玩转二叉树”它给的是前序和中序要求输出镜面反转后的层序。镜面反转说白了就是把每个结点的左右子树交换代码上只需要在建树过程中把“先递归左再递归右”改成“先递归右再递归左”或者建完树之后层序遍历时先右后左效果一样。这两道题能熟练写出来后二叉树的递归划分基本就不会慌了。3.4 栈模拟题判定顺序决定成败L2-032“彩虹瓶”我愿称之为L2模拟题里最容易写错的一道。题目背景是有一堆按1到N编号的球生产顺序是给定的一个序列需要用栈把球按1、2、3……的顺序装进彩虹瓶栈有容量上限M。过程抽象出来就是维护一个变量need表示当前期望放入瓶子的编号。遍历生产序列如果当前生产的球编号正好等于need就直接放入瓶子need随后还要不断检查栈顶是不是新的need如果是就继续弹出。如果当前生产的球不是need那就只能往栈里压压栈之前要检查栈是否已经满了如果满了就说明没办法处理整组失败。遍历结束后如果栈里还有球或者need没走到N1也说明失败。我第一遍写这题时犯的错误是没有在“压栈前检查满”这个时机上控制好导致该判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最容易翻车的角落我把自己踩过以及别人常翻车的几个坑列在这里场景容易漏的点检查办法回文串长度为1的字符串初始答案设为1而不是0链表操作输入含有无效孤立结点遍历完后单独统计有效个数并查集只有一个连通块删城市前后数量不变不报警栈模拟栈满但当前球恰好匹配先匹配后判满别反过来树遍历中序中找不到根题目保证存在但仍要小心区间端点除法计算除数为0在运算前判断并停止这些不是空话每一个我都付出过罚时的代价。比如回文串那道题如果整个字符串就一个字符中心扩展法初始答案如果是0最后就会输出0直接扣分。这种低级错误最伤人因为算法完全正确败在一个初始值上。4.3 为什么你的代码会“超时”而不是“错误”超时和错误是两回事错误说明你的逻辑有bug超时说明你的代码在数据面前跑得不够快。我在温故过程中发现不少“超时”其实是算法复杂度的问题而不是常数问题。举几个典型的第一个是字符串处理时不停用substr或string拼接。substr每次要拷贝新字符串循环里这么干时间复杂度轻松变成O(n^2)数据一大就卡死。正确做法是只记录下标区间需要用的时候再取值。第二个是图类题目里每个城市被删除后都重新跑一次全图DFS。前面说的红色警报为什么可以这么干因为你算过总复杂度确认在时限内。如果没算过就开始暴力数据范围一大就超时。所以暴力不是不行是要“先算账再动手”。第三个是用了不必要的高复杂度容器。比如明明可以数组存状态偏要用map明明可以普通队列偏要用priority_queue。在简单场景里杀鸡用牛刀可能不至于超时但会给你带来额外的调试负担。我排查超时题目的步骤一般是先看数据范围估算自己代码的复杂度是否在最坏情况下可接受如果算法没问题再看是不是STL操作频繁导致常数过大最后看有没有多余的临时拷贝或重复计算。按这个顺序排查基本能在几分钟内定位问题。比赛的时候时间就是分数别在超时问题上钻牛角尖换个更直接的做法有时反而更快。5. 一点自己的复习心法这轮温故让我比较有体感的一件事是刷题数量真的不是关键关键是你对每类题的“坑位”熟不熟。我第一次刷L2的时候很多题是看题解之后照着重写当时觉得自己会了一个月后再做几乎忘光。第二轮我改成手写笔记每题只记三行——核心思路、判定顺序、坑位在哪。效果比刷三遍还显著。另外我也体会到模式匹配这类字符串题很容易让人陷入模板崇拜觉得背了KMP就天下无敌。实际上天梯赛L2更考验的是“在场景里认出模式”的能力模板只是最后一步的工具。把回文串、哈希、映射这些手段用熟远比背死一个算法更能应对题目变化。如果离比赛只剩两周我会建议大家只做三件事把L2的分类题单过一遍把链表和树的几个模板默写一遍把输入输出和边界条件这些坑点记一遍。这三件事做完L2的分数基本就稳了。我自己踩过不少弯路写这篇笔记也算是个总结希望能给正在刷题集的人省下一点试错的时间。