附录 B：USACO 题目集

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

如何使用本题目集

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

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

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

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

题目 1：遮挡广告牌

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

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

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

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

题目 2：奶牛信号

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

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

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

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

题目 3：套球游戏

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

描述： 一个套球游戏，追踪球在一系列交换后的位置。

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

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

题目 4：统计干草堆

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

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

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

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

题目 5：割草

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

描述： FJ 按 N 条指令割草，统计他割了不止一次的格子数。

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

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

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

题目 6：品种统计

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

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

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

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

题目 7：牛蹄剪刀布

竞赛： USACO 2019 January Silver | 主题： DP

描述： Bessie 玩 N 局，最多换 K 次手势，最大化获胜局数。

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

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

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

题目 8：愤怒的奶牛

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

描述： 数轴上的奶牛，一头奶牛发射「爆炸」向外蔓延，引发其他奶牛。找能引发所有奶牛的最小初始爆炸半径。

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

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

题目 9：攻击性奶牛

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

描述： N 个位置，放置 C 头奶牛使任意两头奶牛间的最小距离最大。

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

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

题目 10：Convention

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

描述： N 头奶牛在时间 t[i] 到达，乘坐 M 辆容量为 C 的公共汽车，最小化最大等待时间。

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

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

第四节：图论算法（Silver）

题目 11：关闭农场

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

描述： 农场有 N 块田地和 M 条路径，逐一移除田地，每次移除后判断剩余田地是否仍全部连通。

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

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

题目 12：Moocast

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

描述： 田地上 N 头奶牛，各有对讲机范围 p[i]。找使所有奶牛能通信（直接或通过中继）的最小范围。

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

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

题目 13：BFS 最短路

竞赛： USACO 2016 February Bronze：牛奶桶（改编）| 主题： 状态空间 BFS

描述： 容量为 X 和 Y 的两个桶，填/倒/出操作，找使任意一桶恰好有 M 升的最少操作次数。

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

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

题目 14：草地鉴赏家

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

描述： 牧场有向图，Bessie 可以免费反转一条边，找从牧场 1 出发的环游能访问的最多牧场数。

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

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

第五节：动态规划（Silver）

题目 15：矩形牧场

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

描述： N 头奶牛在二维网格上（横纵坐标各不同），统计恰好包含 K 头奶牛的轴对齐矩形数量。

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

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

题目 16：柠檬水队伍

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

描述： N 头奶牛，奶牛 i 在队伍中已有 ≤ p[i] 头奶牛时才会加入，求队伍中奶牛的最大数量。

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

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

题目 17：最高奶牛

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

描述： N 头奶牛排成一排，给定对 (A, B) 表示奶牛 A 能看到 B（即两者之间的奶牛都更矮），求每头奶牛的最大可能身高。

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

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

第六节：混合（Silver）

题目 18：平衡行动

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

描述： 找树的「质心」——移除后创建最平衡划分的节点（最大化最小剩余分量大小）。

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

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

题目 19：拼接国家

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

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

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

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

题目 20：摘浆果

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

描述： Bessie 从 N 棵树上摘浆果，有 K 个篮子，每个篮子只能装一棵树的浆果，在同组篮子必须装相同数量的约束下最大化总浆果数。

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

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

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

练习建议

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

其他题目来源

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