2020年那届团体程序设计天梯赛我是真没想到自己最后会坐在电脑前以线上方式打完全程。更没想到的是比赛结束后对照榜单复盘我发现自己丢的分里有将近三分之一不是不会做而是会做但踩了坑。这篇文章就是围绕那场比赛的完整复盘每一类题的核心思路是什么哪些地方特别容易想当然以及我们在赛后整理出来的易错点清单。无论你是打算第一次参赛的选手、还在带队的学长学姐还是想找点算法题练手的同学这份复盘应该都能帮你少走一些弯路。我把题目按实际难度和花费时间重新梳理了一遍写的时候不会只丢一句这题用XX算法就能过而是把为什么我会先想到错的方向卡了多久最后怎么绕出来都讲清楚。毕竟题解的价值不在答案本身而在那个从WA到AC的思考过程。1. 赛制、分值分布与开赛前我最后悔没做的事1.1 这届比赛的节奏三档难度不是各做各的团体程序设计天梯赛的题面分三档基础题、进阶题、压轴题。很多人第一次打的时候会下意识把三档题目当三条平行线基础题是热身进阶题是主力压轴题是给大佬准备的。实际上这届比赛打下来我最大的感受是——三档之间是互相渗透的基础题里埋着进阶题的思考量压轴题的某些子问题其实就是基础题的变形。举个例子开头几道基础题里有一道是按规则处理一个队列看起来只是模拟但如果把数据量放大到极限普通链表操作会超时必须用环形队列或者双端队列来优化。也就是说比赛刻意把会做和能拿分分开思路谁都能想到但只有注意到数据范围的人才能拿满分。这一档题的分值看似不高却是整场比赛的胜负手因为基础题不允许丢分。1.2 队伍分工与拿分优先策略我们队赛前定的策略很简单前四十分钟十个人全部扑在基础题上一个人负责扫读全部题面并标记哪几题表面上难、实际有巧劲另外九个人按熟悉度分区块拿分。这个策略来自之前几次模拟赛的教训——总有队友看到压轴题描述很炫忍不住一头扎进去结果半小时后颗粒无收基础题还被别人抢了先。实际比赛的时候这个策略起到了很大的作用。基础题里有几道题是典型的读题陷阱比如要求输出保留几位小数、要求补上前导零、要求按字典序而非输入顺序输出。如果不是专门有一个人提前把这类要求圈出来我们至少会多交几次罚时。队伍十个人不是各写各的而是先花五分钟对齐题面里的坑再分散动手。这一点我觉得比任何算法知识都重要。1.3 环境、提交时限和心态准备说一个赛前最容易被忽略的准备工作编译器版本和提交反馈。天梯赛的评测环境是统一的但本地环境不一样有的队友用新版编译器有的用旧版结果代码在本地能过、提交后编译错误。我们因为这个问题白送了一次罚时。更坑的是某些题目的评测机对栈空间有限制递归写深了直接爆栈而不是给你超时提示。心态上我最后悔的是没有提前模拟长时间连续思考的节奏。三个小时的比赛不是三个小时连续高强度思考而是九十分钟全神贯注加九十分钟咬牙坚持。后半程的题目往往不难但脑子已经转不动了这时候比拼的是前期有没有留下缓冲时间。后来复盘我们队的提交记录后期通过的题占比明显偏低不是不会是累了。2. 基础题里藏得最深的几个坑模拟、字符串与边界条件2.1 模拟题的排队逻辑——插队和离队到底该怎么建模这届比赛的开场题里有一道模拟题我印象特别深。题面大意是这样的一群人排队中途会有人插到某个位置也会有人因为等不及直接离开最后要求输出队伍里的编号序列。数据范围不大但操作次数很多如果你真按每插入一次就移动后面所有人去写最坏情况下会变成O(n^2)提交上去直接超时。这里的易错点第一层是你会不会意识到需要链表。第二层更隐蔽——有些同学用数组模拟链表但忘了维护尾指针导致输出的时候要从头遍历一遍复杂度没问题却因为在插入时没处理边界情况而WA。我当时写的就是数组模拟双向链表结果在插到队尾这个分支上写错了指针更新顺序整整卡了二十分钟。后来和队友讨论才发现这类题目最好的建模方式是数组模拟的双向链表 哨兵节点。哨兵节点不仅能简化空表和插到队首队尾的判断还能让输出循环的判断条件变得统一。我后来把这种加哨兵的思路套用到其他好几道题上屡试不爽。通过这一题我想说的核心是模拟题不是靠蛮力靠的是用数据结构把规则翻译得更简单。2.2 字符串处理读整行、拆分、空串的连环坑字符串题是每届天梯赛基础题的常客2020年也不例外。有一道题要求解析一行输入里的若干字段按特定分隔符拆分后再做处理。乍看很简单但坑全在输入处理上如果直接用某些语言里的按空格切分函数遇到连续的多个空格切出来的数组里可能有空字符串然后你就莫名其妙多了一个字段。这类题还有一个经典易错点行末可能有换行符且换行符之前可能有回车符残留。很多选手在本地测试时没注意因为编辑器自动处理了但提交后第一个测试点就WA。我当时的做法是先读一整行手动去掉末尾的不可见字符再按分隔符拆分最后过滤空串。这段代码看起来多写了三四行却能把输入相关的坑一次排干净。另外一个容易忽略的是输出格式。字符串题里经常要求每个结果占一行或者行末无多余空格如果题目要求每组输出之间有空行而最后一组之后不能有多余空行这个边界能让人WA到怀疑人生。我的经验是在处理输出前先想清楚最后一个元素和最后一次循环的判定条件而不是在循环体里临时补救。2.3 一段真实排查记录从TLE到AC的环形优化我清楚记得有一道题题目本身不难给定一个数组反复做某种区间操作求最终的某几个值。我第一版用最直接的循环模拟本地跑了几个小案例全过提交后第2个测试点TLE。这时候我才回头看数据范围发现最坏情况下的操作次数是百万级别而每次操作又要遍历整个数组肯定不行。排查过程是这样的先把循环里的所有操作打上时间戳用一个十万级的数据跑本地测速发现单次操作大概需要几十毫秒乘上操作次数总时间轻松超过评测时限。接着我试着把每次遍历改为预处理前缀信息让单次操作变成O(1)查询重新提交后从TLE变成了AC。这道题的教训有两条第一看到题目先看数据范围再动手这是老生常谈但永远有人忘第二本地测速不能只跑小样例要按极限数据生成一组测试才能暴露复杂度问题。说到前缀信息我顺便补充一种很常用的思路如果操作是对某个区间整体做加减或求最值优先考虑差分数组和前缀和而不是线段树。区间问题在基础题和进阶题的边界上经常出现差分数组写起来简单、排错容易、常数小是完全够用的。3. 进阶题的贪心与数据结构思路对了一半离AC还差一口气3.1 贪心题为什么不能只靠直觉排序进阶题里头几天大家讨论最多的是一道贪心题。题目大意是有若干任务每个任务有开始时间和结束时间选择尽可能多的任务并且要给选出来的任务排一个执行顺序要求不能冲突。这题百分之八九十的人第一反应是按结束时间排序这个思路本身是对的经典的区间调度问题确实是这么解的。但易错点在于题目额外加了一个条件——任务之间可能还有依赖关系或者某些任务的执行时长不是由开始和结束时间决定的而是一个固定耗时。加了条件之后按结束时间排序就不再是最优策略了。我在赛场上想着这题我见过五分钟后写完提交WA在最开始的两个例子上那一刻我才意识到题面里那个额外条件不是摆设。这类题的正确打开方式应该是先忽略额外条件用经典贪心验证一遍然后构造一个能让经典贪心失效的反例看看额外条件到底改变了什么决策依据。如果经典贪心会选A而最优解选B那就是额外的判断维度没有纳入排序关键字。我们队后来总结的规律是贪心题永远不要急着写排序先想清楚每一步决策到底在比较什么。3.2 并查集与优先队列怎么一眼识别该用哪把工具进阶题里还有一类是数据结构题最常出现的两把工具就是并查集和优先队列。并查集的识别点很明确题面里出现连通分组合并判断两个元素是否属于同一集合这类字眼八成就是并查集。但有个坑是并查集题常和离线处理结合起来比如先给出一堆合并操作再在某个时间点查询状态如果没注意到离线而硬做在线更新就会把自己绕晕。优先队列的识别点则是另一个方向题面里出现每次取最大每次取最小前K个最值动态变化基本就是在暗示堆。我自己的经验是优先队列题最难的不是用堆这个结论而是堆里存什么。有些题存的是数值本身有些题存的是索引数值还有些题要存负值才能模拟取最大。想清楚堆元素的含义代码反而简单。针对2020年那届的题目分布我要提醒一点进阶题经常把两个数据结构缝合在一起。比如题目会先让你用并查集维护若干集合然后把每个集合的最值扔进优先队列最后再取全体最值。如果你的思维只停留在一题一数据结构这种缝合题就会让你发懵。本质上它们是在考你工具的组合能力而不是考单工具的熟练度。3.3 完整WA-AC排查链路一个反例引发的推倒重来我详细复盘一道我们队卡得最久的进阶题。题面需要维护一组集合支持合并以及查询当前所有集合中某个指标的最大值。我先按直觉写了两层循环的版本样例通过提交后WA在第8个测试点。由于看不到具体输入我决定自己构造一批能触发问题边界的用例。构造思路是这样第一组测试只做合并不查询检查合并逻辑第二组测试每次合并后都查询检查查询时机第三组测试人为制造空集合检查空集合是否被错误统计进了最值。三次测试下来问题立刻暴露——我在合并时没有判断两个元素是否已经在同一个集合里导致集合大小被重复累加最终最值算错。排查手段上我最推荐的是内存打点法在关键变量变化的地方打印当前值跑一遍小数据手算一遍期望值然后把两者对着看。这个方法很简单但比debugger还常用。另一个意见是如果WA在比较靠后的测试点多半是某个边界条件触发而不是整体思路错。这时候不要重写代码先用极值参数构造测试绝大多数情况下能找到原因。4. 压轴题怎么开局DP状态设计和图论建图的取舍4.1 先写暴力再谈优化DP题的递推方向压轴题部分最典型的一道动态规划题我记得题面是某种路径计数方案要求路径上不能经过某些格子还要对结果取模。很多选手一看路径计数就直接开DP这没问题但容易在状态定义上犯错。有人用二维数组表示从起点到(i,j)的方案数却漏掉了不能经过某些格子对当前格子的影响。我自己的做法是先写一版最暴力的DFS把暴力结果打印出来再手推几个小用例验证暴力是否正确。暴力对了之后再看暴力递归里的重复子问题在哪里把从(i,j)出发到终点的方案数提取成状态天然得到记忆化搜索。记忆化搜索写顺了再决定要不要转成递推。这个方法比一上来就硬推递推公式要稳妥得多因为递推公式写错的代价是整个思路全错暴力转记忆化至少每一步都能验证。这道题里还有一个很大的易错点取模运算。路径方案数可能很大题目要求对某个质数取模但选手在计算的过程中如果先做减法再取模可能会得到负数必须加模数修正。我们队就有队友在这里丢了分因为本地测试的结果看起来差不多实际差了一个符号。4.2 图论题建图方式比跑什么算法更决定生死另一道压轴题是图论题我当时一眼看上去觉得像是单源最短路刚准备写Dijkstra再读一遍发现边权并不是直接给出的而是取决于当前节点的某种状态。这种边走边算边权的图论题最关键的步骤是状态扩展把原始图里的每个节点根据状态拆成多个节点再在新图里跑最短路。我说的这一题易错点在于同一个物理节点在不同状态下对应的编号。很多选手在拆点的时候搞混了映射关系导致最短路算法跑出的结果张冠李戴。我记得我们队的做法是写一个函数输入节点编号和状态输出拆点后的新编号所有出入边的更新都必须通过这个函数绝不手写硬编码。这种方式虽然多写几行但排错效率和正确率都明显提升。压轴题的另一类常客是最小生成树的变体。如果题面里既涉及连通性又涉及边权最小化而且图可能不连通那么先判断连通性、再跑最小生成树、最后检查是否能覆盖所有节点这个顺序不能反。我见过有人直接把不连通的情况当作生成树权值为0这显然是理解错了题意。图论题的得分关键真的就是先把图建对。4.3 优化落地滚动数组与大常数优化压轴题的最后一个技术点是优化。DP题如果状态是两维的数据范围一大空间就会爆。这时候很多人会想到滚动数组但滚动数组有个隐蔽的坑如果转移需要依赖上一轮的多个位置直接滚动会导致新旧数据混在一起。解决方法是在每一轮更新前把上一轮的数据备份一份或者调整遍历顺序让每个状态只依赖本轮之前已经计算好的部分。大常数优化我就不多说了只说一点在时间勉强够的情况下把vector换成长度固定的数组效果立竿见影。评测机对动态内存分配的惩罚在压轴题里会被放大。2020年那届的压轴题就有那么一两道题纯粹是卡常数算法写对了但实现太豪华也会TLE。另外图论题的邻接表存储我建议直接开一个足够大的边数组不要用vectorvector 这种方式。后者写起来方便但访问时多一层间接跳转百万级边的情况下速度差异很明显。如果读者平时习惯了用STL容器至少要在比赛前适应一下能用数组就不用容器的写法。5. 赛后复盘的五个教训比多拿50分更值钱5.1 输出格式少看半行10分直接蒸发赛后对照题面逐字看我们队有一道题就是因为输出格式翻车。题目要求每两组样例输出之间用一个空行隔开我写成了每组输出后都跟一个空行结果最后一组后面多了一行空白。这种错误在本地几乎看不出来因为评测机的文本比对是严格的多一个空格、多一个换行都会判错。我的建议是读题的时候只要看到输出格式四个字就把它当成一道独立的题来处理。可以在草稿纸上画一个输出模板标清楚哪些地方是空格、哪些地方是换行、哪些地方条件是除了最后一行。等代码写完之后再回头检查一遍输出分支尤其是最后一组和第一次这两个边界。5.2 变量范围与极端数据0、1、n1、最大值的检验几乎每场比赛我们都能在极端数据上翻车2020年也不例外。有一道题我至今记得n的最小取值可以是0我在代码里对n0的情况没有单独处理结果数组越界直接RE。后来我们队定了一条规矩每道题提交前至少构造四组极端测试——n取最小值、n取最大值、所有值相等、没有可行解。有些选手觉得构造极端测试浪费时间但我可以用亲身经历告诉你这五分钟能省下的罚时往往更多。尤其是RE和WA往往不来自正常数据而是来自空输入单元素满边界这种极端情况。记住一个原则评测机永远比你想的更会刁难人。5.3 团队节奏罚时是团队的事不是个人英雄主义的事在团队赛里罚时是比解题数更隐蔽的胜负手。我们队最终排名和另一支队伍非常接近仔细一看差距就来自罚时他们提交次数比我们少了几次尽管答对题数相同排名却在我们前面。罚时这个东西一个人乱抢会影响全队的净用时所以提交前的自查环节绝对不能省。我特别想强调一个协作细节在队友不确定自己的代码是否正确时别急着提交让另一个队友帮忙跑一遍极端测试再一起检查输出格式。这看起来是浪费了双倍的时间实际上避免了多次罚时而且两个人一起排查的纠错能力远远高于一个人。比赛后半段的沟通效率经常就决定了最后一小时能多拿多少分。5.4 把WA原因分类整理形成错题集赛后我做了一件很有价值的事把全队所有的错误提交拉出来按原因分成边界条件输出格式复杂度超限读题遗漏数据范围溢出五类。一统计发现接近一半的错误是读题遗漏也就是看漏了题目里的某个限制条件。这个比例远超我们原本的想象也直接改变了后续的训练重点。从那以后每次模拟赛或正式比赛我都会在结束后的当天写一篇简短的错题总结重点记录我为什么错而不是题怎么做。这种反思式的整理对长期进度的帮助非常大比再多刷几道题更有效。如果你也在准备算法竞赛我真心建议你也试一次这种分类复盘你会发现自己的坑集中在某些固定类型上知道了坑在哪才谈得上避开。5.5 最后分享一个关于比赛当天的食物与休息的经验听着有点跑题但这确实是很多队伍忽略的。2020年的线上赛要求全程在线三个小时对脑力和体力的消耗都很大结果我们队里有两个人中午没怎么吃东西后半程明显反应变慢简单的二分边界都要想半天。如果你要参加类似的长时间算法竞赛建议提前准备好高蛋白、易消化的干粮并把饮水安排在手边这三个小时里尽量别起身太久。还有一个小习惯比赛开始前按自己平时的作息时间上一次厕所。听起来很琐碎但真到了后半程多一次离座就可能打断思路。这些细节很难在题解里看见但我会说比赛的结果从来都不只是算法能力的比拼。关于2020年那届天梯赛的复盘我能写出来的核心经验就这些基础题要当进阶题对待贪心题先构造反例再排序压轴题先把图建对再想算法赛前一定要规划好输出格式检查和极端数据测试。希望这份复盘里的易错点能帮你避掉一些我当年踩过的坑。