N ≤ 20？
├── 是 → 尝试暴力（O(2^N) 或 O(N!)）
└── 否
    是图/网格题吗？
    ├── 是
    │   是最短路问题吗？
    │   ├── 是（无权） → BFS
    │   ├── 是（有权） → Dijkstra（Gold）
    │   └── 否（连通性） → DFS / 并查集
    └── 否
        排序有用吗？
        ├── 是 → 排序 + 扫描 / 二分查找
        └── 否
            有「重叠子问题」吗？
            ├── 是 → 动态规划
            └── 否 → 贪心 / 模拟

7.2.3 用样例测试

始终先测试给定样例

提交前，验证你的解法对所有给定样例都能产生完全正确的输出。

# 编译
g++ -o sol solution.cpp -std=c++17

# 用样例输入测试
echo "5
3 1 4 1 5" | ./sol

# 或从文件
./sol < sample.in

自己创造测试用例

给定的样例很简单。自己创造：

最小情况： N=1，N=0，空输入
最大情况： N 取最大约束，所有值取最大
所有值相同： N 个元素全部相等
已排序/逆序排列
特殊结构： 完全图、路径图、星形图（图论题）

对拍

为小 N 写一个暴力解法，然后与你的优化解法对比随机输入：

📄 为小 N 写一个暴力解法，然后与你的优化解法对比随机输入：

// brute.cpp — 简单 O(N^3) 解法
// sol.cpp — 你的 O(N log N) 解法

// stress_test.sh：
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 "第 $i 个测试不一致"
        cat test.in
        break
    fi
done
echo "所有测试通过！"

对拍能发现样例漏掉的微妙 bug。

7.2.4 C++ 调试技巧

策略一：打印一切

出问题时，加 cerr 语句追踪程序执行。cerr 输出到标准错误（与标准输出分离）：

cerr << "在节点 " << u << "，dist = " << dist[u] << "\n";
cerr << "数组状态：";
for (int x : arr) cerr << x << " ";
cerr << "\n";

为什么用 cerr 不用 cout？ cout 输出到标准输出，评测机在那里检查你的答案。cerr 输出到标准错误，评测机通常忽略。所以调试输出不会污染你的答案。

策略二：用 `assert` 检查不变量

assert(n >= 1 && n <= 100000);   // 条件失败时崩溃并给出信息
assert(dist[v] >= 0);            // 检查 BFS 不变量

策略三：检查数组边界

int arr[100];
arr[100] = 5;   // Bug！合法下标是 0-99

// 调试时用地址消毒器检测边界问题：
// g++ -fsanitize=address,undefined -o sol sol.cpp

策略四：小黄鸭调试法

逐行大声解释你的代码（或写下来），解释的行为迫使你注意不一致之处，很多 bug 就是这样发现的——不是盯着屏幕，而是阐明每行代码应该做什么。

策略五：缩小问题

若代码在大输入上失败，手动创建最小的仍然失败的输入，修复它，重复。

策略六：读编译器警告

g++ -Wall -Wextra -o sol sol.cpp

-Wall -Wextra 启用所有警告，读它们！未初始化变量、未使用变量、有符号/无符号不匹配——都是常见的 USACO bug。

7.2.5 USACO 特有调试

检查 I/O

正确算法答案错误的第 1 原因：错误的输入/输出格式。

你读取了正确数量的值吗？
你打印了正确数量的行吗？
有多余的空格或缺少换行吗？

测试运行时间

检查你的解法是否够快：

time ./sol < large_input.in

USACO 通常允许 2-4 秒。若你的解法本地需要 10 秒，会超时。

先估算复杂度

编码前计算：「我的算法是 O(N²)，N = 10^5，那是 10^10 次运算，太慢了。」

C++ 中 1 秒大概能运行的操作数：

10^8 次简单操作
10^7 次复杂操作（如 map 查询）
10^5 × 10^3 = 10^8，嵌套循环带简单循环体

7.2.6 Bronze 到 Silver 检查清单

用这个清单评估你是否准备好了 Silver：

需要掌握的算法

前缀和（一维和二维）
二分查找（包括二分答案）
图和网格上的 BFS 和 DFS
并查集（DSU）
带自定义比较器的排序
基础 DP（一维 DP、二维 DP、背包）
STL：map、set、priority_queue、vector、sort

解题技能

能判断一道题需要 BFS vs DFS vs DP vs 贪心
能在 10 分钟内从零实现 BFS
能在 5 分钟内从零实现 DSU
能把网格题建模成图
知道如何对答案二分
熟练使用二维数组和网格遍历

竞赛技能

能在 30 秒内写出带快速 I/O 的清晰模板
需要时从不忘记 long long
提交前始终用样例测试
能快速读懂并理解约束条件
至少练习过 20 道 Bronze 题
至少解过 5 道 Silver 题（哪怕借助提示）

练习计划

解所有容易找到的 USACO Bronze 题（2016–2024）
每道 2 小时内解不出的题：读题解，从零实现
解 30+ 道 Bronze 后，挑战 Silver：从 2016–2018 Silver 开始
保持题目日志：题目名称、用到的技术、关键洞察

7.2.7 资源

官方

USACO 官网： usaco.org —— 竞赛档案、题解
USACO 训练营： train.usaco.org —— 旧但好的结构化课程

非官方

USACO Guide： usaco.guide —— 优秀的社区编写指南，强烈推荐
Codeforces： codeforces.com —— 更多题目和竞赛
AtCoder： atcoder.jp —— 高质量教学题

书籍

Competitive Programmer's Handbook by Antti Laaksonen —— 免费 PDF，优秀
Introduction to Algorithms（CLRS）—— 理论圣经（读起来较重）

本章总结

📌 核心要点

技能	练习直到……
读题	3 分钟内理解题目
算法识别	70%+ 的情况猜对正确方案
实现	标准题在 30 分钟内完成
调试	30 分钟内定位并修复 bug
测试	养成提交前测试边界情况的习惯

🧩 「解题思维」快速检查清单

步骤	问自己的问题
1. 检查 N 范围	N ≤ 20 → 暴力/状压；N ≤ 10^5 → O(N log N)
2. 图/网格？	是 → BFS/DFS/DSU
3. 优化某个值？	「最大化最小值」或「最小化最大值」→ 二分答案
4. 重叠子问题？	是 → DP
5. 排序后贪心？	是 → 贪心
6. 区间查询？	是 → 前缀和 / 线段树

❓ 常见问题

Q1：遇到完全陌生的题型怎么办？

A：① 先写小数据的暴力获取部分分；② 画图、手动计算小例子找规律；③ 试着简化题目（如果是二维，先想一维版本）；④ 若仍卡住，转向下一道题，稍后回来。

Q2：如何提高「题型识别」能力？

A：有意识地分类练习。每道题做完后记录其「标签」（BFS、DP、贪心、二分等）。练习足够多后，会立即把类似的约束和关键词与正确的算法联系起来。本书第 7.1 章的模式速查表是个好的起点。

Q3：竞赛中应该先写暴力还是直接写最优解？

A：先写暴力。暴力代码通常只需 5 分钟，有三个用途：① 获取部分分；② 帮助理解题目；③ 用于对拍验证最优解。即使对自己的解法有把握，也建议先写暴力。

Q4：如何用对拍高效调试？

A：写三个程序：brute.cpp（正确的暴力）、sol.cpp（你的优化解法）、gen.cpp（随机数据生成器）。循环运行并比较输出，发现不一致时那个小测试就是调试线索。这是竞赛编程中最强大的调试技术。

🔗 与其他章节的联系

本章的算法决策树涵盖了本书所有章节的核心算法
第 7.1 章涵盖 USACO 竞赛规则和题目分类；本章涵盖「如何解题」
Bronze 到 Silver 检查清单总结了第 2.1–6.3 章的所有知识点
本章的对拍技术可以应用于所有章节的练习题

从 Bronze 到 Silver 的旅程是大量练习加上有意识的反思。每道你解过（或没解出）的题后，问自己：「关键洞察是什么？下次怎么更快地认出这类题型？」

祝你好运，享受和奶牛们在一起的时光。🐄

C++ 竞赛编程：USACO 学习指南