第 7.2 章：解题策略

会算法不等于会比赛。真正的 USACO 能力，是在一题从未见过的情况下，仍然能有条理地完成以下动作：

1. 读懂题意。
2. 抽象模型。
3. 根据约束判断复杂度。
4. 选择可能的算法。
5. 先写可验证的版本。
6. 调试并提交。
7. 赛后复盘。

本章给你一套可以直接在比赛中使用的流程。它不保证你每题都会，但能显著减少“脑子一片空白”和“明明会却写挂”的情况。

7.2.1 一道题的完整处理流程

下图概括了竞赛解题流程：

把它拆成实际动作，就是下面 8 步。

Step 1：读目标

先回答一句话：

这题最终要我输出什么？

常见目标包括：

• 最大值或最小值。
• 满足条件的数量。
• 是否可行。
• 最短步数。
• 任意一个合法构造。
• 每个询问的答案。

如果这句话说不清楚，不要写代码。

Step 2：读输入对象

把故事翻译成数据结构：

Step 3：读约束

约束决定你可以使用什么复杂度。

快速判断：

Step 4：手算样例

不要只看样例输入输出。你要能解释：

• 为什么样例答案是这个？
• 每一步中间状态是什么？
• 如果把样例改小一点，答案如何变化？

Step 5：先想暴力

每道题都先问：最直接的做法是什么？

暴力解的价值有三点：

• 可能已经足够通过 Bronze。
• 可以拿小数据部分分。
• 可以作为对拍的正确基准。

Step 6：优化瓶颈

找到暴力慢在哪里：

Step 7：写前先列边界

在代码旁边写下要测的情况：

• N = 1。
• 所有值相同。
• 已经满足条件。
• 完全不满足条件。
• 最大值。
• 空图或不连通图。
• 区间刚好接触。

Step 8：实现、测试、提交

先写清晰版本，不要过早追求短代码。通过样例后，再测自造边界。若时间允许，用暴力对拍。

7.2.2 算法识别：从约束到方法

问题一：能不能直接模拟

如果题目只是让你按规则执行，且操作次数不大，直接模拟通常最稳。

但要小心：如果 T 很大，例如 (10^9)，朴素模拟会超时。这时要考虑：

• 是否存在循环？
• 是否能用数学公式跳过？
• 是否能把多次操作合并？

问题二：能不能枚举

枚举是 Bronze 的核心能力。关键是枚举对象要选对。

优秀的枚举题常常不是完全不能暴力，而是要找到合适的暴力维度。

问题三：是否有图或网格

如果对象之间有连接关系，立刻考虑图。

网格题也可以看作图：每个格子是点，相邻格子之间有边。

问题四：是否有区间或前缀

出现区间和、连续段、矩形区域时，优先考虑：

• 一维前缀和。
• 二维前缀和。
• 差分数组。
• 滑动窗口。
• 排序后区间合并。

问题五：是否有单调性

如果题目问：

• 最大化最小值。
• 最小化最大值。
• 至少能否达到 X。
• 最多能否控制在 X。

通常可以考虑 二分答案。

二分答案的关键是定义：

check(x) = 是否能做到答案至少/至多为 x

并证明 check(x) 随 x 单调。

问题六：是否有最优子结构

若一个最优解可以由更小问题的最优解转移而来，考虑 DP。

常见信号：

• “最大/最小代价”。
• “方案数”。
• “从前 i 个中选择”。
• “走到第 i 个位置”。
• “状态由上一步决定”。

DP 的核心不是套模板，而是定义状态：

dp[i] = 处理到第 i 个对象时的最优答案

或：

dp[i][j] = 到达状态 (i, j) 的最优答案/方案数

7.2.3 算法决策树

当你不知道从哪开始时，可以按下面顺序问自己：

1. N 是否很小？
   ├─ N ≤ 8：试全排列
   ├─ N ≤ 20：试子集枚举 / 状压
   └─ 否：继续

2. 题目是否是图或网格？
   ├─ 最短步数：BFS
   ├─ 连通性：DFS / BFS / DSU
   ├─ 有权最短路：Dijkstra
   └─ 树结构：DFS / 树形 DP

3. 是否有区间、连续段、范围查询？
   ├─ 区间和：前缀和
   ├─ 多次区间修改：差分
   ├─ 连续窗口：双指针 / 滑动窗口
   └─ 区间重叠：排序 + 扫描

4. 是否在有序结构中查找？
   ├─ 找位置：二分查找
   ├─ 最大化最小值：二分答案
   └─ 找最近元素：排序 + lower_bound

5. 是否是最优决策序列？
   ├─ 有重叠子问题：DP
   ├─ 局部选择可证明：贪心
   └─ 状态很少：BFS 状态搜索

6. 都不像？
   ├─ 试小例子找规律
   ├─ 找不变量
   ├─ 重新表述题目
   └─ 可能是 Ad Hoc

教练提醒： 决策树不是绝对规则，而是帮助你在紧张时不乱。真正比赛中，一题可能同时用到排序 + 前缀和 + 二分答案。

7.2.4 部分分策略

不会满分时，目标不是放弃，而是寻找能稳定通过的子任务。

常见部分分方案

小数据暴力模板思维

如果 N ≤ 20，考虑子集：

for (int mask = 0; mask < (1 << n); mask++) {
    // check subset
}

如果 N ≤ 8，考虑排列：

sort(a.begin(), a.end());
do {
    // check permutation
} while (next_permutation(a.begin(), a.end()));

如果 N ≤ 1000，很多 O(N²) 做法都值得一试。

比赛中如何提交部分分

1. 先保证代码对样例正确。
2. 对不支持的大数据也要输出合法格式，不能崩溃。
3. 在时间允许时，逐步扩展更多情况。
4. 每次较大修改前，保存或保留上一版思路。

7.2.5 测试方法

样例测试不够

样例只验证最基本理解，不能覆盖所有边界。

你应该主动构造测试。

边界测试清单

对拍：最强调试工具

对拍适用于：你有一个暴力解和一个优化解，但不确定优化解是否正确。

工作流程：

1. 写 brute.cpp：小数据正确暴力。
2. 写 sol.cpp：你的优化解。
3. 写 gen.py 或 gen.cpp：随机生成小数据。
4. 多次运行并比较输出。

for i in {1..1000}; do
    python3 gen.py > test.in
    ./brute < test.in > expected.out
    ./sol < test.in > got.out
    if ! diff -q expected.out got.out > /dev/null; then
        echo "Wrong answer on test $i"
        cat test.in
        echo "Expected:"
        cat expected.out
        echo "Got:"
        cat got.out
        break
    fi
done

对拍尤其适合排序、贪心、DP、图论中容易漏边界的题。

7.2.6 调试方法

用 cerr 而不是 cout

cout 是答案输出，调试信息会污染评测结果。调试时用 cerr。

cerr << "i = " << i << ", value = " << a[i] << "\n";

用 assert 检查不变量

assert(0 <= r && r < n);
assert(0 <= c && c < m);
assert(dist[v] == -1 || dist[v] == dist[u] + 1);

如果断言失败，说明程序某处违反了你认为一定成立的条件。

开启编译警告

g++ -std=c++17 -Wall -Wextra sol.cpp -o sol

认真读 warning。很多 warning 对应真实 bug。

使用地址消毒器

g++ -std=c++17 -g -fsanitize=address,undefined sol.cpp -o sol

它能发现：

• 数组越界。
• 使用未定义行为。
• 某些整数溢出。
• 访问无效内存。

缩小失败样例

如果某个大测试错了，不要盲目盯代码。尝试删掉输入中的元素，直到得到一个仍然错误的最小样例。越小的反例越容易看出问题。

7.2.7 常见思维误区

误区一：一上来就写代码

如果你没有完整思路，代码只会把混乱固化下来。至少先写出：

• 状态是什么。
• 转移或操作是什么。
• 复杂度是多少。
• 边界是什么。

误区二：只看题号判断难度

通常题 1 简单，题 3 难，但不是绝对。比赛开始时浏览三题，可以避免在不适合自己的题上浪费太久。

误区三：样例过了就认为正确

样例过了只能说明你没有完全误解题目。真正的正确性需要边界测试和逻辑证明。

误区四：认为暴力没价值

暴力是：

• 部分分来源。
• 正确性基准。
• 帮你理解题目的工具。

误区五：把模板当答案

模板只解决“怎么写”，不解决“为什么这样建模”。USACO 常常考的是把题面变成模板能处理的形式。

7.2.8 Bronze 到 Silver 能力清单

算法能力

• 能熟练写一维/二维前缀和。
• 能写 sort 自定义比较器。
• 能使用 lower_bound / upper_bound。
• 能写二分答案框架。
• 能写 BFS、DFS 和网格 BFS。
• 能写 DSU。
• 能使用 map、set、priority_queue。
• 能写基础 DP。
• 能进行简单贪心证明。

实现能力

• 30 秒内写出快速 I/O 模板。
• 5 分钟内写出方向数组和网格遍历。
• 10 分钟内写出 BFS。
• 5 分钟内写出 DSU。
• 能正确处理 0-index 与 1-index。
• 知道什么时候必须用 long long。

竞赛能力

• 15 分钟内浏览完三题并排序难度。
• 能对每题估计复杂度。
• 卡住时能主动寻找部分分。
• 提交前有固定检查清单。
• 每场后写复盘记录。

7.2.9 四周训练计划

第 1 周：稳定 Bronze 基础

目标：减少低级错误。

• 每天 1 道 Bronze 模拟/枚举题。
• 每题写完后列出边界测试。
• 复习数组、字符串、排序、结构体。

第 2 周：复杂度与优化

目标：从暴力走向 O(N log N) 或 O(N)。

• 练习排序 + 扫描。
• 练习前缀和与差分。
• 练习双指针与滑动窗口。
• 每题写出暴力解和优化解的复杂度对比。

第 3 周：图与二分

目标：进入 Silver 常见题型。

• 练习网格 BFS。
• 练习 DFS 连通块。
• 练习 DSU。
• 练习二分答案。

第 4 周：模拟比赛与复盘

目标：提升赛时表现。

• 每周至少做 1 场 4 小时模拟赛。
• 比赛中严格执行先读三题的流程。
• 赛后补完所有题。
• 记录每题关键洞察和失败原因。

7.2.10 题目日志模板

建议每道题后记录：

题目：
级别：Bronze / Silver / Gold
标签：排序、BFS、DP、Ad Hoc、二分答案……
我一开始的想法：
正确关键洞察：
复杂度：
我犯的错误：
下次遇到类似题要想到：

长期坚持题目日志，会让你形成自己的“题型雷达”。

本章总结

核心要点

竞赛中最实用的五句话

1. 先读完三题。
2. 先看 N，再想算法。
3. 先写暴力，再优化。
4. 样例过了不代表正确。
5. 不会满分也要拿部分分。

常见问题

Q1：我读题后完全没思路怎么办？

先写最直接的暴力，再手算小例子。若仍没有思路，检查是否是图、区间、排序、DP、二分答案或 Ad Hoc。30–40 分钟无进展就切题。

Q2：什么时候应该写对拍？

当你有一个简单但慢的暴力解，以及一个复杂但快的优化解时。尤其是贪心、DP、双指针、排序统计题，对拍非常有用。

Q3：怎么提高算法识别能力？

每道题做完后记录标签和关键洞察。不要只记录“AC”，要记录“为什么这题是二分答案/为什么这题能贪心”。

Q4：比赛中应该追求代码短吗？

不应该。比赛中更重要的是清晰、稳定、可调试。短代码适合熟练后自然形成，不应作为初学目标。

下一章会专门讨论 Ad Hoc 题型。它们没有固定模板，但有一套寻找规律、不变量、构造和模拟捷径的方法。