我至今记得第一次踏进机房赛场的感觉:桌上一个气球架、三个人挤一台机器、五个小时、一桌子打印出来的题面。开始的前二十分钟全场只有键盘声,等到有人拿到第一个气球,气氛才真正起来。ACM竞赛这个东西最容易被误解的地方在于,很多人以为它是"编程能力的考试",实际上它更接近一场在极度受限资源下做决策的团队游戏——三个人、一台电脑、五小时、十几道题,谁先做哪道、谁去卡题、谁负责验证,这些决策的质量往往比你会不会某个算法更能决定最后的名次。
这篇内容我按自己带队、参赛、赛后复盘的经验整理,覆盖四块:赛制规则怎么运转、这块牌子在不同路径上的实际分量、从零到拿牌的入门路线、以及训练与临场的一整套可复用手法。刚进队的新生可以照着当路线图用,已经在打的老队员更适合看训练体系和复盘那几节。里面涉及的工具链、参数、罚时计算、复杂度估算都给了具体数字,能直接抄作业。
1. 赛制规则拆解:先搞懂游戏规则再谈技术
规则不清楚就去刷题,是新人最常见的低效。ACM竞赛的规则设计其实非常精巧,每一条都在逼你做取舍,理解这些设计意图,你在赛场上的判断会完全不一样。
1.1 三人一机五小时:资源约束才是题目本身
标准赛制下,一支队伍三个人共享一台机器,比赛时长通常五小时,题目数量在八到十三道之间浮动。这个"一机"的限制是整套赛制的灵魂——它意味着队伍单位时间内能提交的代码量是有硬上限的,你的思维速度再快,也得排队上机。很多队伍赛前疯狂刷算法,赛后发现自己输在"三个人抢一台机器"上:一个人上机写代码,另外两个人干等着看题,机器空转率高得离谱。
合理的状态应该是机器几乎不空转。做法是让上机的人只负责"敲",思路和伪代码在纸上已经定好了;另一个人在旁边准备下一题的想法,随时可以接手;第三个人负责验证和构造边界数据。机器一旦闲下来超过五分钟,基本就是组织出了问题。
时长五小时也决定了节奏。前两小时是拉开差距的窗口,中段是卡题高发区,最后一小时封榜后是心理战。赛前就该把这三个阶段的目标定好:前两小时拿到几题、中段解决哪几道中等题、最后阶段留给哪道最有希望的难题。
注意:不要把五小时理解成"平均每题二十多分钟"。真实分布极度不均,一道签到题可能八分钟过,一道压轴题可能耗掉一个半小时还过不了。别用平均值规划时间。
1.2 判题结果与罚时:那二十分钟到底怎么算
判题是自动的,提交后系统用若干组测试数据跑你的程序,全部通过算正确(通常叫 AC),任意一组失败就是错误。错误类型很多,每种背后对应的排查方向完全不同,这张表值得背下来:
| 判题结果 | 含义 | 常见真实原因 |
|---|---|---|
| 通过 | 全部测试点正确 | — |
| 答案错误 | 输出与标准答案不符 | 逻辑漏洞、边界没处理、多组数据未清空 |
| 超时 | 运行时间超过限制 | 复杂度估错、常数过大、死循环 |
| 超内存 | 内存占用超限 | 数组开太大、递归层数过深 |
| 运行错误 | 程序异常终止 | 数组越界、除零、递归爆栈、空指针 |
| 编译错误 | 无法编译通过 | 头文件缺失、语法错误、提交语言选错 |
| 格式错误 | 内容对但格式不符 | 行末多余空格、缺换行 |
罚时的算法是新人最容易算错的部分。规则是:只有通过的题目才计入罚时,罚时 = 该题首次通过时的比赛分钟数 + 此前在该题上的错误提交次数 × 20 分钟。没通过的题不计罚时,但也不计入解题数。
举个具体的账:某场比赛,A 题在第 35 分钟一次通过,罚时 35;B 题在第 52 分钟和第 70 分钟各错一次,第 83 分钟通过,罚时 = 83 + 2×20 = 123。两题合计罚时 158 分钟。假设另一支队伍同样过了两题,用时分别是 40 和 90 分钟且零错误,罚时 130,排名就在你前面。
这个设计的意图非常明确:它惩罚的不是失败,而是"没想清楚就上机"。二十分钟的代价在五小时里相当于一题的思考时间,所以赛场上有一条铁律——不确定的代码不要交,先在纸上把边界手推一遍。
提示:赛前一定要和队友统一"提交前检查清单",比如多组数据是否清空、数组是否开够、是否会溢出。三个人都过一遍再提交,比错了再改划算得多。
1.3 赛制变体与赛程层级:别把不同比赛当成一回事
ACM 竞赛体系内部其实有几种不同的赛制,混淆了会吃大亏。最常见的是实时反馈制:提交后立刻知道结果,错了可以马上改,排名实时更新,罚时按上面那套算。另一种是按测试点给分制:每道题拆成若干子任务,每个子任务有独立分值,做不出来整题也能拿部分分,通常没有罚时,最后一次提交为准。还有一种是全封闭评测:比赛过程中看不到结果,结束后统一公布。
三种赛制的策略完全不同。实时反馈制下,错了继续交是常态,因为你能立刻知道方向对不对;按测试点给分制下,拿到部分分就够,不必死磕满分,而且要判断"最后一次提交为准"意味着不能乱交;全封闭评测下,必须自己构造数据验证,心理压力最大。
赛程层级上,通常是校内选拔、省级比赛、区域赛、更高级别的总决赛这样一条路径。区域赛是最核心的一环,名额有限,很多学校要通过校内赛和网络预选来分配。这里有个信息差:不同赛区的题目风格差异很大,有的偏重思维构造,有的偏重代码实现量,有的计算几何题特别多。赛前查一下目标赛区近几年的题目分布,针对性准备,性价比极高。
封榜规则也得提前知道。很多比赛在最后一段时间停止更新排名,只显示"某队在这段时间内提交过"。这意味着最后的排名和封榜时看到的可能完全不同——你看到的第 15 名,结束可能掉到 30 名开外。队伍在封榜后该不该赌一把难题,取决于你当前解出题数是否处于一个"卡在晋级线附近"的位置。
2. 含金量辨析:这块牌子在不同路径上值多少
"ACM 有没有用"这个问题在网上能吵几千楼,但大部分讨论都缺少前提条件。真正该问的是:在你打算走的这条路上,它在筛选环节里排第几权重。我按自己观察到的实际情况拆一下。
2.1 奖项层级的真实分布与区分度
先给个粗略的分层,方便你对号入座:
| 层级 | 大致含义 | 实际区分度 |
|---|---|---|
| 省级奖项 | 省内比赛获奖 | 入门凭证,证明你系统学过算法 |
| 区域赛铜牌 | 区域赛靠后名次 | 有明显加分,简历可写 |
| 区域赛银牌 | 中上名次 | 强信号,很多机会的门槛 |
| 区域赛金牌 | 前列名次 | 稀缺,基本能定向谈 |
| 更高级别决赛 | 极少数队伍 | 属于"硬通货"级别 |
关键在于区分度而不是"有没有奖"。省级奖项数量大、覆盖面广,在筛选环节的信息量有限;区域赛银牌以上,因为名额是固定的、靠排名决定的,含金量天然稳定。我见过不少人简历上写"某某竞赛获奖"但不说名次,这种写法在懂行的面试官眼里反而扣分。
还有一点很少有人提:同一块牌子在不同年份的难度是不一样的。题目难度、参赛队伍水平、晋级名额都会波动。所以看奖牌之外,更该看你在队里承担什么角色、解题贡献占比多少。这个在面试里是会被追问的。
2.2 三条出路上的实际反馈:保研、求职、科研
保研与升学方向:在多数高校的推免加分体系里,程序设计竞赛的奖项属于"学科竞赛"类别,具体加多少分要看本校的细则,差异非常大,有的学校给到很高权重,有的只算作参考。想走这条路,最该做的一件事是提前查清楚本校的加分文件和认定目录,看清楚哪些赛事、哪些层级被认可,别等到大四才发现自己打的比赛不在目录里。这一条我见过太多人栽在上面。
求职方向:技术岗位的笔试和面试环节,这套训练的直接收益极高。笔试基本就是简化版的算法题,训练过的选手在笔试通过率上有明显优势。面试里手写代码、分析复杂度、讨论边界条件,这些正是日常训练的内容。不过要提醒一句:竞赛能力强不等于工程能力强。能写出跑得快的算法,和能维护一个可读、可测试、可协作的代码库,是两套技能。我见过竞赛成绩很好但完全没接触过版本管理、单元测试、代码规范的同学,进公司后前几个月很吃力。
科研方向:算法竞赛训练带来的是建模能力和实现速度。做需要大量实验、要快速验证想法的方向时,这种"想到就能写出来"的能力非常值钱。但科研更看重问题定义、实验设计和写作,这些竞赛不教。把它当成加速器而不是通行证,心态会稳很多。
2.3 投入产出比的冷静计算
我把账算细一点。假设你从零基础到区域赛银牌,比较典型的投入是:入门阶段三到六个月,每天两到三小时;训练阶段一年以上,每周十到二十小时,加上寒暑假集训。累计大概一千到两千小时。这个投入量不小,需要诚实地问自己三件事:
一是你喜不喜欢这件事。这行有个残酷的现实:训练过程大部分时间是不爽的,卡题卡一整天、比赛被打崩、看着别人拿气球。如果不享受解题本身,纯靠意志力撑两年,很难撑到出成绩。
二是你有没有队友。这是团队项目,一个人的水平再高也打不了比赛。找到两个靠谱、能长期配合、水平接近的队友,比多刷两百道题重要得多。找不到人,这个投入的回报会大打折扣。
三是你想用它换什么。如果是换一份技术岗的敲门砖,投入八百小时可能就够了;如果是换保研加分,要看本校政策的具体规则;如果只是喜欢,那就不用算了,做喜欢的事不需要 ROI。
3. 入门路径:从语法到第一块牌子的实操路线
这部分我按时间线写,尽量给可执行的标准而不是空泛的建议。前提假设:你有基本的编程语法基础(学过一门语言的循环、数组、函数),能看懂英文题面。
3.1 语言与工具链选型:为什么主流是 C++
竞赛里的主流语言是 C++,原因很实在:执行效率高、标准库容器好用、模板和指针能省很多代码量。同样一道 n=1e6 的题,脚本语言可能因为常数太大直接超时,C++ 稳过。这不是语言优劣问题,纯粹是赛制对运行时间有硬限制,而 C++ 在这条约束下最省心。
工具链我推荐这套最小组合:
- 编译器:GCC 系列的 C++17 或 C++20,开启 -O2 优化。
- 本地环境:任意你顺手的编辑器或 IDE,别在环境上纠结太久。
- 调试手段:优先用打印调试,比断点调试在赛场上更实用,因为你最终要在没有图形界面的评测环境里定位问题。
- 版本管理:把自己的模板、常用算法实现、错题代码放进一个仓库,长期积累,这是你后续最值钱的资产。
具体到本地编译命令,我习惯这样:
g++ -O2 -std=c++17 -Wall -Wextra -o main main.cpp-Wall -Wextra会把未使用变量、有符号无符号比较、隐式类型转换这类隐患提前报出来,赛场上省你一次罚时。-O2一定要开,本地跑得快不代表评测快,但至少不会因为本地没开优化而误判复杂度。
下面这份快速输入模板,遇到输入量大的题(十万级以上)能显著降低超时风险:
#include <bits/stdc++.h> using namespace std; static char buf[1 << 20]; static int bufPos = 0, bufLen = 0; inline int readChar() { if (bufPos == bufLen) { bufLen = (int)fread(buf, 1, sizeof(buf), stdin); bufPos = 0; if (bufLen <= 0) return EOF; } return buf[bufPos++]; } inline long long readInt() { int c = readChar(); while (c != EOF && (c < '0' || c > '9') && c != '-') c = readChar(); int sign = 1; if (c == '-') { sign = -1; c = readChar(); } long long x = 0; while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = readChar(); } return x * sign; }提示:模板不要临时拼。赛前把自己常用的模板整理成一个文件,比赛中直接粘贴。但必须确保每一行你都理解,粘贴不懂的代码是罚时的头号来源。
3.2 前三个月训练路线:按周拆到可验收
入门阶段最大的问题是"不知道学什么顺序"。我按自己的经验拆成十二周,每周给一个可验收的标准,达标就往下走,不达标就补:
| 周次 | 核心内容 | 验收标准 |
|---|---|---|
| 1-2 | 输入输出、循环、数组、字符串、排序 | 独立完成十道基础题,不限时 |
| 3-4 | 枚举、模拟、简单贪心、前缀和 | 能在三十分钟内过一道中等模拟题 |
| 5-6 | 二分查找、双指针、简单 STL 容器 | 手写二分不出错,能判断"二分答案"场景 |
| 7-8 | 递归、简单动态规划(线性、背包) | 独立推出状态转移方程,不看题解 |
| 9-10 | 图的基本遍历、并查集、简单最短路 | 能默写三种最短路,知道各自适用条件 |
| 11 | 数论基础(取模、逆元、快速幂) | 会算组合数取模,知道溢出的边界 |
| 12 | 综合模拟赛 + 复盘 | 完整打完两场五小时比赛并写复盘 |
这份表里最关键的是第 7-8 周和第 12 周。动态规划是绝大多数人的第一个大坎——它不是一种算法,是一种思维方式,需要靠题量堆出直觉。而第 12 周的综合模拟,是把零散知识组装成"比赛能力"的关键环节,很多人刷了几百题但从不打完整比赛,上场完全不会分配时间。
入门阶段有个反直觉的建议:不要一开始就追求做题数量。前一百道题,每道都写完整思路、手工推边界、对照题解找差异,收益远高于囫囵吞枣做三百道。我见过刷题量很大但一遇变形题就懵的选手,根子就在这一步没做扎实。
3.3 组队与分工:比技术更难的部分
队伍分工一般有两种模式。一种是按题型分工:一人主攻图论和数据结构,一人主攻动态规划和数学,一人主攻字符串和计算几何。好处是深度够,坏处是遇到全场都是 DP 的比赛,另外两个人插不上手。另一种是按角色分工:一人主攻读题和思路(思维型),一人主攻实现(手速型),一人主攻验证和调错(细节型)。我倾向后者,因为赛场上真正的瓶颈往往不是"没人会这个算法",而是"没人能快速把这题读懂并定好方案"。
组队有三个坑必须提前避开:
第一个坑是水平差距过大。一个人明显强于另外两个,会出现"强者包揽所有题、弱者全程旁观"的局面,短期能出成绩,长期队伍会散。理想状态是三人实力接近但专长互补。
第二个坑是没有沟通规范。赛场上最常见的内耗是"两个人同时在推同一道题"。约定清楚:谁在读哪题、读到什么进度、什么时候放弃换人,这些必须形成默契。
第三个坑是训练不同步。队伍只在比赛前一周合练,磨合度基本为零。至少保证每周一次共同训练加一次复盘,长年累月才有默契。
注意:队伍里最好有一个"专职泼冷水"的人。看到一道题觉得思路很妙就冲上去写,十次有八次是错的。有人能在关键时刻说"先手推一遍样例",能救回不少罚时。
4. 训练体系:把刷题变成可复用的能力
刷题量和能力不是线性关系。同样做一千道题,有人能力曲线陡峭,有人平缓,差异全在训练方法上。这一节讲我验证过的几个做法。
4.1 专题模块划分与题量配比
按专题训练比随机刷题效率高得多,因为你能在短时间内密集接触同类问题的不同变形,形成模式识别。我的模块划分是这样的:
| 模块 | 核心知识点 | 建议题量 | 优先级 |
|---|---|---|---|
| 基础算法 | 枚举、模拟、贪心、二分、排序 | 60-80 | 最高 |
| 动态规划 | 线性、背包、区间、树形、状压 | 80-120 | 最高 |
| 图论 | 遍历、最短路、生成树、拓扑、连通性 | 50-70 | 高 |
| 数据结构 | 并查集、树状数组、线段树、单调栈队列 | 50-70 | 高 |
| 字符串 | 哈希、匹配、字典树、自动机 | 30-50 | 中 |
| 数学 | 数论、组合计数、博弈、矩阵快速幂 | 40-60 | 中 |
| 计算几何 | 点线面基础、凸包、扫描线 | 20-30 | 低 |
优先级一栏很关键。基础算法和动态规划是性价比最高的两部分,它们出现在绝大多数比赛的签到题和中档题里,拿下这两块,队伍的解题数下限就有了保障。计算几何投入产出比最低——题量少、实现量大、出错率高,除非你所在赛区特别爱考,否则不建议前期投入太多。
每个专题的训练节奏建议是:先看一遍知识框架,再做十道由易到难的题,然后回头整理模板和套路,最后做五道变形题检验。不要一上来就啃最难的,挫败感会摧毁节奏。
4.2 比赛复盘的正确姿势
复盘是训练里最容易被敷衍的环节。很多人复盘就是"看一遍题解,哦原来是这样,懂了,下一题"。这种做法几乎没收益,因为你获得的是"看懂"的错觉,不是"能独立写出来"的能力。
我用的复盘流程分四步:
第一步,重做没过的题,限时。不看题解,给出和比赛相同的时间上限,逼自己在压力下重新思考。很多时候你会发现,冷静下来后思路其实就在那儿,赛场上只是被时间焦虑压住了。
第二步,对比自己的思路和标准思路的差异点。差异通常分三类:完全不会(知识盲区)、方向对了但卡在细节(实现问题)、思路对但时间不够(熟练度问题)。三类问题的解决方案完全不同,混在一起就白复盘了。
第三步,归类记录。我维护一张表,记录每场比赛的失分点,格式大概是"题目特征 → 我应该想到什么 → 实际想到什么 → 断点在哪"。积累到几十条之后,你会发现自己反复栽在同样的几个地方,这些就是最该补的短板。
第四步,写出可复用的模板或结论。如果一道题的某个技巧在别的题里也能用,就把它抽象出来写成代码模板或者一句话结论,加进自己的知识库。这一步是复盘的真正产出。
4.3 训练数据记录与能力画像
我建议从开始训练就记录数据,字段不用多,但要坚持:
| 记录项 | 用途 |
|---|---|
| 每场训练赛的解题数、罚时、名次 | 看长期趋势,判断是否在进步 |
| 每题的状态(独立过/看题解过/没过) | 区分真实能力和虚假进度 |
| 卡题时长与放弃时机 | 校准临场决策 |
| 失分类型分布 | 找出最该补的模块 |
跑上两三个月,你会得到一张很清晰的能力画像:是思维速度慢、是实现手速慢、还是容易在细节上翻车。针对性补,效率能翻倍。我见过太多人凭感觉训练,"我觉得我图论弱",结果数据一看,真正拖后腿的是读题理解和边界处理。
4.4 复杂度估算:赛场上最该养成的肌肉记忆
这道题给的数据范围,直接决定了你能用什么算法。这条对应关系必须形成条件反射:
| 数据规模 n | 可用复杂度 | 典型算法 |
|---|---|---|
| n ≤ 10 | O(n!) | 全排列枚举 |
| n ≤ 20 | O(2^n) | 状压 DP、子集枚举 |
| n ≤ 100 | O(n^3) | Floyd、区间 DP |
| n ≤ 1000 | O(n^2) | 二维 DP、朴素匹配 |
| n ≤ 1e5 | O(n log n) | 排序、二分、线段树、堆 |
| n ≤ 1e6 | O(n) | 前缀和、双指针、单调栈 |
| n ≥ 1e8 | O(log n) 或 O(1) | 数学公式、快速幂 |
经验值是:一秒内大致能完成 1e8 到 3e8 次简单运算。所以 n=1e5 时,O(n log n) 大约 1.7e6 次操作,非常稳;O(n√n) 大约 3e7 次,在边缘,要小心常数;O(n²) 就是 1e10 次,必然超时。
提示:估算时记得乘上常数。一个 O(n log n) 的算法如果每次操作里有大量取模、容器操作或者内存随机访问,实际耗时可能是理论的五到十倍。当数据规模贴着你估算的上限时,宁可换个更优的写法。
5. 临场实战:比赛日的时间与心态管理
训练水平决定你的上限,临场表现决定你能拿到多少。我见过太多队伍训练成绩不错,正式比赛却打得一塌糊涂,问题几乎都出在流程上。
5.1 赛前准备:把能确定的事全部确定
比赛当天有一堆变量,你能做的就是把可控项全部固化下来。
提前一晚:检查证件、确认赛场位置和交通、把模板文件整理到一个目录、把常用编译命令和测试脚本放在触手可及的地方。队伍开一个十五分钟的短会,明确分工、约定读题顺序、确认谁负责计时。
开赛前十分钟:配置好编译环境,打开模板文件,做一个"环境自检"——写一个读入两个数输出和的小程序,编译、运行、确认输出正确。这一步能排除掉八成环境问题,比开赛后才发现编译器版本不对强得多。
物资准备:题面打印出来后需要纸笔演算,草稿纸、笔、水、能快速补充能量的食物(别带剥壳类的,浪费时间)。正式比赛可能不允许带任何印刷材料,模板要靠粘贴或者手打,赛前确认清楚规则,别到现场才发现模板带不进去。
注意:赛前半小时别再讨论难题了。让脑子保持放松,比多推一道压轴题有用。我见过队伍在赛前争论一道题的解法,吵到开赛后情绪还没平复,前四十分钟白白浪费。
5.2 开题顺序与读题分工:前二十分钟定生死
比赛一开始的正确做法是:三个人分开读不同的题,快速筛出可做的。具体操作是,开局先各自扫一遍前几道题(通常按难度大致递增排列,但并非绝对),用三到五分钟判断"这题我有没有思路"。
判断标准很朴素:读完题如果脑子里立刻浮现出"这大概是某某模型",标为可做;如果是"好像能做但不确定",标为观察;如果是"完全没头绪",先放着。筛完之后三个人碰一下,按"确定可做 + 实现量小"的顺序排。
这时候有个常见错误:所有人挤在签到题上。签到题往往是简单题,但简单不代表快,如果队里手速最快的人在写,另外两个人就该去读后面的题,而不是在旁边围观。围观是纯粹的浪费。
另一个错误是过早开难题。看到一道题觉得"这题做出来能拉开差距"就冲上去,结果卡一个小时,前面几道中等题没时间做。稳妥的策略是先把中档题扫干净,把解题数堆到一个安全位置,再考虑攻坚。
5.3 卡题处理与封榜冲刺
卡题是必然的,关键是设定止损点。我的经验规则是:一道题连续思考四十分钟没有任何进展,必须换人或者换题。换人的目的是引入新视角,因为卡住的人往往会陷入固定思维,越推越偏。
止损之后,卡住的题不要直接放弃,而是降级成"背景任务"——让一个人时不时回头看一眼,同时主力去做别的题。很多时候做完另一道题回来,思路突然就通了。
封榜之后的策略要看位置:
- 如果当前解题数处于晋级线之上且有富余,优先保稳,把手上最有把握的题做扎实,不要冒险交没验证的代码。
- 如果处于线附近,必须赌,选一道最接近做出来的题集中火力。
- 如果明显无望,那就当练手,尽量多交几道能过的题,锻炼队伍。
最后二十分钟有个细节:别在最后五分钟提交代码。系统可能拥堵,编译和判题会有延迟,你的提交可能来不及返回结果。至少留出十分钟余量。
再补一个实操工具——本地对拍。当你不确定自己的代码是否有边界问题时,写一个暴力程序和一个随机数据生成器,让两份代码互相对答案:
#!/bin/bash # 前提:gen.cpp 生成随机数据,std.cpp 是暴力解,my.cpp 是待测解 g++ -O2 -std=c++17 gen.cpp -o gen g++ -O2 -std=c++17 std.cpp -o std g++ -O2 -std=c++17 my.cpp -o my for ((i=1; i<=500; i++)); do ./gen "$i" > in.txt ./std < in.txt > out_std.txt ./my < in.txt > out_my.txt if ! diff -q out_std.txt out_my.txt > /dev/null; then echo "发现反例,测试编号: $i" cat in.txt break fi done这个脚本在赛场上救过我很多次。写完代码别急着交,跑两百组随机数据,比盯着代码看十分钟有用得多。生成器的设计有讲究:随机范围要覆盖小数据(n 小但数值大)、极端数据(全相同、全递增、全递减)、边界数据(n=1、n=最大值),三类混着来,命中率才高。
6. 常见问题与踩坑实录:那些让我付出罚时代价的地方
这一节都是实打实踩过的坑,很多在教材和文档里不会写,但赛场上出现频率极高。
6.1 高频问题速查表
| 现象 | 最可能的原因 | 排查动作 |
|---|---|---|
| 本地对、提交错 | 多组数据没清空全局变量 | 搜索所有全局数组和标记 |
| 大数据超时、小数据正常 | 复杂度估错 | 重算数据规模对应的复杂度 |
| 大数据错、小数据对 | 整数溢出 | 检查乘法是否用长整型 |
| 运行错误但找不到越界 | 递归层数过深爆栈 | 改迭代或检查递归终止条件 |
| 答案差 1 或差一点 | 边界条件处理错 | 手推 n=1、n=2 的情况 |
| 同一份代码重交又过了 | 未定义行为(越界读、未初始化) | 开启编译警告重新检查 |
| 输出格式对但报错 | 行末空格、缺换行 | 用 diff 比对输出文件 |
6.2 代码层面的血泪教训
多组数据清空是排名第一的罚时来源。一道题有多组测试数据(多组 case),全局数组、计数器、标记位如果不清空,第二组数据就崩了。我的做法是:写代码时把需要清空的东西列个清单写在旁边,交之前逐项核对。更彻底的做法是尽量不用全局变量,用完就丢,虽然写起来麻烦,但省心。
整数溢出排第二。两个 1e9 的数相乘,结果 1e18,超出 32 位范围,用 int 就是错的。养成习惯:只要涉及乘法、累加,先想最大值会不会溢出。常见场景是求路径长度、计数方案数、面积计算。
浮点数比较是个隐形杀手。判断两个浮点数相等不要用==,要设一个误差范围,比如差的绝对值小于 1e-8 算相等。涉及几何计算时,误差范围还要根据数据规模调整,我一般用 1e-9 起步。
输出用endl会超时。这个坑我栽过不止一次。endl每次都会刷新缓冲区,输出量大的时候(十万行以上)会严重拖慢速度。用\n代替,需要最后统一刷新时用一次cout.flush()。
递归深度。深度优先搜索在数据规模上万时可能直接爆栈。本地环境栈空间可能比评测环境大,本地跑得动不代表评测能过。稳妥做法是数据规模大时改成显式栈的迭代写法。
模板的隐形错误。从别处抄来的模板,参数含义、边界处理可能和你以为的不一样。我用过一次二分模板,它在区间缩小到两个元素时会死循环,我盯了半小时没发现,最后手推才找到。任何模板,用之前必须自己手推一遍边界。
6.3 队伍协作层面的坑
沉默的卡题。有人卡住了不说,一个人闷头推四十分钟,等别人发现的时候已经浪费了大量时间。约定一个机制:卡题超过二十分钟必须开口说一句"我在这题上卡住了,谁帮我看看"。
抢机器。两个人同时觉得自己的题更急,抢同一台电脑。解决办法是提前约定优先级规则,比如"谁的题更接近完成谁上"。
复盘时的情绪化。比赛输了之后复盘很容易变成互相指责。有效的做法是对事不对人,只讨论"这个决策在当时的条件下是否合理",而不是"你为什么这么蠢"。队伍能长期走下去,靠的是信任。
7. 我个人在这条路上的一些体会
练到后面我越来越觉得,ACM 竞赛真正训练出来的能力有三样:在信息不完整的情况下快速做判断、在压力下保持代码的准确性、以及和另外两个人高效协作。这三样东西在任何技术工作里都用得上,而且很难通过别的方式高效获得。
如果让我给刚入门的同学一句建议,那就是:先把流程跑通,再谈水平提升。很多人在技术细节里打转,却没搞明白比赛的节奏是怎么走的、队伍该怎么配合、复盘该怎么做。把这些"软"的东西理顺,你会发现同样的技术水平能多拿半块牌子。
最后再分享一个我自己坚持了很多年的小习惯:每场比赛结束后,不管成绩好坏,写三句话——这场做对了什么、做错了什么、下一场要改什么。三句话,不多写,但每场都写。攒到几十场之后回头看,进步轨迹清清楚楚,比任何复盘模板都好用。