周六晚上我把AWC 0017 Beta这轮周赛打完了五道题最后AC了四道E题连提交都没交上。说实话这个成绩放在平时算不上好但复盘之后我反而觉得这一场比完整AC五道还要值A题吃过一次WAD题中途推翻重写了一版E题连模型都没来得及验证。踩过的坑越多复盘笔记就越有参考价值。这篇Blog就写给同水平段的选手我不会去复述官方题解的每一步而是把A到E这五档难度对应的常见考点、每道题真正在考察什么能力、以及卡题时我实际会做的决策尽我所能讲清楚。适合刚接触算法竞赛、每周打周赛想稳定AC三四题、但又经常死在读题不细和边界条件上的朋友。1. 开赛之后的前十分钟先通读题面再决定进攻路线我见过太多人包括我自己前两年的状态拿到题目立刻从A开始敲敲完A看B敲完B看C一路按顺序推下去。这个习惯在题目难度严格递增的场次里没有大问题但它浪费了比赛初期最宝贵的一段时间你没法判断后面几题里有谁是白送分、谁是地狱难度。一旦在B或者C卡住你的注意力会被拖死在已经投入的一道题上完全不知道这道题到底值不值得继续。现在我开赛的做法变了先花五到八分钟把A到E的题面全部扫一遍不要求看懂所有细节只看三件事——输入数据范围、操作类型、以及题面里的关键词。所谓关键词就是那些直接暗示算法的词排序、前缀、最大最小、路径、连通块、方案数、取模。这些词能在动手前帮我给五道题各自的分量快速排个序而不是懵着头写。1.1 我以前的错误做法从A到E按顺序硬推这里具体说说顺序打法是怎么坑我的。有一场类似的周赛我按顺序打到C题结果它是个需要绕一下的图论建模题我卡了四十分钟心态直接崩了后面D、E连题面都没好好看。赛后一复盘才发现D题只是个排序加双指针的贪心E题也谈不上做不出。如果我一开始就知道D题是弱题大可以先绕过C把能拿的分拿稳再回头啃C。顺序模式最麻烦的地方是让你被前一道题的心理消耗拖着走而不是根据全局难度合理分配精力。算法竞赛里时间比黄金贵第一步当然是获取全局信息。1.2 现在我在用的读题策略与时间分配表扫完全部题面后我会在草稿纸上按照自己的判断给五道题打一个优先级标记。这个优先级不是按A到E排而是按“性价比”排估计自己能不能做出来、大约需要多久、占用多少时间。以下是我给AWC 0017这种五题场次定的默认时间表实测下来节奏很稳阶段目标耗时控制心态关键词通读分类A-E全部扫一遍5-8分钟只标记不深入第一波A B20分钟以内快速通过错一发可接受第二波C30-45分钟想清楚再写避免重构第三波D45-70分钟选好数据结构再动手最后E剩余时间只求思路不纠结AC当然这只是参考Beta场有时前两题偏简单有时C题会成为全场毒瘤。核心思想是一旦预计某道题超过50分钟还没有稳定思路就标记“暂停”先去做后面的题把这道题的逻辑放在大脑后台自己转。我做D题时经常遇到这种情况强行写半天调不通放一放再看反而一眼看出关键条件。这个习惯看着很小但救过我无数次。2. A题和B题签到层级的题目是怎么把人绊倒的如果说整场比赛有哪两道的分最应该拿稳那必然是A和B。算法难度上这两道几乎没有门槛考的就是读题仔细度和代码基本功。但正因为简单选手特别容易在“顺手就写完”的放松状态里翻车WA一发还反应不过来为什么。2.1 A题标配是简单数学与模拟但输出格式处处是坑A题通常就是给定一组整数或一个字符串做一次简单运算或判断比如最大最小值、累加和、奇偶性、字符出现次数。算法上没有任何唬人之处真正的陷阱常藏在输出格式里。我翻过太多次车“每个答案占一行”和“答案之间用空格分隔”就差一个词结果完全不同。还有一次我在循环末尾输出了多余空格本地样例全部通过提交上去照样WA。对于A题我的经验是先把样例的输入输出格式看死在眼里再谈算法思路。提交前用肉眼检查一遍输出语句尤其是循环里换行和空格的写法。另外一个容易被忽略的点是A题也可能给到10^18量级的数据我现在把所有参与计算的变量一律定义成long long绝对不赌“这道题数值小”的运气。这种看似多余的谨慎在正式比赛里救了我很多次。2.2 B题最常见的两类失误字符计数与区间边界B题经常落在字符串或简单计数问题统计某种字符出现次数、判断子串是否满足某个性质、或者在分类计数上做简单推导。常见翻车点有两个。第一个是字符计数数组开小了只考虑了字母’a’-‘z’没有加上大写字母或数字某组样例直接数组越界。第二个是区间端点处理出错写成左闭右闭或左闭右开时差一个索引统计结果要么多算要么少算。我的对策是固定两套约定所有区间统一写成左闭右开[l, r)所有计数容器尽量用字典而不是定长数组。Python写dictC用map或者unordered_map这样就算字符集超出预期也不会越界。约定固定之后B题这类问题我很少再犯端点错误因为只需要记住一种写法不需要每道题现场重新推理边界。2.3 一道典型签到题的完整调试思路示例不搬原题面这里用A/B档最常见的模型演示我的排查流程。假设题目是“给定字符串s求出现次数最多的字符编号如果次数相同取编号更小的”看起来一句话写完但仍有四个细节值得核对第一输入是否可能为空串第二大小写是否参与排序第三输出的是字符本身还是ASCII码第四统计循环有没有漏掉最后一个字符。我的排查顺序是先构造几个小边界样例空串、单字符、全部相同、长度极大再检查变量类型是否能够覆盖字符的ASCII范围最后逐字对照输出要求。这个“签到题反而不急着写先列一遍边界清单”的习惯真的值得养成。它并不会让你多花两分钟但能省下因为WA而浪费的十几分钟。3. C题在暴力能过与必须优化之间做判断C题是周赛里真正开始有区分度的一道但它的区分度通常不在算法多冷门而在于你能否快速判断当前数据范围允许什么算法。很多人被C题卡住不是因为题目难而是因为他用了复杂度正确但常数极大的写法或者反过来拿着一个暴力就能过的题非要上高级优化结果把自己绕晕。3.1 先用数据范围估算复杂度决定朴素做法可不可行看到一道C题时我第一件事永远是看数据上限。这里提供一个我常年使用的估算标准1秒时限下大约能稳定跑2×10^7次简单运算1e6量级的数据可以用O(N)偶尔O(N log N)1e5量级用O(N log N)很稳O(N^2)就有风险2000量级允许O(N^2)如果只有20到30这个量级大概率是O(2^N)枚举或状态压缩。拿这个标准一框C题该用什么复杂度一目了然。AWC 0017这场我其实犯过一个小错误某道C题看到上限是2000我下意识觉得肯定要优化结果绕了一大圈才发现O(N^2)加少量剪枝就是正解白白浪费二十分钟。后来我每次都会强迫自己先算复杂度再决定优化方案绝不反向操作。这个原则看着简单但在比赛高压下很容易被忽略。3.2 连通块搜索模板多数网格类C题的通用解法C题最常见的载体是二维网格判断连通块数量、最大连通块面积、最短步数。这类题的解法高度模板化BFS和DFS都可行我偏好BFS因为迭代写法不容易爆栈而且求“从起点到目标点最少几步”天然就是BFS的强项。这是我每次都会从模板库调出的网格BFS骨架from collections import deque def bfs_grid(grid, start): h, w len(grid), len(grid[0]) seen [[False] * w for _ in range(h)] q deque([start]) seen[start[0]][start[1]] True cnt 0 while q: x, y q.popleft() cnt 1 for dx, dy in ((1,0), (-1,0), (0,1), (0,-1)): nx, ny x dx, y dy if 0 nx h and 0 ny w and not seen[nx][ny] and grid[nx][ny] #: seen[nx][ny] True q.append((nx, ny)) return cnt很多人栽在同一个地方忘记入队时就标记seen导致同一个点被重复入队轻则计数偏大重则无限循环。BFS里有一条铁律——入队即标记不要在出队时才标记。那个时刻已经晚了因为别的方向可能已经把队里同一个点又加了一遍。这个模板只要改改格子条件和结束条件就能覆盖大多数网格搜索类C题非常值得背下来。3.3 什么时候记忆化搜索比递推DP更省事如果C题上升到动态规划我发现不少选手会在状态定义上卡很久。这里有个取巧的方案先用记忆化搜索把状态转移方程写出来暂时不需要纠结遍历顺序。尤其是转移方向比较复杂、或者状态维度较多的时候记忆化搜索在编写上的心智负担要小很多。Python里直接用缓存装饰器C用一个初始化为-1的二维数组就能实现同样的效果。我个人的判断标准是一个递归函数只要返回值表达的是“从某个状态出发的最优结果”并且参数能唯一确定这个状态那么对它做缓存就不会错。等代码跑通之后如果性能不达标再改成递推也不迟。在C题阶段先保证思路正确、再优化常数这个顺序永远不会错。反过来先想着优化很容易写出一堆自己都看不懂的转移逻辑。4. D题数据结构选型才是真正的分水岭到了D题大部分选手不再卡“怎么写”而是卡“用什么写”。选对数据结构一道D题四十分钟能过选错两个小时都可能调不出来。D题真正考验的是你对数据特征和操作类型的敏感度。4.1 D题最常见的四类模型根据我长期补题的经验D题反复出现的骨架基本就四类。第一是区间问题包括区间和、区间最值、区间加减第二是集合关系包括连通性、合并、分组第三是动态维护比如插入删除后查最值或第K大第四是图论基础包括最短路、拓扑序、最小生成树。你可以把D题理解成一个“业务场景要求你用某种数据结构支撑高频操作”的题目。所以第一步永远是拆解操作类型是单点改区间查还是区间改单点取还是插入删除后动态求最值。这几类操作对应的数据结构几乎是固定的认不出来才是最大问题。4.2 在线与离线决定用堆、树状数组还是线段树的关键我判断数据结构时还有一个更前置的问题这个题目要求即时回答还是允许把所有查询收集起来再统一处理。如果允许离线很多题根本不需要线段树排序加双指针或者树状数组按顺序插入代码量和常数都小很多。如果需要在线回答则多半要上堆、有序集合或者线段树。举一个最常见的例子动态维护数组里的第K大。在线做法是两个堆或平衡树但如果所有查询都在最后给出就可以把所有数字读进来排序然后二分答案用前缀和验证思路瞬间清爽。离线思维是D题里性价比最高的能力之一。很多选手一看到“查询第K大”就条件反射去写平衡树其实离线条件下有更短更稳的路线。4.3 线段树与树状数组选型对比很多同学一看到区间题就写线段树其实很多时候树状数组更合适。我根据自己的使用体验把选择标准列在这里需求推荐结构理由区间求和 单点修改树状数组代码短常数小实现快区间最值 单点修改线段树树状数组维护最值比较绕区间加减 区间求和线段树懒标记或差分差分只能离线线段树支持在线区间覆盖 动态查询线段树懒标记覆盖语义比累加更好控制我的原则是“能树状数组就不线段树”。线段树写着写着容易在区间边界上翻车尤其是左右索引的写法和习惯一旦不统一调一个多小时的人不在少数。树状数组能覆盖的场景往往定义短、边界少反而更适合比赛快节奏。这不是说线段树不重要而是说不要在低需求场景里过度使用重型武器。4.4 卡题时的自救先写暴力再找优化点D题卡住的时候我的第一反应不是去查神仙算法而是先把一个O(N^2)的暴力写出来。这样做有三个作用验证对题意的理解拿到一个正确的基线答案通过暴力代码观察瓶颈到底在哪里。很多时候写着写着就会发现瓶颈集中在某一步的重复扫描那么只要针对这一步做数据结构优化就够了。我记得有一道区间众数相关的题暴力写法提交超时但盯着代码琢磨了一阵发现每次查询根本不需要重新统计全区间只需要维护当前使用的计数数组和当前最大值于是改成双指针扫描轻松通过。暴力不只是用来拿部分分的它其实是D题通向正解的最佳脚手架。这个习惯我每个赛季都会反复推荐因为它真的能救命。5. E题从题面特征反推考点模型E题在五题场次里基本决定了你能不能上分。它不一定比D题难多少但往往更冷、更有迷惑性。花三十分钟看出模型这道题就是白送的大分看不出来可能到比赛结束也只能空在那里。5.1 E题常见的五大考点方向我复盘过不少套题E题的出题方向相对集中在五个方向。第一是数论包括最大公约数、逆元、组合数取模第二是图论进阶包括树形DP、基环树、缩点后的处理第三是状态压缩DP第四是贪心构造题经常用到奇偶性、鸽巢原理、极值论证第五是二分答案配合某种贪心验证。这五个方向有一个共同点动手写代码之前必须先做一轮数学性质的观察。E题几乎不存在“读题直接套模板”的情况它考的就是你能否把题面的约束转化成某个已知模型的约束。5.2 从数据范围和关键动词识别算法识别E题模型时我看三个信号。第一是数据范围n不超过20的时候基本往状态压缩枚举想n在1e5左右并且题面出现“最大最小”优先考虑二分答案出现gcd、lcm、素数这些词直接切数论思路。第二是操作类型“每次可以翻转、选择、删除”往往指向DP或状态压缩“求最少步数、能否达到”指向BFS或者构造“请构造一组解”很多时候是贪心加归纳。第三是取模只要有“对某个模数取模”出现基本可以确定是一个组合计数DP你需要立刻去找状态定义而不是考虑模拟。这套“题面特征到算法模型”的对应表是我在每次复盘时都会专门记录的内容越积越厚识别速度也就越来越快。没有这个积累光靠临场推理E题很难在有限时间内拿下。5.3 复盘E题时我踩过的“想错方向”的坑提到E题我想讲一个心态层面的教训。有次做一道E题题面塞了一堆“最多”“最少”的条件我直接奔着贪心去写样例全过结果提交WA了三次最后还是放弃。补题看题解才发现那是一道二分答案check函数里套了一层贪心。为什么我没想到因为我在读题时把第一个念头当成了正确答案后面所有推理都在为这个念头找理由这就是典型的验证偏差。现在我的习惯是读完题先强迫自己列出至少两种候选思路分别估算复杂度和可行性再决定动手写哪个。这个小改变对E题正确率的提升非常明显。如果你也经常出现“样例能过但逻辑根本没有理顺”的情况不妨也试试这个方法。多列一个候选方案从来不会浪费太多时间。6. 赛后复盘与题解笔记才是涨分的主战场打完比赛AC四道也好、只AC一道也好真正决定下一次能进步多少的是赛后接下来几个小时你在干什么。我见过太多人比赛一结束就把题目抛到脑后下一场继续重复同样的错误。复盘这件事应当被视为比赛的一部分而不是可有可无的收尾工作。6.1 赛后三个小时内要完成的三件事比赛结束后我会给自己开一个“三小时复盘窗口”里面只做三件事。第一件把每道题的最终状态和耗时列出来包括WA了几次、TLE了几次并且标出哪些是不该犯的低级错误。第二件把卡住的题用自己的话重新复述一遍题意不看原题面看自己能不能写清核心约束。复述不出来的地方就是理解漏洞所在。第三件去查官方题解或其他选手的题解但只看思路不看完整代码然后自己重新写一遍AC。如果一道题看完题解还不能独立AC说明问题比想象的大需要回去补相关知识。6.2 怎么把题解写成自己看得懂、能复用的笔记很多人写题解就是把AC代码贴到博客里说实话意义很小。我自己笔记的格式很固定每道题记四行——考点标签、题意模型、关键结论或引理、我当时犯的错误思路。考点标签用来建立题目之间的联系比如“二分答案贪心验证”这道题和之前某道经典题共用同一个check函数就在笔记里互相链接。关键结论单独写因为那往往是别人一句话点醒你、但自己盯一天都想不到的地方。我从来不照抄别人的代码。代码是逻辑的投影只有自己重新写一遍才真正把逻辑内部化。建立错题地图比追求题量更有用这是我的核心看法。6.3 我觉得值得长期维护的三类代码模板最后说说模板库。我建议每个选手都维护三档模板基础档包括常用头文件、快速读入输出、整数二分、前缀和结构档包括BFS/DFS、并查集、树状数组、最短路径进阶档包括线段树懒标记、组合数取模预处理、状态压缩DP骨架。这三档不是用来背的而是帮你在比赛里节省“从零开始敲”的时间。更重要的是每次补题如果发现某类模板的形态和当前解法不一致要第一时间回头修改模板。我自己就是在反复修改模板的过程中逐渐理解了为什么标准写法要那样写。主动维护模板远比从网上下载一份“大全”更有用因为只有经过自己验证的代码才在比赛时用得安心。比赛打完真正值得庆祝的不是AC数量而是你手里又多了几张清楚的错题地图。AWC 0017 Beta这场我的AC率不算亮眼但复盘之后得到的几个判断标准——先读全部题面、先算复杂度、先选数据结构、先列出候选思路——我会应用在接下来每一场周赛里。希望这份思路复盘也能帮你少走几段弯路至少别再让A题和B题把状态搞崩了。