1. 比赛背景与整体印象CodeM 2017是美团举办的第一届编程大赛初赛A轮作为第一道门槛我记得当时报名的人数相当可观基本上各大技术社区、高校BBS里都能看到讨论帖。和现在很多比赛上来就甩一堆业务场景模拟题不同2017年的CodeM更偏向纯粹的算法基本功考察A轮一共4道题覆盖了贪心、搜索、数据结构优化、动态规划这些最核心的算法方向。先说说对这套题的整体印象难度梯度做得比较合理。第一题属于签到题给选手热身的第二题开始需要一点思维转换第三题和第四题就是真正拉开差距的题目了尤其是第四题考场上能完整AC的人不多。我记得当时赛后讨论最多的就是第三题和第四题很多人不是不会做而是被卡在时间复杂度的优化上——这其实是初赛轮最常见的情况思路想出来了但代码跑不过大数据。如果你准备参加类似的编程竞赛这套题很适合用来做限时训练。我当时是掐着时间模拟的4道题给了120分钟最后的感受是题目本身不算偏难怪但对基本功的扎实程度要求很高。什么叫基本功扎实就是你看到一个题能不能快速判断出它属于哪一类问题然后直接往对应的套路上去想而不是现场去发明算法。另外要提一句CodeM 2017的计分规则是按通过的数据点比例给分不是AC/非AC二值判定所以哪怕你只能过部分数据也能拿到部分分数。这个规则很友好但也容易让人心存侥幸——想着“过了三个样例就交了”结果大数据一跑全挂。我自己的习惯是哪怕只过了部分样例也要先把代码交上去保住基础分然后继续优化而不是死磕一个题。2. A轮题目详解与思路拆解2.1 第一题签到题中的思维陷阱初赛A轮的第一题看起来很简单一群人排队给定每个人到达的时间和需要服务的时间问平均等待时间是多少。常规思路是直接模拟用一个优先队列维护当前正在服务的人和等待中的人每次取出最早到达的进行服务累加等待时间最后除以总人数。但这个题有一个细节很多人会忽略服务时间不是先进先出就能最优的。如果后面来了一个服务时间特别短的人让他先办反而能减少整体的平均等待时间。这就是经典的“最短作业优先”SJF调度思想在操作系统原理里学过但在竞赛题里换个马甲出现还是有不少人踩坑。我当时看到这个题的第一反应是“这不是模拟题吗”差点就直接写了个FIFO队列交上去。好在习惯性地先验证了一下样例发现输出对不上才意识到考的是调度策略而不是模拟。所以这里也想提醒一下签到题不等于无脑题尤其是比赛的第一题往往是为了筛选“认真读题的人”而设计的。题目里隐含的“最优”字眼就是在暗示你不能用朴素思路。正确做法是维护一个时间轴每来一个人就计算服务窗口的状态。我用的是priority_queue存当前等待中的人按照服务时间升序排列每次从队头取一个服务时间最短的人来处理。需要注意的边界情况是如果当前没有人在等时间要快进到下一个人的到达时刻不然会凭空多算很多空闲时间。这题的代码量不大核心部分大概三四十行就能搞定。但它是整场比赛第一道“拦路题”我当时看到不少人在讨论区说第一题提交了好几次才过基本都是栽在这个最短作业优先的思维转换上。如果你拿这套题做练习第一题建议设置一个硬性要求一遍AC不要返工因为这种送分题返工的心理影响是很大的。2.2 第二题字符串处理的边界考验第二题是给一个字符串和若干次操作每次操作翻转某个区间或者修改某个位置最终询问某个位置上的字符是什么。题面很短看起来人畜无害但这题真正的考点是字符串很长操作次数很多怎么维护才不超时。最朴素的做法是直接开一个字符数组每次操作就真的去翻转对应区间时间复杂度是O(n)每次如果操作次数一多整体就是O(n*m)直接爆炸。我当时第一反应是“这题要用线段树吧”因为区间操作基本都能往线段树上靠。但实际上这个题的经典解法是分块或者更简单的——用两个数组维护正序和倒序的状态。具体来说每次区间翻转操作可以用两个方向相反的标记来延迟处理。翻转一个区间本质上就是改变了字符串的读取方向你可以维护一个“当前反转状态”然后用数学方式映射每次查询的位置到真实的下标。这种技巧在字符串操作类题目里非常常见核心思想就是不要真的去改数据而是用一个标记记录“改了什么”在查询的时候再把标记计算进去。这个题的坑主要在两个地方一是下标转换的边界从正序到倒序的映射要仔细推尤其是区间端点的情况稍微搞错一位就全崩二是修改操作和翻转操作混在一起的时候标记的叠加要小心。我当时写了个辅助函数专门做坐标变换每次操作都调它测试的时候把随机小数据对拍了一下才敢交。这个题给我的启发是竞赛里很多题并不是考你知不知道某个高级数据结构而是考你能不能想到“用标记代替操作”这个建模思路。一旦想通这一点代码量反而很小跑得也飞快。很多选手说这个题难其实不是难在算法而是难在对“状态延迟”这个概念的不熟悉。2.3 第三题经典DP的状态压缩与优化第三题讲的是一个游戏关卡地图是二维网格里面有一些特殊点需要从起点出发经过所有特殊点再回到起点问最短路径长度是多少。这题一看就是经典的“旅行商问题”TSP变种特殊点个数不多但地图很大不能直接全图BFS每次跑一遍。解题思路分两步第一步先用BFS预处理出起点、终点、每个特殊点之间的最短距离因为地图虽然大但特殊点只有k个题目里给的是k≤10记不太清了但应该不超过15所以只需要k2个点的两两距离第二步在这k个点之间跑一个状态压缩DPdp[mask][i]表示当前已经访问过的特殊点集合是mask最后停在第i个特殊点时的最短路程转移就从mask里去掉一个点加上那一段距离即可。这题最大的陷阱是在BFS预处理的时候不要每次都全图BFS而是要充分利用每个点只BFS一次的特点。我当时是从每个关键点出发各做一次BFS复杂度是O((k2)nm)完全能接受。但如果写成每次查询都重新BFS一次那复杂度就翻了好几倍直接超时。状态压缩DP的过程本身不算难但要小心初始化起点到第一个特殊点的距离要提前算好最后回到起点的距离也要单独处理。我记得有一个坑是dp数组的初始值应该设为正无穷但如果起点和某个特殊点重合就在同一个格子上距离是0而不是无穷大这个边界要单独特判。这题我认为是整套题里区分度最高的一道。原因是它考察的不是单一知识点而是BFS 状态压缩DP 边界处理的综合能力任何一个环节出问题都做不对。如果你练这题建议自己写一个暴力全排列版本对拍这样能快速验证状态压缩DP的正确性。2.4 第四题思维型数据结构题第四题是一道偏思维的题题面是给你一棵树若干个询问每次询问两个节点之间的路径上出现次数最多的数字是哪个如果有多个取最小的。我看到这题的第一反应是树链剖分线段树维护区间众数但这个方向很快就把自己否定了因为合并两个区间的众数是有严格限制的不具备可合并性用线段树维护复杂度和正确性都是大问题。正确的解法是用莫队算法处理树上路径查询。先对这棵树做括号序展开欧拉序把一个树上的路径查询转换为一个序列上的区间查询然后跑带修改或者不带修改的莫队维护当前区间内每个数字出现的次数同时用另一个数据结构维护当前出现次数最多的数字。这里面的难点有两层第一层是树上路径转序列区间的映射。具体做法是对树做DFS进入节点时记录一次离开节点时记录一次总共得到一个长度为2n的序列。对于查询(u,v)如果u是v的祖先那么对应的区间就是l[u]到l[v]的一段如果不是祖先关系对应的区间是r[u]到l[v] 还要额外把lca(u,v)补上。第二层是维护众数这里不能每次查询后用O(k)去扫一遍要用一个桶记录每个次数出现次数然后一个指针维护当前最大次数这样每次增删数字的复杂度是O(1)整体复杂度才能控制在O((nm)*sqrt(n))左右。我当时做这题的时候卡了很久主要是在“树上路径转区间”这一步的理解上绕了弯子。后来自己画了几个例子才彻底搞清楚括号序的原理。如果你也在练这题建议先从链上的情况开始推再扩展到更复杂的树结构会容易理解很多。莫队的排序方式是这题的一个关键优化点不能简单地按左端点排序要用分块编号做按键块内再按右端点排序否则会退化。我第一次就是随手写了个普通排序结果在倒数第二个数据点超时了改成按块排序后直接就过了。这种常数级别的优化在竞赛里经常起决定性作用不要小瞧。3. 实战中的卡点与突破技巧3.1 最容易被卡住的I/O性能很多第一次参加这类竞赛的选手会忽略一个问题算法复杂度算对了但输入输出太慢导致超时。CodeM的评测系统对时间卡得比较严A轮的题量虽然不算大但第三题和第四题的数据规模上来了如果不做I/O优化很可能会出现“算法对了但TLE”的尴尬情况。我之前自己的经历就是写第一版代码的时候用cin/cout大数据直接卡死在读取上。后来统一改成scanf/printf实测第四题的速度提升了将近一半。如果你的目标是冲击高分还是建议比赛开始前就写一个快读模板用getchar实现整数的快速读取百来行代码的事但能在关键时候救命。这里也分享一个实用技巧在本地测试时一定要用大数据量做压力测试光靠样例通过是远远不够的。我一般会写一个数据生成器构造出满足题目上限的数据然后看代码跑多久。如果发现超过时限的50%就会去考虑是常数优化还是算法本身有问题。3.2 小数据对拍的调试方法A轮第三题和第四题有一个共同的特点暴力版本的代码很好写但正确版本不好调。这时候如果只靠自己盯着代码找bug效率非常低。我举个例子第四题的括号序转换如果映射写错了小样例可能侥幸通过但随机数据一跑就裂开。你要快速地验证正确性最好的办法是写一个暴力解法然后用一个脚本随机生成数据把暴力和优化的代码都跑一遍对比输出。我当时是用一个Python脚本生成小规模的树然后分别调用暴力和优化版的C程序逐次比较输出。这一步看着麻烦但实际节省的调试时间远超预期。如果你手头没有现成的对拍脚本可以花几分钟写一个。对拍的核心不是跑多少组数据而是每跑完一组就立即diff输出发现问题第一时间定位到具体用例上。3.3 时间分配和做题次序按照CodeM A轮的难度设置建议的做题顺序是第一题 - 第二题 - 第三题 - 第四题遇到不会的先跳过不要死磕。第四题如果写了30分钟还没有完整的思路建议先放一放回头把前面题目的部分分拿满再说。我自己的经验是比赛中最忌讳的就是在第三题上无限投入时间导致第四题完全没看。因为第三题虽然难但第四题如果正好是你熟悉的知识点反而有可能拿到大部分分数。我当时就是先花了大概40分钟把第三题做出来了然后留了一个小时给第四题虽然最后只提交了莫队的基础版本没有做极限优化但还是拿到了比较理想的分数。另外有一点想强调不要因为第一题简单就掉以轻心很多人在第一题上栽跟头是因为没有仔细理解题面中的“最优”两个字天真地采用了最简单的模拟策略。每一道题做完之后都花30秒重新读一遍题目确认自己确实没有遗漏任何条件。4. 常见问题与赛场经验复盘4.1 套路汇总从CodeM A轮看出的出题倾向很多准备比赛的同学喜欢到处刷题但我个人觉得针对一场比赛做专项复盘效率远高于漫无目的地刷题。从CodeM 2017 A轮这四道题来看出题方的口味显然偏向“经典算法模型的灵活变种”而不是偏难怪的ACM冷门题。第一题是最短作业优先调度第二题是区间反转延迟标记第三题是BFSTSP状态压缩DP第四题是树上路径众数统计全都是教科书里能找到原型的问题。关键在于每一题都在原型上做了一点变化。比如第二题虽然看起来是个“数据结构题”但最优解完全是数学化的坐标变换而不是真的去维护翻转后的字符串。这种“把数据结构的题做成思维题”的风格是这场比赛的灵魂。如果你要备考类似的美团CodeM建议把重心放在动态规划的优化状态、树上问题的序列化处理、以及贪心策略的思路证明这三个方向。4.2 我认为最值得反复练习的两道题如果让我挑两道题反复练我会选第三题和第四题原因很简单它们分别代表了竞赛中最常见的两类“易丢分陷阱”。第三题是典型的多知识点复合题BFS预处理距离状态压缩DP两道工序都必须完整且无BUG哪怕只是BFS里某个方向的顺序写错了在后面对拍时都可能暴露。多写几遍这道题能帮你养成“先对拍再交”的习惯。第四题是典型的思维转换题你很难通过“灵光一闪”在考场上现想出来必须靠平时积累“树上路径转序列”这一套路。这道题我建议每次都写完整版包括快读、分块排序、O(1)维护众数的桶结构而不是写个半吊子版本。因为考场上的时间压力下你不可能临时拼凑一个不熟悉的复杂度模型必须提前练到肌肉记忆的程度。4.3 赛前一周的备战计划参考如果你离比赛还有一周我建议这样安排前三天每天系统做一套往年A轮题限定两小时严格按照比赛节奏来记录自己每道题的耗时和正确率第四天和第五天针对薄弱环节做专项突破比如发现自己状态压缩DP经常转不出来就找5-8道类似的TSP变种题集中做最后两天减少新题量回归到错题复盘和模板整理上确保常用的几个数据结构和算法模板都能快速默写出来。模板这块值得多说一句不要小看那些看起来“很小”的模板比如莫队排序的块大小参数、状态压缩DP的初始化写法、树上括号序的DFS实现这些细节一旦需要现场回忆基本等于丢分。我自己的做法是整理一个代码模板库把常用的数据结构、算法片段都放进去并且每周抽空抄一遍练到不需要思考就能写出来。竞赛的本质还是基本功的比拼考场上的灵感和运气都是建立在大量基本功之上的。最后再分享一个小技巧比赛结束后一定要看别人的AC代码。CodeM当年的比赛在赛后是开放查看他人代码的我花了一整个晚上把第四题排名靠前的大神代码逐行读了一遍收获比刷十道题都大。尤其是那种代码风格精简、思路清晰的代码能让你看到自己的实现里有多少多余的步骤。这种“赛后学习”的习惯是我个人认为提升竞赛水平最有效的方式之一强烈推荐你也试试。