2017年那场CodeM初赛B轮我现在还记得自己提交最后一道题时手都在抖。倒不是怕超时而是前面一道题卡了太久剩下的时间能不能把这道题调通全看接下来十分钟。那一阵算法圈子里到处都在聊CodeM美团办的编程大赛初赛分了好几轮线上赛B轮就是其中一轮。报名不设门槛在校学生和在职工程师都能打奖品除了现金还有校招终面直通卡对当时刚工作没两年的我来说这些都不重要重要的是我想知道自己在真正的限时比赛里能排到什么位置。我之前在A轮栽过一次资格赛过得很轻松结果A轮正赛上来就傻了眼——两道题完全没思路最后排名惨不忍睹。所以B轮对我来说更像是重考心态反而放松了不少。也正是这种放松让我看清了自己在算法题上的真实水平。1. 为什么我会选B轮以及赛前的准备1.1 先弄清楚赛制再报名我记得当时CodeM的初赛分为好几轮线上赛选手可以在不同轮次中重复参赛取最好成绩作为晋级依据。A轮、B轮这样的命名方式意味着官方给了选手多个考试窗口哪怕A轮发挥失常B轮还有一次补救机会。我当时选择B轮除了A轮已经考砸了之外还有一个心理上的考量B轮的时间更靠后意味着我有多一点时间准备。A轮结束后网上会有一些讨论虽然题目不一样但通过讨论能大致感受到出题风格和难度分布。我后来复盘发现这个判断对了一半——B轮的题目和A轮在风格上确实有相似之处比如都偏向于考察基础算法的灵活运用而不是堆砌冷门数据结构但难度并没有因为多给几天准备时间就降低该卡的题照样卡。所以如果你打算参加类似的编程大赛我的第一个建议是不要把希望寄托在下一轮会更简单上而是要把每一轮都当成最后一次机会来准备。1.2 我不是来裸考的赛前模板与工具链A轮失败的一个重要原因是我在准备上太随意了。资格赛的题目简单让我误以为B轮也不过如此。后来才发现比赛这种场景和平时刷LeetCode完全不同时间压力、心理压力、还有对代码熟练度的要求都比日常高出一个量级。B轮前一周我专门整理了一份自己的竞赛模板库按功能模块分类把常用的算法代码提前写好并验证过。不是为了抄而是为了在比赛时减少从零开始敲的时间成本。我的模板库大概包含这些模块基础工具快读快写、常数优化、long long的封装数据结构并查集带路径压缩和按秩合并、树状数组、线段树区间加/区间查、单调栈、单调队列图论Dijkstra堆优化、SPFA、Kruskal、Tarjan 求强连通分量字符串KMP、字符串哈希、字典树数学快速幂、扩展欧几里得、组合数取模预处理阶乘和逆元现在回头看这份模板库帮我在B轮省下了大约二十分钟的编码时间。不要小看这二十分钟在三个小时左右的比赛里二十分钟可能就决定了一道题能不能写完。我还做了一件事把所有模板在本地编译环境中跑了一遍确保没有语法错误或隐藏的编译警告。这个习惯我至今保留任何代码只要是要在比赛或面试现场用的必须提前编译通过。2. 比赛当天的真实节奏2.1 前30分钟先扫题再动手比赛开始后我没有立刻往编辑器里敲代码而是先把所有题目都看了一遍。这个习惯来自一次惨痛的教训——A轮时我直接扑向第一题结果第一题比想象中难白白耗掉了一个小时后面几道简单题反而没时间做。扫题的过程大约花了十五分钟。我把每道题的题面、数据范围、以及初步想法记在草稿纸上。这里有一个关键点数据范围往往决定了算法选型。看到n 10^5基本意味着要设计O(n log n)甚至O(n)的算法看到n 10^3可以考虑O(n^2)的枚举看到n 20那大概率是状态压缩DP或暴搜。那场B轮我扫了一遍题目在心里大致排了个序两道比较简单的题可以快速写掉一道中等难度的题需要仔细推一下状态转移最后一道题当时看完全没思路先放一放。2.2 中段推进一道题卡住时的取舍前两道简单题大概用了四十分钟写完并交掉一次通过心里踏实了不少。但到了第三道题我卡住了。卡住的原因很典型拿到题第一反应觉得是贪心写出来交上去WA以为边界条件没处理对检查了半天再交还WA换个思路改成动态规划推了二十分钟公式发现状态定义有问题。就这样来回折腾了快四十分钟提交记录洋洋洒洒五发没有一发过。当时我的下意识反应是继续死磕因为已经投入了这么多时间现在放弃等于前功尽弃。但我强迫自己停下来去接了杯水做了个决定先做最后一道题即使那道题看起来很难也要至少写出暴力解法拿部分分。等我再回头处理第三题时心态已经平静多了反而很快发现了一个之前的盲区。这个经验我想多说一句比赛中最贵的不是时间而是心态。当你在一道题上连续失败三次以上你的状态会肉眼可见地变差判断力也会下降。这时候最有效的操作是物理上离开——去洗手间、接杯水、甚至只是站起来活动一下让大脑换个状态。2.3 最后1小时从能过到过得更快最后一道题我先写了暴力解法能拿多少分算多少分。这个策略非常务实因为竞赛OJ通常会根据数据规模分档给分即使只过了部分测试点也总比零分强。写完暴力之后还剩大约四十分钟。我回头继续看第三题这次我换了个角度重新读了一遍题面才发现自己对题意的理解从一开始就错了——我把它当成了一类已知的题型但题目里有一个细节完全被忽略了。修正理解之后状态转移方程很快就写出来提交AC。最后剩下的时间我用来做代码体检检查已提交的代码有没有潜在风险数组开得够不够大有没有可能下标越界int相乘会不会溢出需不需要long long有没有忘记处理边界情况比如n0、n1有没有多余的输出干扰OJ的校验这是我个人的习惯宁可提前交卷也不在最后一分钟改代码。比赛结束前五分钟我只检查不修改因为改崩一个已AC题目的风险远大于优化一点常数的收益。3. 复盘B轮里让我印象最深的几道题3.1 一道看着像贪心其实是DP的任务调度题这道题的大意是给定若干个任务每个任务有一个起始时间、结束时间和收益你同一时刻只能做一个任务问最多能获得多少收益。第一反应是经典的区间调度贪心按结束时间排序然后每次选结束时间最早且不冲突的任务。写完交上去WA。后来读题仔细看才发现任务收益不是固定的正数而是可正可负且不同任务的收益差异很大。贪心只能处理每个任务权重一致的简化版一旦引入不同的权重就必须用动态规划。这道题的状态设计其实很经典将所有任务按结束时间排序定义dp[i]为前 i 个任务能获得的最大收益对于第 i 个任务有两种选择不做收益就是dp[i-1]做找到结束时间不超过第 i 个任务开始时间的前一个任务记为p收益就是dp[p] weight[i]核心是快速找到p。由于任务已经按结束时间排序了可以用二分查找整体复杂度O(n log n)。#include bits/stdc.h using namespace std; struct Task { int start, end, weight; }; int main() { int n; cin n; vectorTask tasks(n 1); for (int i 1; i n; i) { cin tasks[i].start tasks[i].end tasks[i].weight; } sort(tasks.begin() 1, tasks.end(), [](const Task a, const Task b) { return a.end b.end; }); vectorint dp(n 1, 0); vectorint p(n 1, 0); for (int i 1; i n; i) { int lo 0, hi i - 1, ans 0; while (lo hi) { int mid (lo hi) / 2; if (tasks[mid].end tasks[i].start) { ans mid; lo mid 1; } else { hi mid - 1; } } p[i] ans; } for (int i 1; i n; i) { dp[i] max(dp[i - 1], dp[p[i]] tasks[i].weight); } cout dp[n] endl; return 0; }这道题给我的教训是看清题面里每一个条件尤其是描述目标函数的那句话。很多题看起来是某类经典问题的变体实际上只是换了几个条件解法就完全不同了。3.2 一道考察离线处理与树状数组的区间题这道题的时间有点久了但思路至今记得很清楚给一个数组多次询问某个区间内有多少对元素满足两数之和等于给定值 k。当时我的第一反应是莫队算法。但现场很快意识到莫队的复杂度虽然也能过可写起来比较复杂而且调试成本高。后来我换了一个思路——离线处理 树状数组。核心想法是这样的把问题看成对于每个右端点维护左端点的贡献。从左到右扫描数组每扫描到一个新的位置 i就找出之前所有满足a[j] a[i] k的 j并在树状数组的位置 j 上加 1。这样当查询区间[L, R]时只需在扫描到右端点 R 时查询树状数组上[L, R]的区间和即可。为了做到这一点需要把所有查询按右端点排序在扫描数组的过程中不断回答查询。struct Query { int l, r, id; // 按 r 从小到大排序 }; vectorint bit(n 1, 0); void add(int idx, int val) { for (; idx n; idx idx -idx) bit[idx] val; } int sum(int idx) { int res 0; for (; idx 0; idx - idx -idx) res bit[idx]; return res; } int rangeSum(int l, int r) { return sum(r) - sum(l - 1); }实际编码时关键在于怎么快速找到所有满足a[j] a[i] k的 j。如果直接用unordered_map存每个值的位置集合就能在扫描到a[i]时去a[j] k - a[i]的位置列表里把所有位置全部取出并在树状数组上加 1。但要注意一点每个位置只应该在它作为右侧元素时被添加一次所以随着扫描推进之前的位置会被重复添加多次。仔细想想这里其实不需要去重因为我们求的是区间内有多少对每一对会在扫描到右侧端点时被添加一次正好符合要求。这道题让我意识到竞赛里考察的核心能力之一是把一个看似复杂的查询问题转化为可以在线的、用数据结构维护的增量问题。离线处理和双指针这类打乱顺序但保持正确性的技巧比单纯背模板重要得多。3.3 一道不算难但极考验细心的字符串题这道题本身不难但我错了两次才过错的不是算法而是细节。题面大致是给定一个原始字符串和一个目标字符串允许对一个子串循环左移若干次问能否得到目标字符串。思路很直接把原始字符串复制一份接到自己后面然后判断目标字符串是否是它的子串。这就是标准的字符串匹配问题用find或 KMP 都能解决。我第一次WA是因为没考虑移动次数可以为0的情况也就是原始字符串本身就和目标字符串相等时应该输出是但在代码里多了一个不必要的处理分支把正确答案覆盖掉了。第二次WA更有意思——我用了unordered_setstring来存所有可能的循环移位结果然后直接查找目标字符串。对小数据没问题但题目的n可能到10^5把所有移位串都存进来内存直接爆了。后来改用 KMP 的线性匹配才过。bool isSubstring(string haystack, string needle) { if (needle.size() haystack.size()) return false; // KMP 匹配 vectorint pi(needle.size(), 0); for (int i 1; i needle.size(); i) { int j pi[i - 1]; while (j 0 needle[i] ! needle[j]) j pi[j - 1]; if (needle[i] needle[j]) j; pi[i] j; } int j 0; for (int i 0; i haystack.size(); i) { while (j 0 haystack[i] ! needle[j]) j pi[j - 1]; if (haystack[i] needle[j]) j; if (j needle.size()) return true; } return false; }这道题的失误让我总结出一个习惯每次写完代码先花30秒检查一遍边界条件。包括n0、两个输入相同、输入全部相同字符、最大值输入等这些极端情况。很多WA不是因为思路错而是因为边界漏了。4. 那些我踩过的坑和后来总结的应对方法4.1 输入输出格式在OJ上被cin坑过的都懂以前我在LeetCode上刷题习惯了用cin/cout因为数据量小影响不大。但到了CodeM这种竞赛场景数据量动不动就是10^510^6输入输出速度就变成了一个隐形杀手。B轮有一道题我用cin配ios::sync_with_stdio(false)加cin.tie(nullptr)勉强过了。但我见过不少人在大数据的题上直接用cin不关同步流结果TLE一道本来能过的题白白丢了分。如果你现在还在用cin我的建议是在竞赛中直接统一用scanf/printf或者自啃一个快速读入模板。这不仅是速度问题也让你少一个临场切换的思考负担。inline int readInt() { int x 0, f 1; char c getchar(); while (c 0 || c 9) { if (c -) f -1; c getchar(); } while (c 0 c 9) { x x * 10 c - 0; c getchar(); } return x * f; }4.2 数据范围不开long long见祖宗那道任务的题如果收益最大不超过10^4任务数不超过10^5加起来最多10^9用int刚好够。但题面并没有直接说明单个收益的上限我默认了int结果计算dp[p[i]] tasks[i].weight时直接溢出成了负数答案错得离谱。从那以后我做题时会刻意做一个动作读题时把每一个数字变量的取值范围抄到草稿纸上然后先算一遍可能的最大值估算会不会溢出。如果题目没说就往大了估用long long永远不嫌多。4.3 时间分配不要把鸡蛋放在同一道题上我在前面说过B轮中段我卡在第三题上半小时以上。事后想起这件事虽然有惊无险但代价很大。如果最后一道题不是暴力能拿到部分分的题型我可能就栽了。后来我给自己的比赛定了一条铁律一道题如果连续提交了三发错误且20分钟内没有新的思路就强制换题。换题不是放弃而是让大脑从惯性思维中抽离出来。等做完其他题再回头看往往会有原来如此的感觉。这条铁律在后面的比赛和工作中救了我很多次。4.4 心态管理提前预演失败场景比赛时最怕的不是不会而是本来会但是慌得写不出来。我后来想到一个办法在赛前训练时故意给自己制造一点逆境——比如规定自己只用一个小时完成原本两个小时的训练赛或者先做最难的题把简单的留在后面。这样到了真实比赛即使遇到不顺也不会因为这不是我熟悉的节奏而慌乱。5. 赛后复盘B轮带给我的改变5.1 从比赛暴露出的短板B轮结束之后我没有马上去看排名先冷静地做了一份自我体检。最明显的问题是我在动态规划上的熟练度不够。那场比赛中任务调度那道题如果我对区间DP和排序后DP的套路足够敏感应该能在第一次尝试时就写对状态转移方程而不是在贪心思路上浪费好几发提交。这个问题也直接影响了我后来刷题的方向——我用了整整两周时间集中刷了各种DP题型从入门到进阶包括背包、区间、树形、状压不带任何选择地做。等再回到CodeM复赛时我对DP的敏感度已经有了明显的提升。第二个问题是我在数据结构题上的应变能力偏弱。区间查询那题莫队算法我虽然没有精熟但也不是不能写但现场我还是选择了想一个更巧妙的做法结果差点把自己绕进去。实际上比赛现场用自己最熟悉的算法是最稳妥的策略追求想起来更优雅的解往往会浪费时间。我现在更倾向于建议参赛选手算法库不在多在于对每个算法都能做到拿出来就能写的程度。5.2 给打算参加下一届CodeM的朋友们的参考答案要说那届B轮给我留下什么最有价值的东西其实是两句话第一比赛是一场工程化能力的考试不只是算法知识的考试。你怎么管理时间、怎么应对突发状况、怎么在压力下保持代码整洁这些能力在比赛中体现得淋漓尽致也和真实的工作场景非常像。那些真正的竞赛选手从来不只靠脑子快更靠日复一日养成的工程习惯。第二赛后复盘比比赛本身重要。我在A轮失利之后如果只是叹息运气不好而不去准备B轮那B轮大概率还是同样的结局。但当我真的静下心去整理模板库、研究自己的错误代码、总结了一套时间分配策略后B轮的结果就有了肉眼可见的变化。这种从教训中提炼出可执行方案的能力才是参加任何竞赛型活动最大的收获。如果你现在正准备参加下一届CodeM或者任何类似的编程大赛我想给你一份直接的参考答案赛前整理一份自己的模板库并确保所有模板都编译通过报名后做至少一次完整的限时模拟赛完全按照比赛的时间和规则来比赛开始前先扫读全部题目排一个做题顺序清单遇到卡题别恋战先拿能拿的分数赛后把每一道题的思路和代码都重新整理一遍哪怕做对了也要看有没有更优解法保持规律的训练节奏但不要为了刷题而刷题每一个问题都要想清楚为什么CodeM 2017美团编程大赛初赛B轮对我而言不只是一场比赛它像一面镜子让我能看到自己在算法、心态和工程习惯上的真实差距。后来每年看到美团编程大赛的消息我都会想起那个下午——手在键盘上微微发抖心率比平时快了一截却觉得特别充实。如果你也在犹豫要不要报名一场比赛我的建议只有一个去报名去把第一道题AC掉后面的路自然就打开了。
2017年那场CodeM初赛B轮我现在还记得自己提交最后一道题时手都在抖。倒不是怕超时而是前面一道题卡了太久剩下的时间能不能把这道题调通全看接下来十分钟。那一阵算法圈子里到处都在聊CodeM美团办的编程大赛初赛分了好几轮线上赛B轮就是其中一轮。报名不设门槛在校学生和在职工程师都能打奖品除了现金还有校招终面直通卡对当时刚工作没两年的我来说这些都不重要重要的是我想知道自己在真正的限时比赛里能排到什么位置。我之前在A轮栽过一次资格赛过得很轻松结果A轮正赛上来就傻了眼——两道题完全没思路最后排名惨不忍睹。所以B轮对我来说更像是重考心态反而放松了不少。也正是这种放松让我看清了自己在算法题上的真实水平。1. 为什么我会选B轮以及赛前的准备1.1 先弄清楚赛制再报名我记得当时CodeM的初赛分为好几轮线上赛选手可以在不同轮次中重复参赛取最好成绩作为晋级依据。A轮、B轮这样的命名方式意味着官方给了选手多个考试窗口哪怕A轮发挥失常B轮还有一次补救机会。我当时选择B轮除了A轮已经考砸了之外还有一个心理上的考量B轮的时间更靠后意味着我有多一点时间准备。A轮结束后网上会有一些讨论虽然题目不一样但通过讨论能大致感受到出题风格和难度分布。我后来复盘发现这个判断对了一半——B轮的题目和A轮在风格上确实有相似之处比如都偏向于考察基础算法的灵活运用而不是堆砌冷门数据结构但难度并没有因为多给几天准备时间就降低该卡的题照样卡。所以如果你打算参加类似的编程大赛我的第一个建议是不要把希望寄托在下一轮会更简单上而是要把每一轮都当成最后一次机会来准备。1.2 我不是来裸考的赛前模板与工具链A轮失败的一个重要原因是我在准备上太随意了。资格赛的题目简单让我误以为B轮也不过如此。后来才发现比赛这种场景和平时刷LeetCode完全不同时间压力、心理压力、还有对代码熟练度的要求都比日常高出一个量级。B轮前一周我专门整理了一份自己的竞赛模板库按功能模块分类把常用的算法代码提前写好并验证过。不是为了抄而是为了在比赛时减少从零开始敲的时间成本。我的模板库大概包含这些模块基础工具快读快写、常数优化、long long的封装数据结构并查集带路径压缩和按秩合并、树状数组、线段树区间加/区间查、单调栈、单调队列图论Dijkstra堆优化、SPFA、Kruskal、Tarjan 求强连通分量字符串KMP、字符串哈希、字典树数学快速幂、扩展欧几里得、组合数取模预处理阶乘和逆元现在回头看这份模板库帮我在B轮省下了大约二十分钟的编码时间。不要小看这二十分钟在三个小时左右的比赛里二十分钟可能就决定了一道题能不能写完。我还做了一件事把所有模板在本地编译环境中跑了一遍确保没有语法错误或隐藏的编译警告。这个习惯我至今保留任何代码只要是要在比赛或面试现场用的必须提前编译通过。2. 比赛当天的真实节奏2.1 前30分钟先扫题再动手比赛开始后我没有立刻往编辑器里敲代码而是先把所有题目都看了一遍。这个习惯来自一次惨痛的教训——A轮时我直接扑向第一题结果第一题比想象中难白白耗掉了一个小时后面几道简单题反而没时间做。扫题的过程大约花了十五分钟。我把每道题的题面、数据范围、以及初步想法记在草稿纸上。这里有一个关键点数据范围往往决定了算法选型。看到n 10^5基本意味着要设计O(n log n)甚至O(n)的算法看到n 10^3可以考虑O(n^2)的枚举看到n 20那大概率是状态压缩DP或暴搜。那场B轮我扫了一遍题目在心里大致排了个序两道比较简单的题可以快速写掉一道中等难度的题需要仔细推一下状态转移最后一道题当时看完全没思路先放一放。2.2 中段推进一道题卡住时的取舍前两道简单题大概用了四十分钟写完并交掉一次通过心里踏实了不少。但到了第三道题我卡住了。卡住的原因很典型拿到题第一反应觉得是贪心写出来交上去WA以为边界条件没处理对检查了半天再交还WA换个思路改成动态规划推了二十分钟公式发现状态定义有问题。就这样来回折腾了快四十分钟提交记录洋洋洒洒五发没有一发过。当时我的下意识反应是继续死磕因为已经投入了这么多时间现在放弃等于前功尽弃。但我强迫自己停下来去接了杯水做了个决定先做最后一道题即使那道题看起来很难也要至少写出暴力解法拿部分分。等我再回头处理第三题时心态已经平静多了反而很快发现了一个之前的盲区。这个经验我想多说一句比赛中最贵的不是时间而是心态。当你在一道题上连续失败三次以上你的状态会肉眼可见地变差判断力也会下降。这时候最有效的操作是物理上离开——去洗手间、接杯水、甚至只是站起来活动一下让大脑换个状态。2.3 最后1小时从能过到过得更快最后一道题我先写了暴力解法能拿多少分算多少分。这个策略非常务实因为竞赛OJ通常会根据数据规模分档给分即使只过了部分测试点也总比零分强。写完暴力之后还剩大约四十分钟。我回头继续看第三题这次我换了个角度重新读了一遍题面才发现自己对题意的理解从一开始就错了——我把它当成了一类已知的题型但题目里有一个细节完全被忽略了。修正理解之后状态转移方程很快就写出来提交AC。最后剩下的时间我用来做代码体检检查已提交的代码有没有潜在风险数组开得够不够大有没有可能下标越界int相乘会不会溢出需不需要long long有没有忘记处理边界情况比如n0、n1有没有多余的输出干扰OJ的校验这是我个人的习惯宁可提前交卷也不在最后一分钟改代码。比赛结束前五分钟我只检查不修改因为改崩一个已AC题目的风险远大于优化一点常数的收益。3. 复盘B轮里让我印象最深的几道题3.1 一道看着像贪心其实是DP的任务调度题这道题的大意是给定若干个任务每个任务有一个起始时间、结束时间和收益你同一时刻只能做一个任务问最多能获得多少收益。第一反应是经典的区间调度贪心按结束时间排序然后每次选结束时间最早且不冲突的任务。写完交上去WA。后来读题仔细看才发现任务收益不是固定的正数而是可正可负且不同任务的收益差异很大。贪心只能处理每个任务权重一致的简化版一旦引入不同的权重就必须用动态规划。这道题的状态设计其实很经典将所有任务按结束时间排序定义dp[i]为前 i 个任务能获得的最大收益对于第 i 个任务有两种选择不做收益就是dp[i-1]做找到结束时间不超过第 i 个任务开始时间的前一个任务记为p收益就是dp[p] weight[i]核心是快速找到p。由于任务已经按结束时间排序了可以用二分查找整体复杂度O(n log n)。#include bits/stdc.h using namespace std; struct Task { int start, end, weight; }; int main() { int n; cin n; vectorTask tasks(n 1); for (int i 1; i n; i) { cin tasks[i].start tasks[i].end tasks[i].weight; } sort(tasks.begin() 1, tasks.end(), [](const Task a, const Task b) { return a.end b.end; }); vectorint dp(n 1, 0); vectorint p(n 1, 0); for (int i 1; i n; i) { int lo 0, hi i - 1, ans 0; while (lo hi) { int mid (lo hi) / 2; if (tasks[mid].end tasks[i].start) { ans mid; lo mid 1; } else { hi mid - 1; } } p[i] ans; } for (int i 1; i n; i) { dp[i] max(dp[i - 1], dp[p[i]] tasks[i].weight); } cout dp[n] endl; return 0; }这道题给我的教训是看清题面里每一个条件尤其是描述目标函数的那句话。很多题看起来是某类经典问题的变体实际上只是换了几个条件解法就完全不同了。3.2 一道考察离线处理与树状数组的区间题这道题的时间有点久了但思路至今记得很清楚给一个数组多次询问某个区间内有多少对元素满足两数之和等于给定值 k。当时我的第一反应是莫队算法。但现场很快意识到莫队的复杂度虽然也能过可写起来比较复杂而且调试成本高。后来我换了一个思路——离线处理 树状数组。核心想法是这样的把问题看成对于每个右端点维护左端点的贡献。从左到右扫描数组每扫描到一个新的位置 i就找出之前所有满足a[j] a[i] k的 j并在树状数组的位置 j 上加 1。这样当查询区间[L, R]时只需在扫描到右端点 R 时查询树状数组上[L, R]的区间和即可。为了做到这一点需要把所有查询按右端点排序在扫描数组的过程中不断回答查询。struct Query { int l, r, id; // 按 r 从小到大排序 }; vectorint bit(n 1, 0); void add(int idx, int val) { for (; idx n; idx idx -idx) bit[idx] val; } int sum(int idx) { int res 0; for (; idx 0; idx - idx -idx) res bit[idx]; return res; } int rangeSum(int l, int r) { return sum(r) - sum(l - 1); }实际编码时关键在于怎么快速找到所有满足a[j] a[i] k的 j。如果直接用unordered_map存每个值的位置集合就能在扫描到a[i]时去a[j] k - a[i]的位置列表里把所有位置全部取出并在树状数组上加 1。但要注意一点每个位置只应该在它作为右侧元素时被添加一次所以随着扫描推进之前的位置会被重复添加多次。仔细想想这里其实不需要去重因为我们求的是区间内有多少对每一对会在扫描到右侧端点时被添加一次正好符合要求。这道题让我意识到竞赛里考察的核心能力之一是把一个看似复杂的查询问题转化为可以在线的、用数据结构维护的增量问题。离线处理和双指针这类打乱顺序但保持正确性的技巧比单纯背模板重要得多。3.3 一道不算难但极考验细心的字符串题这道题本身不难但我错了两次才过错的不是算法而是细节。题面大致是给定一个原始字符串和一个目标字符串允许对一个子串循环左移若干次问能否得到目标字符串。思路很直接把原始字符串复制一份接到自己后面然后判断目标字符串是否是它的子串。这就是标准的字符串匹配问题用find或 KMP 都能解决。我第一次WA是因为没考虑移动次数可以为0的情况也就是原始字符串本身就和目标字符串相等时应该输出是但在代码里多了一个不必要的处理分支把正确答案覆盖掉了。第二次WA更有意思——我用了unordered_setstring来存所有可能的循环移位结果然后直接查找目标字符串。对小数据没问题但题目的n可能到10^5把所有移位串都存进来内存直接爆了。后来改用 KMP 的线性匹配才过。bool isSubstring(string haystack, string needle) { if (needle.size() haystack.size()) return false; // KMP 匹配 vectorint pi(needle.size(), 0); for (int i 1; i needle.size(); i) { int j pi[i - 1]; while (j 0 needle[i] ! needle[j]) j pi[j - 1]; if (needle[i] needle[j]) j; pi[i] j; } int j 0; for (int i 0; i haystack.size(); i) { while (j 0 haystack[i] ! needle[j]) j pi[j - 1]; if (haystack[i] needle[j]) j; if (j needle.size()) return true; } return false; }这道题的失误让我总结出一个习惯每次写完代码先花30秒检查一遍边界条件。包括n0、两个输入相同、输入全部相同字符、最大值输入等这些极端情况。很多WA不是因为思路错而是因为边界漏了。4. 那些我踩过的坑和后来总结的应对方法4.1 输入输出格式在OJ上被cin坑过的都懂以前我在LeetCode上刷题习惯了用cin/cout因为数据量小影响不大。但到了CodeM这种竞赛场景数据量动不动就是10^510^6输入输出速度就变成了一个隐形杀手。B轮有一道题我用cin配ios::sync_with_stdio(false)加cin.tie(nullptr)勉强过了。但我见过不少人在大数据的题上直接用cin不关同步流结果TLE一道本来能过的题白白丢了分。如果你现在还在用cin我的建议是在竞赛中直接统一用scanf/printf或者自啃一个快速读入模板。这不仅是速度问题也让你少一个临场切换的思考负担。inline int readInt() { int x 0, f 1; char c getchar(); while (c 0 || c 9) { if (c -) f -1; c getchar(); } while (c 0 c 9) { x x * 10 c - 0; c getchar(); } return x * f; }4.2 数据范围不开long long见祖宗那道任务的题如果收益最大不超过10^4任务数不超过10^5加起来最多10^9用int刚好够。但题面并没有直接说明单个收益的上限我默认了int结果计算dp[p[i]] tasks[i].weight时直接溢出成了负数答案错得离谱。从那以后我做题时会刻意做一个动作读题时把每一个数字变量的取值范围抄到草稿纸上然后先算一遍可能的最大值估算会不会溢出。如果题目没说就往大了估用long long永远不嫌多。4.3 时间分配不要把鸡蛋放在同一道题上我在前面说过B轮中段我卡在第三题上半小时以上。事后想起这件事虽然有惊无险但代价很大。如果最后一道题不是暴力能拿到部分分的题型我可能就栽了。后来我给自己的比赛定了一条铁律一道题如果连续提交了三发错误且20分钟内没有新的思路就强制换题。换题不是放弃而是让大脑从惯性思维中抽离出来。等做完其他题再回头看往往会有原来如此的感觉。这条铁律在后面的比赛和工作中救了我很多次。4.4 心态管理提前预演失败场景比赛时最怕的不是不会而是本来会但是慌得写不出来。我后来想到一个办法在赛前训练时故意给自己制造一点逆境——比如规定自己只用一个小时完成原本两个小时的训练赛或者先做最难的题把简单的留在后面。这样到了真实比赛即使遇到不顺也不会因为这不是我熟悉的节奏而慌乱。5. 赛后复盘B轮带给我的改变5.1 从比赛暴露出的短板B轮结束之后我没有马上去看排名先冷静地做了一份自我体检。最明显的问题是我在动态规划上的熟练度不够。那场比赛中任务调度那道题如果我对区间DP和排序后DP的套路足够敏感应该能在第一次尝试时就写对状态转移方程而不是在贪心思路上浪费好几发提交。这个问题也直接影响了我后来刷题的方向——我用了整整两周时间集中刷了各种DP题型从入门到进阶包括背包、区间、树形、状压不带任何选择地做。等再回到CodeM复赛时我对DP的敏感度已经有了明显的提升。第二个问题是我在数据结构题上的应变能力偏弱。区间查询那题莫队算法我虽然没有精熟但也不是不能写但现场我还是选择了想一个更巧妙的做法结果差点把自己绕进去。实际上比赛现场用自己最熟悉的算法是最稳妥的策略追求想起来更优雅的解往往会浪费时间。我现在更倾向于建议参赛选手算法库不在多在于对每个算法都能做到拿出来就能写的程度。5.2 给打算参加下一届CodeM的朋友们的参考答案要说那届B轮给我留下什么最有价值的东西其实是两句话第一比赛是一场工程化能力的考试不只是算法知识的考试。你怎么管理时间、怎么应对突发状况、怎么在压力下保持代码整洁这些能力在比赛中体现得淋漓尽致也和真实的工作场景非常像。那些真正的竞赛选手从来不只靠脑子快更靠日复一日养成的工程习惯。第二赛后复盘比比赛本身重要。我在A轮失利之后如果只是叹息运气不好而不去准备B轮那B轮大概率还是同样的结局。但当我真的静下心去整理模板库、研究自己的错误代码、总结了一套时间分配策略后B轮的结果就有了肉眼可见的变化。这种从教训中提炼出可执行方案的能力才是参加任何竞赛型活动最大的收获。如果你现在正准备参加下一届CodeM或者任何类似的编程大赛我想给你一份直接的参考答案赛前整理一份自己的模板库并确保所有模板都编译通过报名后做至少一次完整的限时模拟赛完全按照比赛的时间和规则来比赛开始前先扫读全部题目排一个做题顺序清单遇到卡题别恋战先拿能拿的分数赛后把每一道题的思路和代码都重新整理一遍哪怕做对了也要看有没有更优解法保持规律的训练节奏但不要为了刷题而刷题每一个问题都要想清楚为什么CodeM 2017美团编程大赛初赛B轮对我而言不只是一场比赛它像一面镜子让我能看到自己在算法、心态和工程习惯上的真实差距。后来每年看到美团编程大赛的消息我都会想起那个下午——手在键盘上微微发抖心率比平时快了一截却觉得特别充实。如果你也在犹豫要不要报名一场比赛我的建议只有一个去报名去把第一道题AC掉后面的路自然就打开了。
