★ FEATURED ARTICLE 每年天梯赛结束总会有一批队伍到处找上一年的全国总决赛题集。2019年那套题集我至少刷了三遍第一遍以选手身份第二遍带新队员第三遍纯属看不服气。说实话这套题集最厉害的地方不是题目本身而是它把程序设计竞赛里最基础但又最容易被忽视的细节全部筛了一遍。今天不聊比赛当天多紧张也不灌鸡汤只讲题集的结构、核心考点、刷法还有我们踩过的坑。无论你是第一次参加天梯赛的队伍还是准备省赛之后冲总决赛的老手这套题集都是绕不过去的参照物值得花时间琢磨透。1. 一页看懂2019天梯赛总决赛题集1.1 题集结构和赛制特点天梯赛和普通的ACM赛制不太一样。ACM是三个人一台机器一题一提交按照通过题数和罚时排名。天梯赛强调的是“团体”和“阶梯”。整个比赛分成L1、L2、L3三个级别对应基础题、进阶题、难题题目的分值和难度都随级别上升。队伍总分的计算方式决定了你不能只把难题做得很漂亮基础题才是保命的底盘。2019年这套全国总决赛题集整体给我的感觉是基础题真的基础但基础不等于无脑进阶题开始考验你对数据结构的理解而不仅仅是会写模板难题则不再是“背个算法就能过”那种需要现场建模的题目特别多。很多人一开始会陷入一个误区觉得L3分值高比赛时就应该优先做L3。实际上天梯赛的时间很紧L1题量不小而且每题都需要读题、写代码、验证这些看起来简单的题一旦在细节上翻车浪费的时间够你把一道L2的栈模拟写完。所以拿到题集之后第一件事不是去看L3而是把L1从头到尾过一遍看看有没有会做但是容易写错的题。1.2 评测环境、编译器和提交策略2019年的比赛评测环境通常基于Linux支持的编程语言包括C、C、Java和Python。这里有一个非常现实的问题语言选型直接影响你在赛场上的速度。队伍里如果有人的C比较扎实那么L1和L2的大部分题目用C写完全没有问题标准库里的字符串处理、排序、队列、栈都能直接用写起来比Python更稳至少不会出现莫名其妙的超时。Python在简单题上有语法优势但遇到L2后半段的循环模拟、L3的图论和DP效率会差不少。我见过不少队伍在练习时用Python把L1做得飞快结果到了L3直接卡到大样例超时整套策略都被打乱。所以我的建议是以C为主线Python只用来查数据或者临时验证小样例。还有一个很多人忽略的细节提交前一定要确认编译选项。天梯赛部分题目对输出格式极其严格多一个空格、少一个换行都可能直接判错。这套题集里有个特点就是题目描述中的“输出格式”写得特别长很多人急于看输入输出样例反而把中间那段格式要求漏掉了结果白白送分。2. 逐层拆解L1、L2、L3分别卡住什么人2.1 L1那几道题最容易丢分的不是算法而是细节L1的目标是让你得分但想拿满并不容易。2019年题集里的L1涉及不少字符串处理和格式化输出。看起来都是“读进来处理一下输出去”可一旦输入里混着空行、空格、换行就很容易让你出错。举个很典型的例子有一类L1题需要按字典序输出多个字符串并且要去重。有人可能会直接用“排序后相邻判断”来做这没问题。但题目的坑在于字符串中间可能包含数字和大小写字母如果不看清比较规则直接用ASCII码排序就会与预期输出不一致。这时候需要先明确题目给的是“字典序”还是“不区分大小写”再决定怎么写比较函数。另一个常见的丢分点是数组大小。L1题的数据范围看起来不大但有些人习惯性开100的数组结果输入数据到了1000就爆。2019年这套题集里至少有2道L1题的数据范围是稍微看一眼就能通过的可如果你没养成“先看数据范围再开数组”的习惯很容易在验证时用大样例把自己搞崩溃。在训练新队员时我会专门让他们做这类题并要求每一步都加上注释读入什么、处理什么、输出什么。表面上看是浪费时间实际上能够避免“自我感觉写对了但运行结果就是不对”的尴尬。2.2 L2的进阶题数据结构才是分水岭到了L2题目难度明显上了一个台阶。2019年题集里大量出现栈、队列、树和并查集。不是说这些数据结构本身很难而是题目常常给你一个场景需要你自己判断该用哪种数据结构来建模。举个例子有一类L2题是关于“模拟排队”的。如果用数组做删除一个人之后所有后续元素都要往前移动时间复杂度会很难看。正确的做法是用队列或者双端队列甚至用优先队列处理“固定优先级”的排队逻辑。很多队伍卡住不是不知道队列怎么用而是没意识到这题需要队列。树相关的内容也是L2的重头戏。二叉树的遍历、根据遍历序列还原树、层序遍历输出这些几乎每年都会出现。2019年这套题集里有一道题让我印象很深它要求你根据前序和中序遍历还原二叉树再输出层序遍历。理论上这就是一个递归建树问题但很多人在还原时搞不清楚左右子树的区间边界递归索引算错一位就全盘皆输。我后来总结了一个口诀前序找根中序切分递归建树层序用队列。凡是碰到“给两种遍历求另一种遍历”的题都是这个套路。关键是写代码之前先在草稿纸上面画一棵小树把索引区间标清楚再动手敲。很多人跳过了这一步直接写递归结果满屏越界。2.3 L3难题考的是拆题能力L3题目不多分值却很大。2019年的L3给我的感觉是算法模板只是入场券真正的分水岭是你能不能把题目的场景转化成经典问题。有些L3题表面上是“在地图上找一条最短路径”实际上还要考虑路径上的某种限制条件比如某些节点必须经过、某些边在某些条件下不可走。这就不是裸的BFS或者spfa能解决的了可能需要多状态的最短路也就是把访问状态和当前位置一起放进优先队列里。看起来复杂但如果你在训练时练过“分层图”或者“状态压缩”看到这个场景就会条件反射地想到建图方案。动态规划也是L3常客。有一类题是“选物品但有限制条件”标标准准会让人想到背包。可题目会把限制条件藏得很深比如“每选一个物品其他某些物品的价值会变化”这就要求你用更复杂的状态定义。我在刷这套题集的时候发现自己的DP状态设计还是太常规遇到这种变化就卡壳。后来我把题集里所有的DP题集中起来每道都重新推一遍状态转移慢慢才有感觉。还有一类L3题属于大模拟。这种题算法含量不高但代码量极大稍微写错一个数据结构的更新逻辑调试就能花掉一个小时。2019年题集里的大模拟题细节多到简直像读一份说明书。我的建议是这种题留到最后有时间再做不要一开始就跟它死磕。3. 我们队的复盘一道题如何毁掉整场比赛3.1 赛前分工与热身赛摸底天梯赛虽然是团队赛但每个人都有自己的职责。我们队当时的分工很简单一位同学负责L1和L2的前半段一位同学专攻L2后半段和L3我负责整体的题目排序、数据结构和查代码。这个分工看起来很清晰实际运行起来才发现有一个致命问题负责L1的选手如果卡住会卡住整个队伍的开局节奏。热身赛的时候我们就发现了。一位队友写L1的字符串题因为忘记考虑输入中的空行连续提交了三次都判错。那时候我们只有几分钟就进入正式比赛整个队伍的心态都有点焦躁。所以后来我们调整了策略正式比赛开始后的前20分钟所有人先把L1所有的题都看一遍每个人挑自己最有把握的两三道先写形成“多点开花”的局面而不是让一个人从头写到尾。这道题集的L1虽然不难但很讲究第一次读题时的准确率。如果你能保证前几题一次性通过就会给全队带来稳定的节奏。一旦开局就频繁交错误后续的L3做题时间会被严重压缩。3.2 赛中的一个教训int越界能耽误三十分钟那次正式比赛最让我记忆深刻的是一道L2的模拟题。题目本身并不复杂只是需要累加很多数值然后比较大小。一位队友很快就写出了代码自己测试小样例也能通过但提交后总显示答案错误。我们三个人围在一起看了一个多小时最后才发现拿到核心数据用的变量是int类型而题目的数据范围明显允许累加结果超过32位整数的上限。这就是题集里那种“表面朴素实则暗藏杀机”的典型。数据范围写在题目描述里但很多人写代码时不会刻意去看。如果换一个细心的人可能在读题阶段就注意到“保证结果不超过2^31-1”这类字眼但我们那次就是没注意白白浪费了时间。这次之后我们定了一个规矩每读完一道题先用笔在草稿纸上写清楚数据范围和可能的最大值然后开盘前在代码里给关键变量用long long。这个习惯虽然简单却让后面刷题和比赛的出错率降低了很多。所以我不止一次跟别人说刷这套题集的时候一定要把每一道题的数据范围当重要信息去读而不是扫一眼跳过。4. 这套题集怎么刷才最有价值4.1 刷题顺序和时间规划很多人拿到2019年总决赛题集直接就按顺序从L1做到L3我觉得这样效率不高。更好的方法是先把整套题集分类按照知识点重新排列。因为同一类型的题目集中刷你会更容易总结规律而不是今天做字符串、明天做图论知识点散成一堆。我当时把题目分成了几组字符串和模拟、线性表、树、图论、动态规划。每组花一周左右的时间每天安排2到3道题。第一遍不用计时目的是把每道题完整吃透写不出标准答案也没关系但一定要写到最后能通过所有测试点。第二遍开始计时模拟比赛环境只给自己3小时尽量让自己回到赛场上那种压力中去。第三遍专门针对错题和勉强通过的题重新写一遍不再看原来的代码。如果你有队员一起刷可以尝试组织2到3次高仿真模拟赛。不要单独做题而是实打实地三个人一起坐在机房里用一套题目跑3小时模拟提交和打印的错误报告。天梯赛的节奏感需要在真实环境中养成光靠个人刷题很难培养。4.2 如何建立自己的错题笔记刷题不是看刷了多少道而是看你有没有从错题里提炼出规律。我发现大多数人的错题笔记只是把错误代码贴进去下一遍刷的时候根本不会回头看。正确的做法是给每道错题写一段“复盘话”包括三件事错在哪一步、为什么错、下次怎么预防。举个例子在刷二叉树的遍历时我经常错在递归边界。后来我在笔记里写了几种常见的边界情况比如“当序列区间左边界大于右边界时当前节点必然为空”“中序区间长度和前序区间长度必须一致”等。到了比赛时再遇到类似的题我会先在草稿纸上把这些边界写出来再开始编码基本不会再出同样的错。错题笔记还有一个用途是筛选重点。2019年这套题集里有些题目你第一遍就做出来了第二遍仍然做得很快那就不用反复刷。但有些题目你第一遍看了题解才做出来第二遍还卡住这种题才是你的重点靶子。把有限的练习时间花在这些题上性价比远大于漫无目的地重新刷整套题。5. 备赛工具箱与常见坑点速查5.1 考点和模板清单如果你准备用这套题集备赛至少要把以下知识点整理成自己的“模板库”不需要背太多但每个模板都必须在3分钟内无错写出来大数加法与乘法、字符串哈希快速判断相同子串、栈与队列的自定义模拟、二叉树数组存法和结构体存法、并查集带路径压缩与按秩合并、最短路Dijkstra堆优化、SPFA、Floyd、DFS和BFS的经典写法、01背包与完全背包的一维滚动数组写法、最长上升子序列和最长公共子序列动态规划。2019年题集里树和图相关的题比重不低所以要特别注意模板的鲁棒性。很多模板你在纸上能写出来但敲到编辑器里时会犯下标错误比如并查集的find函数忘记路径压缩、Dijkstra的优先队列里存成“点号”而不是“当前距离”这些错误光靠背模板是防不住的必须实际多跑几遍大样例。5.2 常见报错和排查技巧实录评测结果一般包括编译错误、答案错误、运行超时、内存超限、段错误等。我根据刷题经验整理了一份快速排查表评测结果常见原因排查思路答案错误输出格式不对、排序规则理解错、int越界仔细看输出格式用题目给的最小样例手算一遍检查变量范围运行超时算法复杂度太高、死循环、输入输出太慢用大数据试跑关闭同步流改成更优算法段错误数组越界、递归栈溢出、未初始化指针开大数组到上限加5递归改为循环或显式栈用调试器定位内存超限开了过大数组三维数组或DP表过猛压缩状态滚动数组把数组类型改为short或bool编译错误缺头文件、变量名冲突、用错重载函数本地编译看第一行错误注意C和C的差异很多人在正式比赛时遇到运行超时下意识只想优化局部代码其实问题可能出在输入输出上。C里的cin和cout默认同步会把性能拖得很慢特别是在循环里频繁读入的时候。只要在main函数第一行加上ios::sync_with_stdio(false)和cin.tie(0)很多超时问题就消失了。如果题目里包含大量整数还可以自己写快速读入用getchar配合累加解析效果立竿见影。还有一种排查技巧是针对答案错误。不要只测试题目里给的样例那太少了。我会自己构造几组边界数据空数据集、全部相同的字符串、最小和最大的数值、数据范围顶点的值然后把期望答案甚至用暴力法算出来再跟自己的代码结果对比。这套题集里很多题的隐藏测试点就是这些边界情况平时养成测试边界的习惯比赛时会省很多试错时间。提示哪怕在训练时也不要得理不饶人地反复提交同一份代码。每次提交前先停下来读一遍自己的输出格式和题目要求是否完全一致。很多时候判错不是算法问题就是因为多了一个看不见的空格。6. 从刷题到比赛心理节奏也是一种能力准备2019年总决赛题集时你会发现它的难度曲线很典型L1让你兴奋L2让你紧张L3让你崩溃。这是好事。它模拟了真实比赛里的情绪波动。如果你刷的时候没有经历过“以为稳了结果错麻了”的感觉到了正式赛场可能会更慌。我个人的经验是每次刷这套题集不要一个人闷头刷。找两三个水平相近的朋友一起卡时间做然后互相讲题。讲题的时候你会发现自己是否真的理解了算法而不是背下了模板。2019年题集的很多题目其实一两个人也能做但团队氛围会让你发现自己平时根本不会暴露的问题比如“写代码时容易分心”“队友写错时不敢指出”这些非技术问题。另外不要忽视赛后总结会。每次模拟赛结束我们会把每道题第一位写出代码的成员、花费时间、提交次数全部记下来。一段时间后你会发现某个成员总是在排序题上多花时间某个人总是在大模拟题上陷进去。这些数据比“我感觉我哪里不错”要可靠得多针对性训练时也更有据可依。这套2019年题集就像一面镜子。它能测试你的代码基本功也能测试你面对复杂题时的取舍能力。如果你想在正式比赛中稳定发挥不妨把这套题集的每一道题都当成一次小型面试不仅要会做还要能在别人问“为什么这么写”的时候把推理过程讲清楚。这种能力恰恰是很多人刷题刷得再多也得不到的。
阅读完成 · 觉得有帮助？
