OI 训练指南Informatics Olympiad

训练路线

四个阶段,把分数从「能过」拉到「稳过」

每个阶段只回答三个问题:要补什么、练多少、什么标准才允许进入下一阶段。 时间按每周 10–15 小时估计,进度可以压缩,但不要跳阶段——省选的题全都建立在前面阶段的模型之上。

阶段 0

自查

1–2 周

先把「我以为我会」变成「确实能默写」。这一步看起来浪费时间,实际能省掉后面几个月的瞎刷。

  • 过一遍专题页「应当已经会」的清单,逐项限时 5 分钟默写
  • 拿两套近年真题,限时整套做完,逐题记录卡点
  • 把卡点按出现频率排序,前三个就是这一轮的主攻方向

进入标准:能明确说出自己最弱的三个专题,而不是「感觉哪儿都不会」。

阶段 1

补硬伤

1–2 个月

目标是「没有硬伤」:常规提高题读完能立刻说出归类,模板能默写,不再因为不会某个基础结构卡住整场。

  • 图论建模:最短路三种写法、最小生成树、拓扑排序、差分约束
  • 树上问题:LCA(倍增 / 欧拉序)、dfs 序、树形 DP 基本形态
  • DP 四类:区间、树形、状压、数位,能写出状态与转移
  • 数据结构:树状数组、线段树(含懒标记)、ST 表、带权并查集
  • 字符串:哈希(双哈希 / 随机底数)、KMP;数论:快速幂、线性筛、逆元、组合数取模

进入标准:提高- 难度的题,限时 60 分钟能独立写出正解,或至少拿到一半以上部分分。

阶段 2

专题深入

3–6 个月

从「会用模板」到「知道什么时候用、为什么是对的」。这一阶段决定你是省一,还是止步于 CSP-S 一等。

  • DP 优化:单调队列、决策单调性、线段树优化转移,能判断该用哪个
  • 进阶图论:分层图、拆点、二分图匹配、最小割建模
  • 树上技巧:树链剖分、换根 DP、dfs 序 + 数据结构
  • 构造与思维:手玩小数据找性质、特判、随机化的正确用法
  • 暴力艺术:按子任务分档写暴力、剪枝、对拍、卡时

进入标准:CSP-S 提高组模拟赛(300 分制)稳定 200 分以上,且每场都能说出扣分原因。

阶段 3

冲刺

赛前 3–6 个月

这一阶段不学新东西。只做三件事:限时模拟、按年份成套刷真题、把考场动作固定成肌肉记忆。

  • 每周 2 场以上限时模拟,严格 3 小时、不查资料、赛后立刻复盘
  • 专门练「5 分钟内判断该写暴力还是冲正解」,并写成自己的决策规则
  • 模板压缩到 5 分钟能默写:快读、并查集、线段树、最短路、LCA
  • 固定时间分配:读题 10 分钟 → 先写最稳的暴力 → 再攻能拿分的部分分 → 最后冲正解

进入标准:连续三场模拟赛分数波动不超过 30 分,且没有一次因读题、越界、溢出丢分。

选题

难度选错,练什么都白费

用「独立思考后能否做出」来衡量,而不是题目的难度标签。标签在不同题库里并不可比。

通过率 70% 以上

太简单。可以拿来做模板热身,但不要用它打发时间——连续一周只做这类题,水平不会动。

通过率 40–60%

正好。需要认真想、可能需要看一次题解才能打通,但第二天能独立重写出来。

通过率 30% 以下

除非它是某个专题的首批题,否则先放。硬啃超出能力的题,通常只收获挫败感而不是方法。

复盘

一场模拟赛的四步复盘

不复盘的模拟赛,价值接近零。分数只是结果,卡点才是收获。

  1. 赛后 0–1 小时

    写卡点日志

    每道没做出来的题记一句话:卡在第几分钟、当时在犹豫什么。趁记忆新鲜,这一步最值钱。

  2. 赛后 24 小时内

    限时重做

    不看题解、不看自己旧代码,重新限时写一遍。写不出来的,才是真正的漏洞;写得出来但很慢的,是需要练熟练度的。

  3. 当天

    归因分类

    把失分归到三类:模型不认识、认识但写不对、写对但超时。三类对应的训练完全不同,混在一起就无法制定计划。

  4. 三天后

    裸题重做

    只看题面、不看任何旧代码再写一遍。这一遍能过,这道题才算真的拿下了。

规则

三种赛制,策略完全不同

赛制 反馈 计分 这个水平该用的策略
OI 赛制
CSP、NOIP、NOI
赛后出分 测试点得分,部分分有效 先估分再动笔:暴力保底 → 写部分分 → 冲正解;绝不留空白题
ACM / ICPC
多数高校组队赛
实时返回 过题数优先,罚时次之 读题手与实现手分工,先清简单题;一次写对,罚时就是排名
IOI 赛制
IOI、部分线上赛
子任务实时得分 按子任务累计 按子任务分档推进,先拿稳的档位,别在最后一档上把时间耗光

清单

提交前 60 秒:正确性与性能各查一遍

这个水平的失分,八成不来自「不会」,而来自「知道怎么做却写挂了」。

正确性

  • 数据范围逐个核对,数组是否按上界 +1 开
  • 该 long long 的地方是否漏了(乘法、前缀和、边权累加)
  • 边界:n=1、空图、重边自环、全等元素
  • 多组数据是否清空(尤其邻接表与桶)
  • 递归深度是否会爆栈(10⁵ 级的一条链)

性能

  • 复杂度与限制匹配:10⁸ 次简单运算约 1 秒,带常数要打折
  • 卡常手段是否用上:快读、关闭同步、避免 vector 高频扩容
  • 大数据是否本地跑过一遍计时,别只看小样例
  • -fsanitize=address,undefined 本地查过越界与溢出
  • 暴力对拍过至少 50 组随机小数据

继续:按专题查缺补漏 → 或 找题源和工具 →