2020年那个格外漫长的暑假我和队友几乎每周都要雷打不动地打一场线上赛多校联合训练赛Multi-University Training Contest。主办高校把十道左右的题挂上OJ来自各校的队伍在五个小时里同场竞技没有奖金、没有证书但暑期集训的队伍几乎没有缺席的。它的定位很明确拿比正式区域赛更锋利的题把队伍从会做题磨到会比赛。这篇东西不打算复述某道题的具体做法而是想把我对赛制理解、赛前准备、场上节奏和赛后复盘的一整套经验写下来。适合今年刚组队、准备打区域赛的同学也适合已经打过一两场、但总觉得每场都打得乱糟糟的中间队伍。1. 先搞清楚多校联合训练赛到底在练什么1.1 五小时、十道题一个比区域赛还恶的赛制多校赛的赛制大家应该都熟按程序设计竞赛通用的排名规则来过题数优先罚时少的排前面。每道题每次错误提交加20分钟罚时比赛时长通常在4到5小时题目数量在10道上下。区别在于正式区域赛往往会有几道送分题让大部分队伍都能体面地过掉三四题多校赛不跟你讲这个客气出题人来自各个高校题目风格五花八门有的题连签到都要搭上一个不算小的观察。我把这个特点称为恶。但恶得有价值如果你的目标是区域赛拿牌那么暑假里被多校赛虐几个星期比你在自己OJ上刷一百道水题有用得多。因为它模拟了真实的比赛压力——五个小时内你要在做不出来和必须做出来之间反复横跳这种心理上的训练是单刷题目完全给不了的。具体到排名逻辑队伍在比赛期间能看到实时榜单。我建议大家至少每半小时看一次榜不是为了焦虑而是为了判断哪些题应该被做出来。一道题如果有大量队伍过了而你们一点思路都没有那多半不是题目太难而是你们读题或者入手方向有问题。这是多校赛最珍贵的信息它会直接告诉你当前的位置和问题。1.2 三梯度难度分布别把所有题都当难题以我这几年的观察多校赛一场十道题的难度大致可以分成三档。梯度题量预估过题队数常见形态签到/热身1~2道150简单观察、模拟、直接套模板中期主力4~6道50~120需要一到两个经典算法叠加压轴难题2~4道30以下多个知识点混合常常带构造/交互/码量巨长理解这个分布的意义在于排兵布阵。签到题是要抢的中期题是要磨的压轴题是要赌的。如果你把一个人长时间丢在压轴题上导致中期题没人推进这场比赛的整体收益就会非常低。多校赛的排名不是靠某个人的爆发而是靠三个人对这道题到底该不该现在做有共识。另外多校赛还有一个特点题面有时候会给得很绕样例很小你需要从样例反推题意。我遇到过不止一次三个人各读各的读完发现理解完全不一样。所以我的建议是任何一个人觉得题意有点怪的题读完后花三十秒把题目复述给另一个人听这个成本很低但能避免后面几十上百分钟的无效思考。1.3 什么水平的人适合来打经常有同学问我我们队是不是太菜了多校赛会不会纯被虐我的回答是只要你有三个人、有打区域赛的打算就该来。多校赛不设门槛成绩好坏本来就没有任何实际奖惩它就是一个训练载体。如果你还在犹豫我给你一个更具体的标准队伍三个人里至少要有人在暑假前能在模拟赛中独立过掉中等难度题如果暂时达不到可以两个人、甚至一个人开虚拟赛把十道题按顺序当限时训练做。别因为过题数少而不好意思——我见过第一年每场只过一两题的队伍一年后进圈拿牌的大有人在。多校赛的真正价值不在当场排名在于它提供了一个固定节奏、高真实感的训练环境。2. 赛前准备模板、分工和磨刀2.1 队伍分工按算法方向切不要按写代码习惯切很多队伍有个误区让代码写得快的人主写、慢的人主想。但多校赛五小时十道题的模式下瓶颈往往不是打字速度而是某个方向没人能接住。我的建议是按算法领域切一个人负责图论与网络流、匹配类一个人负责动态规划、计算几何和字符串一个人负责数论与数据结构。这样任何一道题出来至少有一人能顺着熟悉的套路快速给出初版解法。当然领域之间有大量交叉比如树链剖分既算数据结构也算图论网络流建模经常用到DP思路。所以分工不是垄断负责方向的人先给思路其他人负责查漏补缺和出测试样例。实际操作中我们三人会约定谁先读完题谁先口头报这题用什么模型、复杂度多少、能不能做三十秒内报不出来就换人。还有一个建议全程固定一个人操作键盘不太现实五个小时手会累。我们队的方法是谁最熟悉当前这题的实现细节谁上键盘另外两个人负责盯常见错误和构造反例。刚开始可能会乱多打两场就会形成默契。2.2 模板库该带什么、该扔什么多校赛允许带纸质/离线材料所以一份趁手的模板库比临时现推算法重要得多。我整理模板的原则是只放你真正写过并验证过的代码不放从网上复制但没跑过的代码。比赛里最坑的不是没有模板而是模板有bug你还拿它交了然后WA到怀疑人生。下面是我个人比较看重的模板清单类别必带内容备注基础快读快写、输入输出优化多校赛数据量大的题很多数论素数筛、扩展欧几里得、逆元、CRT、莫比乌斯反演组合计数题占比高字符串KMP、AC自动机、后缀数组/后缀自动机至少要会用一种数据结构线段树、树状数组、Treap/Splay、可持久化线段树线段树应用场景最广图论最短路、最小生成树、Dinic、费用流、强连通/割点网络流模板一页纸就够DP优化斜率优化、四边形不等式、状压/数位DP骨架别带太冷门的计算几何凸包、半平面交、旋转卡壳基础这类题出现频率不稳定但出现就是大分以及一个示例快读代码多校赛这种数据量大的题很常用#include cstdio inline int read() { int x 0; char c getchar(); while (c 0 || c 9) c getchar(); for (; c 0 c 9; c getchar()) x x * 10 (c - 0); return x; }模板库不需要追求面面俱到。比如带个仙人掌DP之类一年用不到一次的东西不如把空间留给那些你知道有这个东西、但细节总是记不全的算法。每个人情况不同模板库应该是你私人知识的压缩包而不是某个大佬的全集。2.3 真正被忽略的赛前准备环境与手感赛前一周我会做三件事。第一确认编译环境和语言标准。不同OJ的编译器和标准库版本可能有差异提前用一个小的提交测试一下bits/stdc.h、std::random、__int128这些到底能不能用否则比赛时代码写得很high一编译就报错的滋味非常难受。第二确认栈空间和递归深度。多校赛出题人不会手软动不动就是百万级的DFS/递归如果你的环境默认栈只有几MB递归写深了直接段错误。应对方式是提前准备好非递归写法或者把递归转成BFS/迭代。第三赛前两三天打一场热身虚拟赛哪怕只做简单题目的是让眼睛和手都进入比赛状态。多校赛周期长、强度大状态调整和心理准备同样是训练的一部分。这跟体力无关纯粹是让你在正式五小时里不被首小时的手生浪费掉。3. 场上五小时的节奏前30分钟、中段与下半场3.1 开局前30分钟抢签到不是拼手速是拼读题顺序比赛开始后最忌讳的一件事是三个人同时埋头看同一道题。正确姿势是把前六道题按题号拆开每人读两题两分钟内口头汇报每题的题意、数据范围和初步方向。汇报完优先做题意最清晰、解法最直接的那道题而不是感觉最难的。签到题的共同特征是数据范围不大、样例能直接验证、解法通常在15分钟内能写完。如果读完两道题都没有这种感觉不要慌翻到后面的题看看。多校赛有时会把真正的签到题放到中后位置我就见过一道全场几百人过的题被放在第八题的位置很多队伍从头顺序扫白白错过了黄金时间。另外前30分钟的输出要克制。签到题只值一个提交不值得为了抢首A连续提交错误版本。多校赛的罚时规则比较狠一个错误提交20分钟两三个错误就会让你从榜首掉到中游。我的经验是哪怕慢三分钟提交也要保证第一发是经过两三个样例验证的版本。3.2 中段卡题你先要判断是题难还是我们笨比赛进行到一两个小时大概率会遇到某道题写了很久过不了。经验不足的队伍会一直硬磕结果磕掉一个小时还是WA。我的判断标准是先看一眼这道题当前的过题队数。如果同场100队过了你们卡住那九成是思路或者细节实现的问题这种时候应该立刻拉人一起看而不是一个人钻牛角尖。拉人看也有次序先让另一个人独立读一遍你的代码重点查边界条件数组越界类型溢出这三类问题如果代码没问题再回去重新审视算法本身。我见过太多队伍把代码里一个等于号写错当成思路不对来重做白白浪费半小时。还有一种性价比很高的做法写一个暴力枚举的小程序给算法打对拍。多校赛很多题的答案规模都很小暴力程序跑小数据跟你的复杂算法对比几分钟就能定位错误。这招在字符串题、数据结构题上特别管用属于看似笨、实际快的排错法。3.3 下半场压轴题、罚时和止损的艺术比赛进入最后两小时场上会出现一个分水岭强队在攻坚压轴弱队在纠结要不要再交一次。我最想强调的是止损——你最后一个小时的产出决定了你这场练得值不值。止损规则很简单如果一道题你们已经连续做了两个小时没有任何阶段性进展那么就需要暂停。暂停不意味着放弃而是把视角从做换成想再读一遍题确认没有漏掉关键条件和队友复述一遍当前思路听听哪里听起来不对劲。很多时候问题出在一开始就理解错了题意这种错不是靠拗能拗对的。罚时方面最后阶段不要抱着赌一把的心态提交没有把握的代码。如果排名相近一个WA带来的惩罚比你想的大。但反过来如果你有一个明显能过小数据的算法只是担心大数据超时那么提交一次拿个反馈信息也是合理的——多校赛允许你在交之前先确认复杂度而不是干等到比赛结束。4. 比排名更重要的赛后补题与复盘4.1 补题的优先级先救差一点做出来的题赛后第一件事不是看排名是趁热记录赛场上每道题的状态然后按优先级安排补题全场过题人数很多、但你们没过的题——这通常是应该会但不会的题补起来性价比最高。你们想了很久、思路大半正确但没调出来的题——这种题只要把最后一段坎补上进步是立竿见影的。涉及你们薄弱方向的压轴难题——放在最后能补多少算多少。有人喜欢一口气把十道题全补完我觉得没必要。补题的目的是把你从不会变成会而不是刷完题单。每场补两三道反思到位比泛泛地看一遍题解强得多。看题解也有讲究先自己想十五分钟想不出来再瞄一眼题解的关键词然后合上题解继续写。直接抄代码是最低效的补题方式。4.2 复盘笔记怎么记才能在区域赛前用上我的复盘笔记不是题目题解式的收藏夹而是每道题记四件事关键观察这题最妙的那个点在哪里、算法模型是变成了最短路还是变成了DP、踩坑记录当时卡住的原因、一句话总结以后看到这类题要先想什么。这四件事合在一起比贴一长段AC代码有用十倍因为你上场时不可能翻题解你能依靠的只有这种压缩过的认知。每个轮次打完后我还习惯写一个更粗粒度的小结本场我们最大的问题是读题、代码细节还是团队分工分别赢在哪里、输在哪里这些小结我会按周排列开学期末翻一遍就能看到自己从签到都慌到稳定做中档题的变化这种反馈本身也是一种动力。4.3 用整轮数据给自己的队伍做体检多校赛一个暑假那么多轮是天然的采样数据。我建议队伍里固定一个人做统计每轮过了几题、每个方向的题在场上有没有推出来、错误提交主要来自哪些情况。不用复杂一张表格就够轮次过题数中档题完成率主要WA来源卡住最久的题第1轮42/5少考虑边界图论建模第2轮53/5类型溢出数论DP连续统计四五轮之后你们的短板会非常清晰。比如发现字符串题一到场上就卡那好接下来两周的训练就往字符串方向倾斜。多校赛的题目质量高、方向全通过它来发现短板比你自己凭感觉看书刷题要客观得多。5. 几件被反复踩的小事希望你别再踩5.1 快读之外编译环境、栈空间和能跑就行我在前面提过环境检查但这里还是想单独拎一个细节很多同学只在本地IDE里测过上了OJ才发现自己的代码依赖了本地特有的头文件或宏。多校赛每题提交次数有限真的经不起这种折腾。所以赛前一定要先在那个OJ上用一道简单题把环境跑通确认基本输入输出、long long、__int128如果支持都正常。另外递归深度大的题尽量写成迭代别赌OJ的栈大小我们队伍曾在一个树形DP题上因为递归爆栈而三个人轮流改错四十分钟最后才发现是栈的问题。5.2 模运算和类型溢出看起来对的代码最危险多校赛的计数题特别爱出答案对某模数取模的题这种题错误来源很固定加法取模没考虑负数、乘法忘了转long long、int之间的比较溢出。我提供一个基本够用的写法模板int add(int a, int b, int mod) { int s a b; if (s mod) s - mod; return s; } long long mul_mod(long long a, long long b, long long mod) { return a * b % mod; // 已经保证 a,b mod乘积在 long long 范围内 }限制条件值得仔细读如果模数在1e9级别a*b大概1e18long long能撑住如果模数到了1e18就得用倍增乘法或者__int128。很多WA不是题目思路难是这种基础函数的边界没处理好。我自己的习惯是凡是说不定会溢出的运算一律用long long凡是说不定会负数的取模先加模再取模宁可慢一点也不想在赛场上debug半天。5.3 团队沟通是场上最容易被低估的罚时来源最后想聊一个特别容易被忽略的问题沟通。多校赛里队友之间我以为他懂了他没告诉我他已经放弃导致的时间浪费我见过太多太多。我们队后来立了三条规矩第一一个人报思路时必须说清楚数据范围、时间复杂度、关键数据结构三个信息第二谁负责哪道题就在聊天框里打一句话让另外两个人知道避免同时开两道题然后互相等第三任何一个人对当前进度感到不确定必须立刻说出来禁止一个人闷头做。这三条规矩不复杂但它在五个小时的高压环境里非常管用。比赛打到第四小时的时候人的判断力会下降沟通也会变得烦躁这时候规矩能兜住你。我记得有一次我们三个人用了半小时争论一道题用不用建树最后发现是因为其中两个人读到的数据范围不一样——一个人看漏了限制条件。从那以后先复述题意再讨论成了我们队雷打不动的流程。这个小习惯算是我打多校赛收获最大的一件事。