附录 B：USACO 题目集

本附录提供了按主题分类的 20 道 USACO 精选题目，这些题目经过精心挑选以巩固本书中涵盖的技术。所有题目都可以在 usaco.org 上免费获取。

如何使用本题目集

大致按顺序做这些题。对每道题：

1. 仔细读题，独立尝试解题至少 1-2 小时
2. 若卡住，看下面的提示（不是完整题解）
3. 若再过 30 分钟仍卡住，在 USACO 网站上读题解
4. 解完（或读完题解）后，从零自行实现解法

当你挣扎后再理解时学习最多，而不是被动地读解法。

按学习阶段使用这份题单

这份附录不只是题目列表，更应该当作一张「从章节到真题」的训练地图。建议按下面顺序推进：

做题时的五段复盘法

每道题做完后，不管是否 AC，都用下面五个问题复盘：

1. 题干解读： 题目真正要求的量是什么？哪些约束决定算法复杂度？
2. 思路分析： 为什么这个题对应某个章节的算法？暴力会在哪里超时？
3. CPP 实现： 用到了哪些容器、排序规则、下标约定、快速 I/O？
4. 易错点： 哪个边界最容易错？有没有溢出、越界、重复计数？
5. 拓展思考： 如果数据范围扩大、限制改变、目标函数改变，算法是否还成立？

第一节：模拟与暴力（Bronze）

题目 1：遮挡广告牌

竞赛： USACO 2017 December Bronze | 主题： 二维几何，矩形

描述： 两块广告牌和一辆卡车（都是与坐标轴平行的矩形），求广告牌未被卡车遮挡的面积之和。

数据规模： 矩形顶点坐标满足 0 ≤ x, y ≤ 1000；卡车可能只遮挡一块、两块或不遮挡任何广告牌。

关键洞察： 计算卡车与每块广告牌的交集。广告牌面积 - 交集面积 = 可见面积。

技术： 二维矩形求交、仔细算术 | 难度： ⭐⭐

题目 2：奶牛信号

竞赛： USACO 2016 February Bronze | 主题： 二维数组操作

描述： 给定 K×L 字符网格中的图案，按因子 R「放大」它（每个方向重复每个字符 R 次），输出 RK×RL 的放大结果。

数据规模： 1 ≤ K, L ≤ 10，1 ≤ R ≤ 10；输出最多 100×100 字符。

关键洞察： 输出位置 (i,j) 的字符来自输入的 ((i-1)/R + 1, (j-1)/R + 1)。

技术： 二维数组索引、整数除法 | 难度： ⭐

题目 3：套球游戏

竞赛： USACO 2016 January Bronze | 主题： 模拟

描述： 一个套球游戏：三个壳中一个藏有豆子，给出 N 次交换 (a, b) 及交换后豆子所在位置的猜测，求猜测正确的最大次数。

数据规模： 1 ≤ N ≤ 100 次交换；1 ≤ a, b ≤ 3（壳编号）。

关键洞察： 追踪球在每次交换中的位置，尝试球在三个起始位置下的情况。

技术： 模拟、对起始位置的暴力 | 难度： ⭐

题目 4：统计干草堆

竞赛： USACO 2016 November Bronze | 主题： 排序、搜索

描述： N 捆干草在数轴上的特定位置，Q 次查询问闭区间 [A, B] 范围内有多少捆。

数据规模： 1 ≤ N ≤ 10⁵，1 ≤ Q ≤ 10⁵；位置 0 ≤ x_i ≤ 10⁹；0 ≤ A ≤ B ≤ 10⁹。Q 次查询禁止每次 O(N) 扫描，需要 O(N log N) 预处理 + O(log N) 查询。

关键洞察： 排序干草堆位置，然后对每次查询用二分查找（lower_bound/upper_bound）。

技术： 排序、二分查找 | 难度： ⭐⭐

题目 5：割草

竞赛： USACO 2016 January Bronze | 主题： 网格模拟

描述： FJ 在无穷网格上按 N 条指令割草（每条指令给出转向方向和步数），统计他割了不止一次的格子数。

数据规模： 1 ≤ N ≤ 1000 条指令，每条步数 1 ≤ s ≤ 10；坐标范围有限（约 ±10⁵），可用 map<pair<int,int>> 或偏移数组追踪。

关键洞察： 在集合/映射中追踪所有访问过的位置，再次访问格子时就是双重割草。

技术： 用集合/映射追踪已访问格子、方向模拟 | 难度： ⭐⭐

第二节：数组与前缀和（Bronze/Silver）

题目 6：品种统计

竞赛： USACO 2015 December Bronze | 主题： 前缀和

描述： N 头奶牛排成一排，各有品种 1、2 或 3，Q 次查询问 [L, R] 范围内各品种各有多少头。

数据规模： 1 ≤ N ≤ 10⁵，1 ≤ Q ≤ 10⁵；1 ≤ L ≤ R ≤ N。每次查询 O(1) 的前缀和是标准做法。

关键洞察： 为 3 种品种各建一个前缀和数组，每次查询 O(1) 回答。

技术： 前缀和、多数组 | 难度： ⭐⭐

题目 7：牛蹄剪刀布

竞赛： USACO 2017 January Gold | 主题： DP

描述： Bessie 玩 N 局剪刀石头布（对手手势已知），最多换 K 次手势（游戏开始前选定的初始手势不算换），最大化获胜局数。

数据规模（USACO 官方）： 1 ≤ N ≤ 10⁵，1 ≤ K ≤ 20。状态数 N×K×3 ≈ 6×10⁶，三维 DP 可行。

关键洞察： DP 状态：（轮次，已用次数，当前手势）。完整解法见第 6.2 章。

技术： 三维 DP | 难度： ⭐⭐⭐

第三节：排序与二分查找（Bronze/Silver）

题目 8：愤怒的奶牛

竞赛： USACO 2016 February Bronze | 主题： 排序、模拟

描述： 数轴上 N 头奶牛各有位置，一头奶牛发射「爆炸」半径 R 向外蔓延，被波及的奶牛会以同半径继续引发爆炸。找能引发所有奶牛的最小初始爆炸半径。

数据规模（USACO 官方）： 1 ≤ N ≤ 50，位置 0 ≤ x_i ≤ 10⁸。N 很小，二分答案 + O(N) 模拟绰绰有余。

关键洞察： 对爆炸半径二分答案，对给定半径模拟哪些奶牛被引发。

技术： 二分答案、排序、模拟 | 难度： ⭐⭐⭐

题目 9：攻击性奶牛

竞赛： USACO 2011 March Silver | 主题： 二分答案

描述： 数轴上 N 个位置，从中放置 C 头奶牛（一头一个位置），使任意两头奶牛间的最小距离最大。求该最大化的最小距离。

数据规模（USACO 官方）： 2 ≤ C ≤ N ≤ 10⁵；位置 0 ≤ x_i ≤ 10⁹，互不相同。O(N²) 枚举不可行，需要 O(N log range) 的二分答案。

关键洞察： 对答案（最小距离）二分，对每个候选距离贪心检查能否放 C 头奶牛。

技术： 二分答案、贪心检查 | 难度： ⭐⭐⭐

题目 10：Convention

竞赛： USACO 2018 February Silver | 主题： 二分答案 + 贪心

描述： N 头奶牛在时刻 t[i] 到达车站，乘坐 M 辆各容量 C 的公共汽车（按到达顺序分组上车），最小化任意奶牛的最大等待时间（等待时间 = 发车时间 − 到达时间）。

数据规模（USACO 官方）： 1 ≤ M, C ≤ N ≤ 10⁵，1 ≤ t[i] ≤ 10⁹。对最大等待时间二分答案 + 贪心分组是 O(N log N) 的标准做法。

关键洞察： 对最大等待时间二分，对每个候选值贪心将奶牛分配到汽车。

技术： 二分答案、贪心模拟、排序 | 难度： ⭐⭐⭐

第四节：图论算法（Silver）

题目 11：关闭农场

竞赛： USACO 2016 January Silver | 主题： DSU、离线处理

描述： 农场有 N 块田地和 M 条双向路径，按给定顺序逐一关闭（移除）田地，每次移除后判断剩余开放田地是否仍全部连通。

数据规模（USACO 官方）： 1 ≤ N ≤ 3000，1 ≤ M ≤ 6000。逆向 + DSU 的 O((N+M)α) 是标准做法；正向暴力 O(N·(N+M)) 在此规模勉强可行但慢。

关键洞察： 逆向处理——按逆序添加田地，用 DSU 追踪添加田地时的连通性。

技术： DSU、逆向处理 | 难度： ⭐⭐⭐

题目 12：Moocast

竞赛： USACO 2016 February Silver | 主题： DSU / BFS

描述： 平面上 N 头奶牛，各有对讲机广播半径 p[i]（所有奶牛半径相同参数 p，即题中统一的 X）。奶牛 i 与 j 能直接通信当且仅当距离 ≤ p；通信可多跳中继。找使所有奶牛相互连通的最小 p。

数据规模（USACO 官方）： 1 ≤ N ≤ 1000（Silver 版本），坐标 0 ≤ x, y ≤ 25000。

关键洞察： 对最小范围二分答案，对给定范围建图并检查连通性。

技术： 二分答案、BFS/DFS 连通性，或 Kruskal MST | 难度： ⭐⭐⭐

题目 13：BFS 最短路

竞赛： 经典问题（倒水问题）| 主题： 状态空间 BFS

描述： 容量为 X 和 Y 的两个桶，可用操作为装满/倒空/互倒，找使任意一桶恰好有 M 升的最少操作次数；无解输出 −1。

数据规模： 1 ≤ X, Y ≤ 100，1 ≤ M ≤ max(X, Y)；状态数至多 (X+1)×(Y+1)，状态空间 BFS 轻松处理。

关键洞察： 将（桶1中的量，桶2中的量）建模为图状态，BFS 找最少操作次数。

技术： 状态图 BFS | 难度： ⭐⭐⭐

题目 14：草地鉴赏家

竞赛： USACO 2015 December Silver | 主题： SCC（强连通分量）、DAG 上的 BFS

描述： 牧场构成有 N 个节点、M 条边的有向图，Bessie 从节点 1 出发沿边方向游览，且可以免费反转一条边（至多一条、可不用）。求她能访问的最多不同牧场数（可重复经过，只数不同）。

数据规模（USACO 官方）： 2 ≤ N ≤ 10⁵，1 ≤ M ≤ 2×10⁵。

关键洞察： 将 SCC 收缩为超级节点，在 DAG 上做 BFS，对每条可反转的边检查改善情况。

技术： SCC、BFS、图收缩 | 难度： ⭐⭐⭐⭐（Gold 级别思维，Silver 竞赛题）

第五节：动态规划（Silver）

题目 15：矩形牧场

竞赛： USACO 2021 January Silver | 主题： 二维前缀和、DP

描述： N 头奶牛在二维平面上（任意两头奶牛的横纵坐标各不相同），统计四条边平行于坐标轴、恰好包含 K 头奶牛的矩形数量（边界上的奶牛也算包含）。

数据规模（USACO 官方）： 1 ≤ N ≤ 2000，1 ≤ K ≤ N；坐标 1 ≤ x, y ≤ 2500。

关键洞察： 按 x 排序，对每对列，在行上做 DP，二维前缀和快速统计矩形。

技术： 二维前缀和、组合数学 | 难度： ⭐⭐⭐

题目 16：柠檬水队伍

竞赛： USACO 2017 February Bronze | 主题： 贪心

描述： N 头奶牛想排队买柠檬水。奶牛 i 只在队列中已有 ≤ p[i] 头奶牛（排在它前面）时才愿意加入，否则离开。你可以自由选择邀请顺序。求队伍中奶牛的最大数量。

数据规模（USACO 官方）： 1 ≤ N ≤ 10⁵，1 ≤ p[i] ≤ 10⁹。

关键洞察： 按耐心（p[i]）降序排序，贪心地尽可能添加每头奶牛。

技术： 排序、贪心 | 难度： ⭐⭐

题目 17：最高奶牛

竞赛： USACO 2016 February Silver | 主题： 差分数组

描述： N 头奶牛站成一排，给定所有奶牛的最大身高 H 和 R 条关系 (A, B)（A、B 互不相同）：奶牛 A 和 B 能互相看见，意味着两者之间的奶牛身高都严格小于 min(h[A], h[B])。在满足所有关系的前提下，求每头奶牛的最大可能身高。

数据规模（USACO 官方）： 1 ≤ N ≤ 10⁴，1 ≤ R ≤ 10⁴，1 ≤ H ≤ 10⁶。

关键洞察： 用差分数组追踪身高约束，对每对 (A, B)，A 和 B 之间的奶牛必须比两者都矮。

技术： 差分数组、前缀和 | 难度： ⭐⭐⭐

第六节：混合（Silver）

题目 18：平衡行动

竞赛： USACO 2018 January Silver | 主题： 树形 DP、质心

描述： 给定 N−1 条边构成的树。删除一个节点后树分裂成若干连通分量；找使「最大分量最小」的节点（质心），输出删除它之后最大连通分量的大小。

数据规模（USACO 官方）： 1 ≤ N ≤ 10⁵；树上一次 DFS 求 O(N) 是标准做法。

关键洞察： 通过 DFS 计算子树大小。移除某节点时最大分量是 max(各子节点子树大小, N - 该节点子树大小)。

技术： 树形 DP、子树大小 | 难度： ⭐⭐⭐

题目 19：拼接国家

竞赛： USACO 2016 January Bronze | 主题： 字符串操作、排序

描述： 给定 N 个字符串，对每对 (i, j)（i < j）形成字符串 s_i + s_j（i 在前），统计有多少个这样的拼接字符串是回文。

数据规模： 1 ≤ N ≤ 1000，字符串总长 ≤ 2×10⁶，每个字符串只含小写字母。O(N²) 配对配合哈希/直接比较可行。

关键洞察： 检查每一对，O(N² × L)，N ≤ 1000 时可行。

技术： 字符串操作、回文检查 | 难度： ⭐⭐

题目 20：摘浆果

竞赛： USACO 2020 January Silver | 主题： 贪心、DP

描述： Bessie 从 N 棵树上摘浆果（树 i 有 b_i 个），共 K 个篮子，每个篮子的浆果只能来自一棵树；Bessie 和 Elsie 各分 K/2 个篮子，且 Elsie 的所有篮子必须装有相同数量的浆果（Bessie 的篮子数量任意但非空）。最大化 Bessie 篮子中的总浆果数。

数据规模（USACO 官方）： 1 ≤ N ≤ 1000，1 ≤ K ≤ 1000（K 为偶数），1 ≤ b_i ≤ 10⁶。

关键洞察： 最优：K/2 个篮子给 Bessie，K/2 个给 Elsie。排序树，对 Elsie 篮子的每种可能大小，二分查找找 Bessie 的最优分配。

技术： 排序、二分查找、贪心 | 难度： ⭐⭐⭐⭐

代表题深度拆解：如何把真题映射回章节

下面选取几道代表题，示范如何用「题干解读 → 思路分析 → CPP 实现要点 → 易错点 → 拓展思考」复盘。完整代码建议回到对应章节阅读或自行实现。

代表题 A：统计干草堆（题目 4）

• 对应章节： 第 3.3 章（排序与搜索）、第 3.9 章（二分答案的前置思想）
• 数据规模： 见上文题目 4——1 ≤ N, Q ≤ 10⁵，位置 0 ≤ x_i ≤ 10⁹，0 ≤ A ≤ B ≤ 10⁹。
• 题干解读： 多次询问区间 [A,B] 内有多少个点。Q 很大，不能每次扫描所有干草堆。
• 思路分析： 排序位置数组后，用 lower_bound(A) 找第一个 ≥ A 的位置，用 upper_bound(B) 找第一个 > B 的位置，两者下标差就是答案。
• CPP 实现要点： auto left = lower_bound(pos.begin(), pos.end(), A);，auto right = upper_bound(pos.begin(), pos.end(), B);，答案是 right - left。
• 易错点： upper_bound(B) 不是 lower_bound(B)；区间端点是闭区间 [A,B]。
• 拓展思考： 如果位置会动态新增/删除，静态数组二分不够，需要 set、树状数组或线段树。

代表题 B：关闭农场（题目 11）

• 对应章节： 第 5.6 章（并查集）、第 5.1–5.2 章（图的连通性）
• 数据规模： 见上文题目 11——1 ≤ N ≤ 3000，1 ≤ M ≤ 6000。
• 题干解读： 农场按给定顺序关闭，每次问剩余开放节点是否连通。正向删除很难维护连通性。
• 思路分析： 反向思考：关闭顺序反过来就是逐个打开节点。并查集擅长维护「新增边后的连通块数量」。
• CPP 实现要点： 反向遍历打开节点；每打开一个节点，连通块数 components++；对已打开邻居执行 union，成功合并则 components--。
• 易错点： 只和已经打开的邻居合并；答案要反向填回原顺序；节点编号通常是 1-indexed。
• 拓展思考： 如果题目要求支持任意时刻删除和新增边，普通 DSU 不支持删除，需要离线处理、分治回滚 DSU 或动态连通性结构。

代表题 C：牛蹄剪刀布（题目 7）

• 对应章节： 第 6.1 章（DP 入门）、第 6.2 章（经典 DP 问题）
• 数据规模： 见上文题目 7——1 ≤ N ≤ 10⁵，1 ≤ K ≤ 20。
• 题干解读： 已知对手每轮手势，Bessie 可改变手势的次数有限，目标最大化胜场。
• 思路分析： 当前最优不仅取决于第几轮，还取决于已经换了几次、当前手势是什么，因此状态应包含 (轮次, 切换次数, 当前手势)。
• CPP 实现要点： dp[i][k][g] 表示前 i 轮、用了 k 次切换、当前手势 g 的最多胜场；转移分「不换」和「从其他手势换来」。
• 易错点： 最终答案是使用 0..K 次切换的最大值，不是恰好 K 次；初始选择手势不算切换。
• 拓展思考： 手势种类增加时，朴素转移会出现 M^2，可以维护最大/次大优化。

代表题 D：摘浆果（题目 20）

• 对应章节： 第 4 部分（贪心）、第 3.9 章（二分/枚举答案思想）
• 题干解读： 需要在篮子容量和分配之间取最大收益，表面像 DP，但关键是枚举篮子大小后贪心填充。
• 思路分析： 固定 Elsie 篮子的大小后，剩下分配可以排序贪心；难点是把「容量」作为枚举对象。
• CPP 实现要点： 枚举每个可能篮子大小，统计能装满多少篮子，再考虑剩余浆果对 Bessie 的贡献。
• 易错点： 只考虑装满篮子会漏掉 Bessie 的半满篮；排序方向和取前 K/2 个收益容易写错。
• 拓展思考： 这类题体现 USACO Silver/Gold 常见技巧：不直接枚举方案，而是枚举一个关键参数，把剩余部分变成贪心。

快速参考：按技术分类的题目

练习建议

1. 在 train.usaco.org 上使用 USACO 训练门户自动评测
2. 每道题后都读题解（在 usaco.org 上）——哪怕是你解出来的题
3. 保持题目日志——写下每道题的关键洞察
4. 难度进阶：从近年简单题做起，再做老年份的中等题

其他题目来源

CSES 题目集（cses.fi/problemset）特别推荐——约 300 道精心策划的题目，涵盖所有 USACO Silver 主题，自动评测，免费。