第 7.1 章：了解 USACO

如果你第一次参加 USACO，最重要的不是马上学习高级算法，而是先弄清楚这场比赛如何给分、如何晋级、如何安排时间、如何避免低级失误。

很多同学明明会写代码，却在第一次比赛中因为以下原因丢分：

• 只读了第一题，没有比较三题难度。
• 看到不会的题就放弃，没有写小数据部分分。
• 算法复杂度估错，写了必定超时的 O(N²)。
• 样例过了就提交，没有测边界情况。
• 用 int 存了会超过 (2^{31}-1) 的答案。

本章会从零讲清 USACO 的规则，并站在教练角度告诉你：怎样把 4 小时变成尽可能多的分数。

7.1.1 USACO 是什么

USACO（USA Computing Olympiad，美国计算机奥林匹克竞赛）是面向中学生的算法竞赛体系，也是美国选拔 IOI（国际信息学奥林匹克竞赛）选手的重要渠道。

对普通参赛者来说，你可以把 USACO 理解为：

• 一套免费、在线、长期开放的算法竞赛。
• 一条从基础编程到高水平算法的分级路线。
• 一个非常适合训练 C++、数据结构、图论、动态规划和竞赛思维的平台。

USACO 的特点

教练提醒： USACO 不是“只要知道算法就能赢”的比赛。许多 Bronze/Silver 题真正考的是建模、细节和稳定性。

7.1.2 比赛形式

比赛日程

USACO 每个赛季通常有 4 场比赛：

• December Contest：12 月赛。
• January Contest：1 月赛。
• February Contest：2 月赛。
• US Open：通常在 3/4 月，时间更长，难度也常常更高。

下图展示了一个典型赛季的节奏：

比赛时长与题数

比赛通常在一个多天窗口内开放。你可以在窗口内选择一个合适时间开始，但一旦开始，计时就连续进行。

输入输出形式

USACO 早期题目常使用文件输入输出，例如从 problem.in 读入，输出到 problem.out。较新的题目更多使用标准输入输出。

一定以题面说明为准。

文件 I/O 模板如下：

#include <bits/stdc++.h>
using namespace std;

int main() {
    freopen("problem.in", "r", stdin);
    freopen("problem.out", "w", stdout);

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // solution code

    return 0;
}

标准 I/O 模板如下：

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // solution code

    return 0;
}

7.1.3 四个级别

USACO 有四个主要级别：

Bronze：基础编程与细节

Bronze 适合刚开始算法竞赛的同学。它主要考：

• 循环、数组、字符串、结构体。
• 模拟、枚举、计数、排序。
• 简单几何、网格、区间处理。
• Ad Hoc 观察题。

Bronze 的难点常常不是算法高级，而是：

• 能否读懂题目真正要求。
• 能否不漏情况地实现模拟。
• 能否根据数据范围写出够快的暴力。

典型复杂度： O(N)、O(N log N)、O(N²)、有时 O(N³)。

Silver：标准算法入门

Silver 开始大量出现标准算法：

• 排序 + 扫描。
• 前缀和、差分。
• 二分查找、二分答案。
• BFS、DFS、连通块。
• 并查集（DSU）。
• 双指针、滑动窗口。
• 基础动态规划。

Silver 的核心变化是：N 经常达到 (10^5)，这意味着你不能再随便写 O(N²)。

典型复杂度： O(N)、O(N log N)、O(N + M)。

Gold：算法组合与证明能力

Gold 对算法熟练度和证明能力要求明显提高。常见主题包括：

• Dijkstra、最小生成树、拓扑排序。
• 树形 DP、LCA、欧拉序。
• 线段树、树状数组。
• 更复杂的 DP。
• 数学、组合计数、状态设计。

Gold 题往往不只问“会不会模板”，而是要求你把多个思想组合起来。

Platinum：高阶竞赛水平

Platinum 是 USACO 的最高公开级别，题目接近高水平竞赛难度，可能涉及：

• 高级数据结构。
• 复杂图论。
• 高阶动态规划。
• 组合数学与构造。
• 需要较强证明能力的原创题。

7.1.4 晋级与评分

基本评分方式

每道题由多个隐藏测试点组成。通过一个测试点就得到相应分数，没通过则不得该测试点分数。

为什么部分分很重要

很多选手的错误心态是：

“我不会完整解法，所以这题没法做。”

这是不对的。USACO 很多题会包含小数据测试点或特殊结构测试点。例如：

• 完整数据 N ≤ 100000，但部分分 N ≤ 1000。
• 完整图是一般图，但部分分图是一条链或一棵树。
• 完整值域很大，但部分分值域很小。
• 完整要求最优解，但部分分允许暴力枚举。

如果你能在一题上拿 100%，另一题拿 80%，第三题拿 30%，总分就可能非常接近晋级线。

部分分策略

教练提醒： 错误答案通常没有额外罚分。只要代码能编译运行，部分解就值得提交。

7.1.5 用约束判断算法复杂度

USACO 题面的约束不是装饰，它几乎直接告诉你要用什么复杂度。

经验估算：C++ 每秒大约能执行 (10^8) 次非常简单的操作。若 N = 100000，O(N²) 约为 (10^{10})，通常必定超时。

判断流程

1. 看 N 的最大值。
2. 估算你的循环次数。
3. 若超过 (10^8) 到 (10^9) 级别，基本危险。
4. 再看值域，判断是否需要 long long 或坐标压缩。
5. 最后再决定具体算法。

7.1.6 竞赛时间管理

一场 USACO 通常 4 小时，看似很长，实际很快。推荐按阶段使用时间。

前 15 分钟：浏览全部题

不要一开始就写第一题。先快速阅读三题：

• 每题问什么？
• N 和值域多大？
• 看起来像什么题型？
• 哪题最有把握？
• 哪题可能有部分分？

给每题做一个初步标记：

第 15–90 分钟：拿下第一道题

优先选择最稳的题，而不一定是题号最小的题。

目标：拿到至少一道满分或接近满分的题。

这能稳定心态，也能避免整场比赛颗粒无收。

第 90–180 分钟：冲第二道题

第二道题是决定晋级的关键。此时你应该：

• 先写清楚思路和复杂度。
• 如果最优解不确定，先写暴力版本。
• 用样例和自造边界测试。
• 尽早提交一次稳定版本。

最后 60 分钟：取舍

最后一小时要非常务实：

• 若第二题还有 bug，优先修它。
• 若第三题完全没思路，写小数据部分分。
• 若已有两题高分，避免重写大段代码导致崩盘。
• 最后 30 分钟主要做测试和格式检查。

教练经验： 许多选手不是输在不会第三题，而是输在第二题明明会却因为赶第三题留下 bug。

7.1.7 读题方法

USACO 题面常有故事背景。故事可以帮助理解，但你必须把它翻译成精确模型。

读题四步

1. 抽目标：最终要输出什么？最大值、最小值、数量、是否可行、构造方案？
2. 抽输入：有哪些对象？数组、点、边、区间、字符串、网格？
3. 抽限制：N、M、值域、是否有特殊性质？
4. 抽操作：允许做什么？每次操作改变哪些量？

题面中最重要的词

手动推演样例

样例不是用来“跑一下代码”的，而是用来确认你理解题意的。写代码前你应该能手算出样例输出。

如果你手算样例都算不出来，说明你还没理解题目，不应该开始编码。

7.1.8 Bronze 题型地图

Bronze 不是“简单题”的同义词，而是“主要用基础编程解决”的级别。常见题型如下：

Bronze 训练重点

要晋级 Silver，Bronze 选手应优先训练：

• 读题后能准确复述问题。
• 根据 N 选择 O(N)、O(N log N)、O(N²) 或 O(N³)。
• 能写稳定的模拟。
• 能独立处理边界情况。
• 能在没有完美思路时写部分分。

7.1.9 Silver 题型地图

Silver 需要你把基础编程升级为标准算法思维。

Silver 与 Bronze 的区别

7.1.10 常见错误与修正

1. 差一错误

// 错误：漏掉最后一个元素
for (int i = 0; i < n - 1; i++) {
    // ...
}

// 错误：访问 a[n]
for (int i = 0; i <= n; i++) {
    cout << a[i] << "\n";
}

// 正确：0-indexed 数组
for (int i = 0; i < n; i++) {
    // ...
}

2. 整数溢出

int a = 1000000000;
int b = 1000000000;
long long wrong = a * b;              // 先以 int 相乘，已经溢出
long long right = 1LL * a * b;        // 正确

3. 未初始化变量

int ans;          // 错误：值不确定
int best = 0;     // 正确：根据题意初始化

若要求最大值，常用：

int best = INT_MIN;

若要求最小值，常用：

int best = INT_MAX;

4. 输入输出格式错误

常见错误包括：

• 少输出换行。
• 多输出调试信息。
• 文件 I/O 和标准 I/O 用错。
• 没读完整个输入。
• 多组测试时忘记循环。

调试输出应使用 cerr，不要用 cout。

5. 数组大小不够

若题目 N ≤ 100000，数组至少应开到 100000，若你用 1-indexed，最好开到 100005。

const int MAXN = 100000 + 5;
int a[MAXN];

6. 忽略边界情况

提交前至少检查：

• N = 1。
• 所有值相同。
• 已经满足条件。
• 完全不满足条件。
• 最大值导致溢出。
• 图不连通。
• 字符串长度为 1。

7.1.11 参赛模板与本地测试

推荐编译命令

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

调试阶段可以使用：

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

-fsanitize=address,undefined 能帮助发现越界、未定义行为等问题。正式提交前一般不需要保留这些选项。

最小模板

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    return 0;
}

常用方向数组

int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, -1, 1};

网格题中统一用 r 表示行、c 表示列，能减少行列混淆。

7.1.12 如何补题

补题是 USACO 进步最快的环节。正确补题不是“看懂题解就算了”，而是经历下面过程。

补题五步

1. 重新读题：确认比赛时有没有读错。
2. 自己再想 30 分钟：尤其是看约束和小例子。
3. 只看提示：例如“这题用二分答案”或“先排序”。
4. 读完整题解：重点理解关键观察，不是代码细节。
5. 关掉题解，从零实现：能独立写出来才算掌握。

复盘问题清单

每道错题问自己：

• 我卡在题意、算法、证明还是实现？
• 约束给了什么提示，我当时忽略了吗？
• 有没有小例子可以更早看出规律？
• 我的复杂度估算是否正确？
• 如果比赛再遇到类似题，我的第一反应应该是什么？

把答案记录在题目日志中。长期来看，这比机械刷题更重要。

本章总结

核心要点

赛时快速清单

• 已读完三道题。
• 已记录每题 N、值域、特殊性质。
• 已估算复杂度。
• 已选择最稳题目先做。
• 不会满分时已考虑部分分。
• 提交前测试样例和边界。
• 检查 long long、数组大小、输出格式。

常见问题

Q1：第一次参加 USACO 应该期待什么？

不要期待第一次就一定晋级。你的目标应该是熟悉流程、至少认真完成一题，并在赛后完整复盘。

Q2：Bronze 晋级 Silver 最需要补什么？

最需要补的是稳定实现和复杂度意识。会写模拟、枚举、排序、计数，并能避免低级错误，比学很高级的算法更重要。

Q3：比赛中可以查资料吗？

通常可以查通用资料，例如 C++ 文档、算法说明，但不能查本场题解或寻求他人帮助。具体以官方规则为准。

Q4：是否应该用 Python？

USACO 支持多语言，但本书推荐 C++。C++ 速度快，STL 强大，也最适合学习主流竞赛算法。

Q5：我应该什么时候放弃一道题？

如果 30–40 分钟没有新进展，先提交已有部分解，然后切换题目。放弃不是失败，而是比赛资源管理。

下一章会进入更具体的解题流程：如何从题面约束推算法，如何测试，如何调试，以及如何把 Bronze 能力训练到 Silver 水平。