算法与数学基础 · 第 8 期 · 本季收官

算法竞赛思维：OI 选手怎么想

读题 → 估复杂度 → 定算法 → AC · competitive thinking

OI 选手拿到题不是直接写代码，而是先估复杂度：n=10⁵ 时 O(n²)=10¹⁰ 必超时，得换 O(n log n)。前 7 期讲了工具，这期讲怎么用——从看到题到 AC 的完整思维流程。
⏱ 约 11 分钟 🎯 想参加算法竞赛的人 📦 源：OI-wiki · 竞赛思维

01一个反共识：竞赛不是比谁会写，是比谁会估

新手拿到题就动手写，老手先看数据范围。数据范围决定了能用什么复杂度，复杂度决定了能用什么算法——这一步走对，题目就过了一半。

n ≤ 10⁵ → O(n log n) · n ≤ 20 → O(2ⁿ) · n ≤ 5000 → O(n²)

1 秒时限大约能跑 10⁸ 次操作。n=10⁵ 时 O(n²)=10¹⁰，超时 100 倍；O(n log n)≈1.7×10⁶，绰绰有余。先估复杂度再选算法，是竞赛选手和业余选手的分水岭。估错了，代码再漂亮也是 0 分。

先估复杂度，
再写代码。
灏天文库 · 算法与数学基础 P.44

02竞赛题型闯关：从读题到定算法

下面是三道典型竞赛题，每题给你数据范围，让你选合适的算法复杂度。选对进下一关，看你能拿几分。

🏁 竞赛题型闯关
看数据范围，选对算法复杂度，模拟 OI 选手的判断流程。
得分：0 / 3

03OI 选手的完整思维流程

步骤一

读题三遍

第一遍懂题意，第二遍找边界，第三遍想反例。读错题是竞赛第一大杀手。

步骤二

估复杂度

看数据范围反推可用复杂度，再据此筛选算法。先排除超时的。

步骤三

定算法 + 验证

选算法后手算小例子，确认逻辑无误，再动手写。

步骤四

写码 + 调边界

边界（n=0、n=1、最大值）最易错，单独测一遍再交。

这个流程的核心是先想后写。业余选手 80% 时间在写代码、20% 在调试；OI 选手反过来，80% 时间在想、20% 在写——想清楚了，代码一次就对。竞赛比的是判断力，不是手速。这套思维迁移到工程上也成立：先设计再实现，比边写边改高效十倍。

先想清楚，
再动手写。
灏天文库 · 算法与数学基础 P.46

04带走这套清单

✅ 竞赛思维 5 条可执行规则

  1. 先看数据范围估复杂度：10⁵ 用 O(n log n)，20 用 O(2ⁿ)，别用错量级。
  2. 读题三遍：懂题意、找边界、想反例，少一次都容易翻车。
  3. 定算法后手算小例子验证，别直接交，错逻辑比错代码难发现。
  4. 边界单独测：n=0、n=1、最大值、负数，这些是 WA 的高发区。
  5. 先想后写：80% 时间在想，20% 在写，比边写边改高效十倍。
竞赛比的是判断，
不是手速。
灏天文库 · 算法与数学基础 P.47