3月4日晚上十点半我关掉PTA的练习页面把今晚的L2题目记录复制进错题本文档长长舒了口气。这已经是队伍连续第四个周一晚做天梯赛L2专项练习了——不练L1不碰L3就硬啃中间这一层。原因很简单天梯赛的排位很大程度上是L2稳不稳决定的。L1是送分题大家都会L3太难多数队伍只能拼一两题真正决定团队排名的是L2能不能又快又准地拿下。今晚我选了四道有代表性的L2题从树的遍历、链表反转到并查集全部AC但过程一言难尽中途两次差点把键盘砸了。1. 3月4日这晚我为什么只盯着L2刷1.1 天梯赛L2题在整场比赛中的真实地位很多人第一次参加天梯赛容易被题目数量唬住L1那么多道L3看起来分值更诱人。但打过几次正式比赛之后就会发现团队排名表上真正拉开的差距几乎全部来自L2。原因其实很直白。L1的题面通常就是“读入-处理-输出”三步走考的是语法熟练度和手速训练过三五场的队伍基本都能拿到九成以上的分。L3则完全是另一个世界每道题都带一定算法深度放眼整个区域赛能把L3全部做出来的队伍凤毛麟角绝大多数队伍的策略是“能骗一点分是一点”。中间的L2就变成了兵家必争之地它有一定思维量但不像L3那样劝退给足时间认真分析大部分人是能做出来的。从分值构成看L2每题的分数在L1的三倍上下一题L2顶好几道L1。如果一支队伍L2全面崩盘哪怕L1满分总排名也会被甩出很远。所以我在3月4日这晚给自己定的目标是不管做几题做完必须能把“为什么卡住”讲清楚而不是随便AC就翻页。1.2 这几次练习暴露的第一道坎L1惯性思维连续四期专项练习下来我发现队伍里不少同学包括我自己前几周最大的问题不是不会做L2而是带着L1的惯性去读L2题。什么叫L1惯性就是拿到题先写输入输出框架然后照着题面字面意思模拟模拟到一半发现特殊情况处理不了代码已经长得没法看了。L1大多数题没有隐藏的边界条件但L2几乎每道都在输入格式或边界上埋了雷。比如链表类题目里“给出的节点未必都在链表上”这种经典坑L1绝对不会这样考L2就非常喜欢。所以3月4日的练习我有意识地强迫自己做一件事先花三到五分钟把题面读完用笔在草稿纸上写出“输入是什么、输出是什么、哪一步容易出错”然后才动手写代码。这个习惯看着笨但确实治好了我前两周“交一版错一版”的毛病。2. 当晚练习清单四道L2题的时间与失分分布下面是我3月4日晚上的实际练习记录题目类型正好覆盖了L2的高频考点树的遍历、链表反转、并查集和一道模拟题。题目类型主要考点开始时间AC耗时中途提交卡住的地方树的遍历中序后序还原二叉树并输出层序19:1031分钟2次递归区间的偏移量算错链表反转按K个一组反转链表处理无效节点20:0046分钟4次没过滤“不在链表上”的节点并查集社交网络集群合并爱好相同的人21:0024分钟1次合并时没统一根节点关系模拟题按规则处理字符串队列21:4038分钟3次输出格式和空串边界先把结论放在前面四道题全部AC但有将近一半的时间花在了“按错误理解写代码再推翻重来”上。这不是个高效率的状态不过拿来复盘反而最有价值——真正能让自己进步的不是AC的那一瞬间而是中间那次提交报错时你停下来看懂了多少东西。2.1 时间分布透露出的问题看这张表能发现我的AC耗时和题目的真实难度并不完全匹配。并查集那道题理论上比链表反转简单但链表题我绕了46分钟模拟题也用了38分钟。这个差距反映出的不是算法不会而是对“考试式题面”的适应问题。链表反转这道题我相信大部分人在学习数据结构时都手写过但PTA的考法非常“现实”它用一串五位数地址来模拟内存中的链表节点而不是给你一个现成的结构体数组。很多人包括我都下意识按“课本链表题”去处理结果忽略了输出时地址的补零、-1的单独处理、以及“并非所有输入节点都在最终链表上”这三个隐藏条件。这种题说难不难但如果不熟悉PTA的出题语言就会反复踩坑。3. 三道题复盘从读题到掉坑再到修正的完整过程3.1 树的遍历中序后序还原层序坑在区间边界这道题是一个很经典的组合给出二叉树的中序遍历和后序遍历要求输出层序遍历结果。思路大家应该都清楚——后序序列的最后一个元素是根拿着根去中序序列里定位左右子树的范围然后递归处理。但真写起来区间边界真是让人头大。我第一次提交报错问题出在右子树的后续区间上。中序序列是简单的[L, pos-1]和[pos1, R]但后序序列的划分没这么直接。因为后序里左子树和右子树是连在一起的需要根据左子树的节点数量leftLen来切int leftLen pos - inL; // 左子树的后序区间[postL, postL leftLen - 1] // 右子树的后序区间[postL leftLen, postR - 1]我第一版写成了[postL 1, postL leftLen]虽然看着对称但右边界多了一个位置导致个别节点挂错了父亲层序输出错乱。这类问题我建议不要硬记公式每次递归都在草稿纸上画一棵三层的树用具体例子把区间下标走一遍比背模板可靠得多。层序输出用的是队列BFS建树时我用数组存左右孩子。PTA的节点编号不一定是1到n连续所以数组开大一点或者用map存节点信息免得越界。3.2 链表反转哨兵节点与“节点不在链表上”的陷阱这道题让我栽了最多跟头。题面给出一串节点每个节点有地址、数据、下一个地址要求从链表头部开始每K个节点反转一次不足K个的不反转。第一眼看到这题我的反应是“链表反转嘛三指针搞定”但接二连三的WA让我冷静下来认真读题。问题出在我完全忽略了一个关键信息输入给的所有节点中有一部分可能是孤立节点或者属于其他链表的节点它们根本不在我们这次要处理的链表上。如果直接拿输入节点总数 / K来计算反转轮数会把那些游离节点也算进去结果链表尾部一堆不该输出的东西。正确做法是先遍历一遍只统计从给定头节点开始能走到的有效节点数量int cnt 0; for (int p head; p ! -1; p node[p].next) cnt; int round cnt / K;然后才是反转。反转时我用了一个哨兵头节点把上一段的尾部和当前段的头部接起来避免每次单独处理边界。哨兵节点这东西平时写题可能觉得多余但连续反转多段链表时它能让代码简洁非常多。还有一个细节地址统一按五位数输出用printf(%05d, addr)但-1要单独处理。我第二次提交失败就是因为最后一位输出成了-0001这种格式坑在PTA的链表类题目里出现频率极高刷几道就能形成肌肉记忆。3.3 并查集部落合并顺序决定生死不夸张地说并查集这题是我整晚唯一感到“舒适”的题。题目大意是给出一群人每个人有若干爱好有共同爱好的人自动属于同一个部落最后统计部落数和最大的部落人数。这题在L2里出现频率很高考法也很标准以每个爱好第一次出现的人作为代表后续有相同爱好的人并到一起。我第一版提交错在了一件很蠢的事情上合并时只对hobbyId - personId方向做了join忘了之后要统一查根。比如A和B拥有共同爱好x我把B并到了A的集合但B原本所在的集合里还有其他成员这些人并没有跟着更新父节点。不查根直接统计就会把一个部落拆成两个。正确写法是每次合并都走find拿到真正的根节点再做 union统计的时候也只认find(i)的结果for (int i 1; i n; i) { int root find(i); cnt[root]; maxSize max(maxSize, cnt[root]); }顺带记录一个经验有些同学喜欢在join函数里偷懒直接把某个parent[ ]赋值过去不去查两个根。这个坏习惯在数据量小的时候看不出问题一旦测试数据变多要么TLE要么集合关系整个错乱。并查集的代码就那十行值得背得滚瓜烂熟。4. 练习后总结的五个赛场生存技巧4.1 先做格式分析再动键盘L2的很多题目题面描述都非常“正式”会明确写清楚“输入保证……”“如果……则……”之类的条件。这些句子不是废话全是出题人划的重点。我养成了一个习惯读题时拿笔把“保证”“如果”“否则”圈出来对应到代码注释里写一行检查。比如链表那题题面很可能写了“给出的节点不一定在链表上”我如果早点在草稿纸上写下这个条件至少能省二十分钟。4.2 能用 STL 就别手写L2的常用包里vector、map、queue、reverse这些都是能救命的东西。链表反转那题反转单段链表的逻辑完全可以手写三指针但按K段反转且要拼接的时候直接对每段的vector做reverse再重新链接代码短且不容易错。有人说用STL会超时——L2大部分题目的数据规模并没有那么大真正卡常数的题目主要在L3。练习阶段优先保证思路清晰遇到过不了的再针对性地优化顺序不要反。4.3 边界条件测试用例要自己造每次AC之前我都要求自己至少手动构造三组测试样例最小输入n1或K1、恰好整除的边界、以及最坏情况。以链表题为例K等于1时不应该有任何反转K大于链表长度时保持原序输出。这些边界不看题面也能猜出七八成猜到并测过WA概率直接砍半。4.4 不要迷信单一解法多准备一个暴力对拍天梯赛L2有些题容易让人钻牛角尖明明暴力能过却非要写一个高超的优化算法结果优化算法写错了。我在练习时定的规矩是如果五分钟内没想出正解先写一个能保证结论正确的暴力版本再拿小数据对拍。对拍代码本身不用提交但它能极大压缩“自以为正确”的盲区。4.5 赛后错题比AC题更值得记这可能是老生常谈但我自己真的是因为坚持做错题记录才把分数提起来的。每道卡住的题我会记三行卡在哪个知识点、当时的错误代码写法、正确的处理方式。一周后重新做一遍如果还不会说明这个知识点是真的薄弱。3月4日的复盘文档里链表反转那题被我标了五颗星下周要再刷两道同类型题巩固。5. 接下来一周的训练安排与刷题路线5.1 周中专题把L2的五个高频考点拆开打天梯赛L2虽然题目变化多但考点真的相对集中树的遍历、链表操作、并查集、最短路径、字符串与模拟。这五个方向覆盖了L2的大部分题目。我给自己排的周中安排是每天一个专题只刷该考点的两三道题以保证熟练度而不是追求数量。比如周一是树就在PTA题库里把树的遍历、完全二叉树、二叉搜索树相关题目连刷一遍周二是并查集把社交集群这类变体集中做些。专题训练的意义在于你会重复遇到同样的模板和同样的坑身体会形成记忆。5.2 周末全真模拟限定三小时只按正式赛的流程走天梯赛不是单题决胜负是三小时连续作战。很多人平时单题能AC一合起来就崩盘多半是精力分配出了问题。3月4日晚上我做了一个很小的测试连续做两小时不碰手机、不查资料结果后半段明显效率下降。所以周末我计划做一次完整的三小时模拟L1快速扫完L2每道最多给四十五分钟超时先跳过标记最后再回头查缺补漏。这个时间盒策略在正式比赛里非常管用。5.3 关于刷题量的一句实话3月4日的四道题加上复盘文档我花了整整一个晚上。从产出看可能只“刷”了四题但我觉得比之前一晚上做十道L1题要有效得多。L2的复习重点从来不是见过多少题而是每一道题里有没有把自己真实的想法逼出来。如果你也在备战天梯赛我建议宁可少做两道也要把每一道卡住的题从头到尾搞明白这个习惯拉长到一个月效果绝对肉眼可见。最后再补一句我个人的体会天梯赛L2的设计很像职场里那种“不难但琐碎”的项目真正拉开差距的往往不是思维爆点而是对细节的敬畏程度——地址补零、递归边界、输入里那些不起眼的限定词哪一个漏掉了都前功尽弃。3月4日之后我开始刻意训练自己“读完题先在草稿纸上写下三个最容易翻车的点”这个办法笨但真能让你在赛场上少输很多不该输的分。