2017年我还在学校的时候看到同学群里有人转了一个比赛链接CodeM 2017美团编程大赛资格赛。说实话当时很多人的第一反应是“美团的比赛他们不是做外卖的吗怎么也开始搞算法竞赛了”。后来才明白这是美团技术团队主办的年度编程大赛面向全社会开放资格赛是线上答题按排名晋级后续轮次。当时我抱着“试试水、顺便看看大厂出题思路”的心态报了名赛后复盘才发现这套资格赛题目质量相当高覆盖了算法竞赛里最常见的几类考点而且每道题都绑了一个贴近业务的场景做起来还挺有意思。这篇文章不聊比赛本身的组织细节我想从参赛者的角度把资格赛的赛制逻辑、出题风格、典型题解和备赛经验完整拆一遍。适合下面这几类人看准备参加算法竞赛的学生、想进互联网公司做研发的在职或在读同学以及纯粹想了解“大厂笔试题到底考什么”的好奇读者。1. 赛制拆解资格赛到底在筛什么1.1 为什么美团要办一场编程大赛2017年前后国内大厂办算法竞赛已经不算新鲜事不少头部互联网公司都有自己的编程大赛。美团这时候下场办CodeM明面上是一次技术品牌活动实际诉求很直接用真实业务场景包装算法题提前触达一批动手能力强、算法功底扎实的工程师。你想一场线上比赛可以覆盖全国范围内的候选人成本远低于一场场宣讲会而且能在短时间内用排名把人才筛出来。对技术团队来说这是性价比极高的招聘前置动作。参赛者在提交代码的过程中相当于提前经历了几轮“业务建模 代码实现”的模拟笔试主办方也能通过榜单快速定位高水平选手双方都不亏。对参赛者来说这种比赛的意义同样明确。互联网公司的笔试面试题本质上也是在考“在规定时间内用代码解决一个有约束的实际问题”和打算法竞赛高度重合。所以即使不冲着名次去单纯把资格赛当一次模拟笔试也是稳赚不赔的。1.2 资格赛的定位海选关不卡人但也不放水先说一下资格赛的形式。线上答题限时完成若干道编程题按正确题数、罚时等综合排名排名靠前的选手进入下一轮。门槛很低注册账号就能参加所以参赛人数会特别多。资格赛的核心任务就是“海选”从大量选手里筛出一批有基本算法能力的人。海选阶段的题目设计非常有讲究。如果出太难一堆人零分区分度就很差如果出太简单人人满分也起不到筛选作用。所以资格赛的题目通常呈阶梯状前一两道是签到题考察基本功保证认真准备过的人能拿分中间一两道是中等题考常见算法套路最后一道是压轴题用来区分高水平选手。我当时的体感是资格赛题目覆盖的知识点集中在这些方向字符串处理与模拟、贪心、动态规划、图论基础并查集、最短路、简单数理逻辑。并不追求偏题怪题而是考察“面对一个业务场景能不能把它抽象成经典算法模型并快速实现”。这一点和很多同学想象的不太一样——大厂比赛并不是为了炫技而是看你在真实问题面前有没有建模意识和代码落地能力。2. 题型考点分布资格赛的出题套路解析2.1 难度阶梯和出题比例根据我自己的参赛经验加上赛后和其他选手交流资格赛题目大体上可以按难度分成三档。整理成一张表方便对照难度定位常见考点目标人群低签到题送分、建立信心字符串、枚举、排序、模拟所有认真准备的参赛者中主力题拉平均分贪心、DP、二分、简单图论有一定刷题量的选手高压轴题区分名次数据结构、数论、综合思维题竞赛选手、冲奖高手这个分布不是随便拍脑袋定的。主办方要保证签到题能让大部分人拿分晋级线不会太低但晋级名额就那么多所以中等题必须能拉开差距最后再来一道压轴题把最顶尖那批人筛出来。看懂这个逻辑之后做题策略就很清晰了先稳稳拿下签到题再集中火力攻中等题压轴题放到最后尽力而为。2.2 核心考点的应对策略字符串和模拟题几乎必考因为这类题最能体现“仔细读题”和“边界处理”能力。面对字符串题第一件事是看清楚字符集范围和数据量是不是大小写混合、要不要去标点、有没有空格、总长度是否可能达到10^6级别。这些直接决定你用map还是unordered_map、用string处理还是字符数组处理。签到题的程序量不大但边界条件往往藏在题目描述里读题稍微粗心就容易错。贪心题是资格赛的常客因为贪心策略“想到就很快想不到就卡死”区分度很好。常见的处理方式是先排序再维护一个数据结构堆、栈、单调队列来做决策。做题时有个经验如果题目让你求“最大能完成多少”“最小需要多少”先尝试从排序加维护极值的角度想大概率能摸到正解。DP题在资格赛里不会出太难的通常是线性DP或背包变形重点是定义好状态、推好转移方程。一个很实用的判断标准是如果转移写起来很别扭往往说明状态设计得不对换个维度定义状态通常就顺了。图论题通常以“判断连通性”“求最短路”“找环”等形式出现。并查集几乎是默认知识点遇到连通性相关问题先想并查集最短路则看数据范围决定用哪种算法。这里多说一句求正权最短路优先写堆优化的Dijkstra别用SPFA后者在竞赛数据里容易被卡成O(n * m)得不偿失。3. 典型题目还原与代码实现先说明一下下面的题目是根据CodeM 2017资格赛的出题风格和考点做的一次“合理还原”不是当年的原题粘贴。但题型、难度、知识点覆盖和真实比赛是一致的拿来练手或体会当年比赛的感觉都合适。3.1 签到题餐厅评价关键词统计题意还原给出n条餐厅评价文本每条由若干单词、标点、空格组成。要求统计全部文本中出现频率最高的k个单词单词不区分大小写标点不计入单词。输出按出现次数从高到低排序次数相同按字典序升序。思路拆解这是一道标准的字符串模拟题考三点字符处理小写化、去标点、哈希统计、排序。很多人一开始会忽略“标点不计入单词”这个细节导致统计出来的单词串是带标点的和预期结果对不上。正确做法是逐个字符扫描遇到字母就累加进当前单词遇到其他字符就认为单词结束进行统计。#include bits/stdc.h using namespace std; int main() { int n, k; cin n k; string line; getline(cin, line); // 吃掉第一行末尾的换行 mapstring, int cnt; for (int i 0; i n; i) { getline(cin, line); for (char c : line) c tolower(c); string cur; for (char c : line) { if (isalpha(c)) { cur c; } else if (!cur.empty()) { cnt[cur]; cur.clear(); } } if (!cur.empty()) cnt[cur]; } vectorpairstring, int v(cnt.begin(), cnt.end()); sort(v.begin(), v.end(), [](const auto a, const auto b) { if (a.second ! b.second) return a.second b.second; return a.first b.first; }); for (int i 0; i k; i) { cout v[i].first v[i].second \n; } return 0; }复杂度是O(total_len m log m)m是不同单词数。注意这里用map而不是unordered_map是因为map本身按字典序存储虽然最后还是要统一排序但用map能让统计过程更直观。如果你用unordered_map统计完再转vector排序效果也一样习惯哪个用哪个。3.2 主力题骑手订单调度贪心 最大堆题意还原外卖骑手手上有n个订单每个订单有两个属性配送耗时t_i和截止时间d_i。骑手同一时刻只能配送一个订单从0时刻开始送完一个才能送下一个。问最多能完成多少个订单。思考过程求“最多能完成多少个”这种最值问题第一反应是贪心或DP。再看约束每个订单做完需要耗时t_i且有截止时间d_i这是非常典型的“任务调度”模型。经典解法是把订单按截止时间从小到大排序从头处理用一个大根堆维护“已经选择的订单的耗时”。每处理一个订单先假定选择它把耗时加入堆同时累加当前总耗时如果总耗时超过了当前订单的截止时间说明在保证这个订单不超时的前提下我们选的单子太多了需要丢掉一个耗时最大的订单把总耗时降下来。最终堆里剩下的订单数就是答案。这个贪心的正确性在于按截止时间排序后永远优先处理更紧急的订单当出现冲突时丢掉耗时最长的订单是最优的因为这样能让总耗时下降最多给后续订单留出最大空间。这也是“用堆反悔”的经典思路——普通贪心只能顺序做选择加上堆之后就能动态调整之前的选择。#include bits/stdc.h using namespace std; struct Order { int d, t; }; int main() { int n; cin n; vectorOrder a(n); for (int i 0; i n; i) { cin a[i].d a[i].t; } sort(a.begin(), a.end(), [](const Order x, const Order y) { return x.d y.d; }); priority_queueint pq; // 大根堆存已选订单耗时 long long cur 0; for (const auto o : a) { pq.push(o.t); cur o.t; if (cur o.d) { cur - pq.top(); pq.pop(); } } cout (int)pq.size() \n; return 0; }复杂度O(n log n)。这个题用long long存总耗时是因为n可能到10^5t_i可能到10^9累加很容易爆int。这个细节在比赛中很关键不少人挂在“int溢出”这种问题上实在不值。3.3 压轴题商家网络连通并查集题意还原本地生活平台有n个商家节点m条已有的合作关系无向边。平台想让所有商家节点都连通问最少需要新增多少条合作边。数据范围较大n、m都在10^5量级。思路拆解把商家当成图上的点合作关系当成边问题就变成了“当前图有多少个连通分量”。要让整个图连通最少需要加的边数是“连通分量数 - 1”因为每新增一条边最多能把两个连通分量并成一个。统计连通分量最方便的工具就是并查集。这里有一个容易忽略的点并查集的路径压缩要写对否则在大数据量下会退化成一条链导致查找接近O(n)。另外统计连通分量个数时要在合并完成后重新遍历一遍所有点数一数有多少个点的父亲是自己。#include bits/stdc.h using namespace std; const int MAXN 100005; int fa[MAXN]; int find(int x) { return fa[x] x ? x : fa[x] find(fa[x]); } int main() { int n, m; cin n m; for (int i 1; i n; i) fa[i] i; for (int i 0; i m; i) { int u, v; cin u v; int fu find(u), fv find(v); if (fu ! fv) fa[fu] fv; } int cnt 0; for (int i 1; i n; i) { if (find(i) i) cnt; } cout cnt - 1 \n; return 0; }复杂度近乎O(n m)并查集加路径压缩后单次操作均摊O(alpha(n))alpha函数可以认为是一个很小的常数。这道题的思维方式很有代表性很多看似业务化的场景剥掉外壳之后就是教材上的经典模型。你在比赛里能不能快速做出来取决于你脑子里积累了多少这种“模型库”。4. 参赛全流程实操与避坑指南4.1 赛前准备别忽略这些小事比赛前第一件事是确认比赛环境。我是提前一天在本地把编译器、IDE、快捷键都调好然后在比赛平台上试了试提交流程提交了一道AB确认评测结果能正常返回。这个动作看起来多余但对第一次参赛的人特别重要——万一比赛开始后发现自己连提交按钮在哪都找不到心态直接崩掉。第二件事是准备自己的代码模板。我习惯准备一个C模板包含bits/stdc.h、using namespace std、常用的typedef和快读函数。比赛开始后不用花时间写这些基础代码。注意模板不是越多越好我见过有人背了一整套几百行的板子结果每道题的代码量都不大模板根本用不上还占脑子。准备最基本的几个就够了。第三件事是阅读规则。资格赛的排名规则一般包含正确题数和罚时两个维度罚时通常指“从比赛开始到通过该题所花的时间加上错误提交的罚时次数”。这意味着如果你预计一道题可能调很久不如先跳过把能拿的分拿了再回来处理难题。罚时规则对做题策略的影响非常大忽略它的人往往会在排名上吃大亏。4.2 比赛中的做题顺序和时间分配我的习惯是拿到题先整体扫一遍判断每道题的难度和考点然后从签到题开始做。正常情况下签到题10到20分钟内应该通过中等题控制在30到40分钟一道压轴题留到最后能做多少做多少。这里分享一个实际经验不要盯着一道题死磕超过40分钟。算法竞赛里“卡题”是常有的事卡住的时候越焦躁越写不出来不如先换一道题换换脑子。我那次比赛就有一道题想了很久没思路先放下把后面的题做完了回头再看那道题突然找到了正确的贪心方向。这种“顿悟”其实是因为大脑在后台继续处理信息换题不是放弃而是给思维松绑。输出格式也要特别留意。有些题目要求输出到小数点后多少位或者对行尾空格做了严格限制。我见过不少人在这种地方莫名其妙地WA浪费大量罚时。提交前务必看一眼输出格式要求每个输出间用空格还是换行行尾要不要保留多余空格这些细节能救命。4.3 赛后复盘的正确姿势比赛结束不等于学习结束。我每次比赛后都会做三件事。第一对照题解把自己没做出来的题重新想一遍不看题解自己动手写直到通过为止。直接看题解是最低效的复盘方式因为那样你只是“看懂”了而不是“会做”。第二整理“卡点清单”记录当时卡住的原因是想错了算法、边界条件没处理好还是代码实现写得有bug。第三把比赛题目按考点归类补充进自己的刷题笔记让这些题成为后续复习的一部分。复盘不是浪费时间恰恰是水平提升最快的方法。特别是对于资格赛这种难度适中的比赛错过的题往往对应你知识体系里的薄弱环节。把薄弱环节补上下次遇到同类题就是送分题。5. 高频问题速查与算法进阶建议5.1 比赛中常见的“送命”问题整理一个我在比赛和日常刷题中见过的高频问题表排查思路也写在里面问题表现排查思路读入错误多读一行、漏读一行、字符串带空格读不全检查getline和cin混用必要时手写读入数组越界本地跑正常提交后随机RE或TLE检查数组大小是否按题面上限 5 开爆int中间结果变成负数或答案明显偏大涉及累加、乘法时统一用long long死循环提交后TLE检查while/for循环条件和自增变量排序条件写反输出前几个名次和预期相反手写样例推一遍排序比较函数多组数据未清空结构第二组开始答案越来越离谱每组开始时重新初始化全局容器这些问题的共同特点是本地调试时很难复现一提交就暴露。原因多半是对题目约束理解不到位或者对C底层行为不熟悉。建议比赛前专门花时间把常见RE、TLE、WA的成因过一遍能省下不少冤枉罚时。5.2 从资格赛到决赛的进阶路径资格赛只是CodeM的第一关晋级之后还有初赛、复赛甚至线下决赛题目难度会逐级提升。如果你是以“拿到好名次”为目标的选手我的建议是把刷题规划成三个层次。第一个层次是巩固基础字符串、模拟、排序、二分、简单贪心这些是必须拿满分的部分。按专题刷100道左右就能形成肌肉记忆看到题就能条件反射地想到对应解法。第二个层次是掌握核心套路熟练写出堆优化的Dijkstra、并查集、线性DP、背包问题、常见贪心模型。这个阶段的关键是理解算法适用场景而不是背模板。你要能说清楚“为什么这个题用Dijkstra而不是SPFA”“为什么这个DP按这个维度定义状态”这才叫掌握。第三个层次才是挑战难题树状数组、线段树、树形DP、状态压缩DP、网络流等进阶内容这些更可能出现在复赛和决赛准备时也要投入更多时间。到这个阶段刷题已经不是重点重点是阅读题解、思考一题多解、参加线上高强度比赛来检验水平。对我个人来说CodeM 2017资格赛最大的收获不是名次而是通过几道贴近业务场景的算法题逼着自己把字符串处理、贪心、并查集这些基础算法重新刷了一遍。后来面试的时候好几个面试官问过类似“如果订单太多怎么调度”“怎么判断两个用户是否在同一个团购群里”的问题我几乎都能套上比赛里的建模思路。这也是我为什么建议不管是学生还是职场新人都去参加一次算法竞赛题目本身也许不能直接等于工作但它练的是建模和落地的能力这个能力在任何写代码的岗位上都能用上。