USACO白银组真题解析：模拟、贪心、DFS与动态规划通关指南

USACO白银组2008年2月那场月赛，在我备考清单里一直占着特殊位置。那时候的USACO还没有现在这么友好的页面，题目是纯英文，交上去要等评测机慢慢跑，回来的结果常常是“line 42: segmentation fault”。白银组恰好卡在入门参赛者的必经路上：青铜组太简单，黄金组又够不着，只有白银组这套题的难度分布最接近真实比赛——你算法不一定精，但你必须把一个想法完整地写成代码、改到通过为止。

下面内容我会把这个阶段最值得讲的四类题逐题拆开讲清楚：每题读题之后第一反应应该是什么、为什么那样想，最终代码怎么落地，以及我在老OJ上提交时踩过的具体坑。不论你是刚升白银的选手，还是刷了好多题但总是卡在“会思路不会代码”阶段的备赛党，这套题都很值得踏踏实实过一遍。

1. 2008年2月白银组的地图：出题风格和那个年代的USACO

1.1 当时的比赛环境和白银组定位

2008年左右的USACO，和现在差别还挺大的。比赛采用标准输入输出（stdio），不像USACO Training里的老题那样要求从文件读、往文件写；语言上C++、Java、Pascal都能交，但那会儿用Pascal交题的中学生还特别多，网上题解一半是Pascal。评测反馈没法即时看，一层一层翻日志，有时候一个变量忘初始化，得等好几分钟才知道错哪。

白银组的定位很明确：从青铜升上来之后，你需要证明自己不仅会“写程序”，而且会“想算法”。青铜组考的基本是模拟、简单循环；白银组开始出现排序加贪心、搜索、以及最基础的动态规划。2008年2月这场就是非常标准的一套白银组试卷——四道题，难度递进，覆盖了四个完全不同的算法方向。很多后来进黄金组的朋友回头看，都会觉得格外的怀念：这几乎就是“白银组到底考什么”的官方答案。

1.2 四类模型怎么分布

这套分布后来我看过好多场，几乎成了白银组的“标准模板”：一张试卷必须有纯模拟题用来筛“读题不仔细”的选手，必须有排序贪心题用来筛“只会套模板不会证明”的选手，必须有搜索题用来筛“不敢写递归”的选手，最后放一道入门DP，用来筛“没建立状态概念”的选手。2008年2月的题目恰好把这四类都占全了。想升黄金，这四关一道都躲不掉。

2. 第一题：组合锁判定——最不起眼的模拟题其实最能筛人

2.1 题意重述与数据范围

这道题当时的表述大致是：农夫约翰的仓库门上装了一个三位数字密码锁，每位数字的范围是1到N，三位数字可以完全相同，也可以完全不同。约翰自己设了一个正确密码，同时他的助手在说明书上记下了另一个据说也能开锁的密码（可能正确，也可能不正确，但题目保证两个密码的各对应位都不相同）。这台锁有个特殊设定：只要你在锁上拨的三位数字和正确密码的所有对应位之差，在环形意义下都不超过2，门就能打开。问一共有多少个不同的拨法能开锁。

环形意义的“差不超过2”是这道题最容易理解错的地方。因为密码设成1到N，N和1在数轴上隔着N-1，但在拨号盘上它们其实是相邻的。比如N=10，密码是(1,2,3)，拨(9,10,1)时，第一位9和1就比较近：从9往后走9和10、1，距离是3？不对，环形意义下1和9的距离其实是2，因为走的方向可以顺着走9→10→1，也可以逆着走1→9。这里需要小心计算，所以题目专门强调了一个“环形”的概念。数据范围我记得是N最大100，全部拨法最多100万种，哪怕写最笨的三重循环也毫无压力。

2.2 暴力的正确姿势

这种模拟题，第一反应别想优化，直接枚举。三位数字x、y、z，分别从1到N循环，对每一种拨法，判断它是否离两个给定密码中的任意一个足够近。

判断“环形距离”有一个通用写法：对每一位计算直线距离d = abs(a - b)，如果d ≤ 2，当然合法；如果d > 2，再看N-d是否 ≤ 2。因为拨号盘上从a往另一个方向绕一圈也能到b，N-d就是那个方向的距离。两者取小，只要min(d, N-d) ≤ 2就满足条件。这里有个小细节：当N比较小时（比如N=3或N=4），同一个差可能会有多条路径，但取min永远是对的。

想确认自己理解对了，可以手动验证一个极端例子：N=2时，数字只有1和2，环上任意两个数的距离都是1，所以任何三位组合都能开锁。你拿公式代一下就会发现，任意差d，要么是0，要么是1，N-d也总是1或0，永远≤2，结论正确。这类特殊数据在比赛前一定要自己造出来测一测，能省下大把查错时间。

2.3 为什么说这种题最能筛人

模拟题往往是整套试卷的得分题，但USACO专门用它卡人，方法就是埋两个坑。

第一个坑是漏掉环形。很多选手看到N≤100就直接写abs(a-b)≤2，完全没想过1和N是接上的。本地自测数据恰好N=100、两个密码差值都大于2时不报错，一旦真跑到N=10左右的边界数据就翻车。第二个坑是重复计数。两个正确密码之间如果有重合的合法区域，例如N=5时两个密码(1,1,1)和(2,2,2)，暴力判定用“或”连接、一个拨法只计一次，没问题；但如果有人想当然先算第一个密码的合法区数，再加第二个密码的合法区数，就重复了。最稳的办法就是老老实实对每个拨法判断一次，宁可慢，不可错。

提示：考试时候的第二步永远不是“想更快的算法”，而是“确认暴力解法结论正确、代码不会写错”。这道题你要做的就是认真把三重循环写出来，然后重点检查边界和环形差值。

2.4 完整代码

#include <bits/stdc++.h> using namespace std; int n; int key[2][3]; // 检查组合(x,y,z)是否与第id个密码环距<=2 bool close(int x, int y, int z, int id) { int cur[3] = {x, y, z}; for (int i = 0; i < 3; i++) { int d = abs(cur[i] - key[id][i]); if (d > 2 && n - d > 2) return false; } return true; } int main() { scanf("%d", &n); for (int i = 0; i < 2; i++) for (int j = 0; j < 3; j++) scanf("%d", &key[i][j]); int ans = 0; for (int x = 1; x <= n; x++) for (int y = 1; y <= n; y++) for (int z = 1; z <= n; z++) if (close(x, y, z, 0) || close(x, y, z, 1)) ans++; printf("%d\n", ans); return 0; }

这段代码的时间复杂度是O(N^3)，N=100时刚好100万次判断，每个判断的常数极小，在老OJ上跑起来零点几秒。空间上只有常数数组，几乎等于没占用。提醒一句：别为了省那三重循环去搞容斥公式，这道题容斥很容易算重复，暴力就是最优解法。

3. 第二题：混合牛奶——把贪心建立在排序之上

3.1 题意与数据范围

第二题也很有意思。约翰每天需要N加仑的牛奶来喂小牛，镇上M个农民都能供应，第i个农民的单位价格是p_i，最多能供应a_i加仑。约翰想用最少的钱买够N加仑，问最小总花费是多少。

这个题是白银组“排序+贪心”的典型代表。N最大可以到两百万加仑，M最多五千个农民，所以直接从最贵的买到最便宜的这种O(MN)的思路是肯定不行的，得想清楚决策顺序。这道题的数据范围摆在那，天然就在提示你：要么排序，要么二分，要么动态规划。而这道题的最优决策又格外直白——谁便宜就买谁的。

3.2 为什么按单位价格升序一定最优

贪心的核心不在于“我觉得这样省”，而在于“我能证明这样一定不会更差”。买牛奶这件事有个非常好的性质：一加仑牛奶和另一加仑牛奶在功能上完全等价，不存在“这个农民的牛奶更好喝所以要优先买”这种区别。那么如果存在一个最优方案，它没有先买价格最低的农民，而是先买了某个更贵的农民，我就可以把方案里那一加仑换成从最便宜那个农民处购买，总花费只会变少，不会变多。

这种“交换论证”是在白银组就该养成的习惯。以后到黄金组遇到更复杂的贪心，比如区间调度、哈夫曼编码，证明思路都是一脉相承的：假设最优解和我们贪心选择的方案不一样，然后通过交换元素说明两种方案花费相同或更好。备考的时候一定要把“为什么贪心是对的”当回事，别停留在背模板。

3.3 结构体排序与桶数组两种实现

最常见写法是开一个结构体数组，存p和a，按p从小到大排序，然后从前往后买。能买多少就买多少，直到凑够N加仑。

还有一种情况适合开“桶”：如果p_i的取值范围很小（比如价格都在0到1000之间），就不需要排序了，直接开一个1001大小的数组cnt[price]统计每个价格下总供应量，然后从0到1000循环。这种方式写起来更短，而且完全不需要比较函数。2008年那会儿题目里的p_i范围我记得在0到1000以内，所以这两种写法都能过。万一你遇到的版本数据更乱，结构体排序更稳妥。

3.4 本地对拍：一个在考场外帮你抓错的办法

这道题虽然简单，但我在备考阶段养成了一个非常好的习惯：用对拍来验证贪心正确性。具体做法是写两个程序，一个是我认为正确的贪心解法，另一个是完全暴力的枚举解法——对这道题而言，暴力可以写成递归枚举每个农民买多少，或者在数据范围足够小时尝试所有购买组合。然后用一个随机数据生成器反复产生小数据，把两个程序的结果对比，一旦出现不一致，说明其中有个程序想错了。

对拍的价值在于，它能用几百次随机测试代替你的“我觉得没问题”。尤其是贪心题，思路上的漏洞往往藏在极端数据里，比如价格相同但供应量不同、总价格一样但组合不同，这些情况靠手算根本测不完。不过要记住，对拍只是验证工具，真正的依据还是你脑子里的交换论证。两条腿走路，才能放心提交。

3.5 易错点与提交经验

这道题的坑点主要有三个。第一个是总花费可能超过int范围：N最大两百万，单价最高一千，乘积就是二十亿，刚好卡在int边界上，再加一点就可能溢出。我建议任何涉及“总”的中间和最终结果都开long long，这道题里我用的是long long来存cost。第二个是while(scanf("%d%d", &N, &M) != EOF)这个标准读入写法，2008年的USACO月赛是多测试点风格的，读一次测一组，别漏掉循环。第三个细节：买的时候不能假设某个农民全部供应量都要，得用min(need, farmer.amount)来取。

3.6 完整代码

#include <bits/stdc++.h> using namespace std; struct Farmer { int price; int amount; }; const int MAXM = 5005; Farmer farmers[MAXM]; bool cmp(const Farmer& a, const Farmer& b) { return a.price < b.price; } int main() { int N, M; while (scanf("%d%d", &N, &M) != EOF) { for (int i = 0; i < M; i++) scanf("%d%d", &farmers[i].price, &farmers[i].amount); sort(farmers, farmers + M, cmp); int need = N; long long cost = 0; for (int i = 0; i < M && need > 0; i++) { int take = min(need, farmers[i].amount); need -= take; cost += 1LL * take * farmers[i].price; } printf("%lld\n", cost); } return 0; }

复杂度是O(M log M)，主要是排序的代价，M最大五千，老OJ上毫无压力。如果换成桶数组写法，复杂度能降到O(maxPrice + M)，但排序那种更通用，建议掌握排序版本。

4. 第三题：数水塘——DFS Flood Fill的边界思维

4.1 题意与数据范围

第三题是一个经典的连通块问题。约翰有一片矩形牧场，被划分成R行C列的小格子，每个格子要么是陆地'.'，要么是积水'W'。一场大雨之后，他想知道自己牧场上一共有多少个互不相连的水塘。两个相邻的'W'格子（包括上下左右和四个斜对角）属于同一个水塘。

数据范围我记得是R和C最大不超过100，格子总数不超过10000。这决定了你用什么遍历方式都无所谓，只要逻辑对就能过。所以这道题的重点不是性能，而是你能不能一次写对边界条件。

4.2 用DFS还是BFS

连通块计数有两种完全等价的路子：深度优先搜索（DFS）和广度优先搜索（BFS）。这道题用DFS会更顺手，因为不用维护队列，递归函数天然地把“从一个点出发把所有连着的点都标记完”这件事表达得特别直白。BFS当然也能写，但对于这种没有最短路需求的连通块个数统计，DFS代码量更少，调起来也更快。

我自己的习惯是：遇到这种“数连通块数量”的题，直接用DFS。但如果题目问的是“从起点到终点的最短距离”之类的问题，才需要认真考虑BFS。判断标准其实很朴素：你只是要“标记并区分”，还是要“计算距离”。

4.3 八方向遍历的实现

核心是两件事：方向数组和防重。方向数组把八个方向的偏移量写死，然后用一个for k遍历；防重用visited二维数组，进DFS的第一个动作就是标记vis[x][y] = true，而不是在枚举邻居时判断进没进过。这个顺序很重要，如果先递归再标记，同一个格子可能被重复递归很多次，虽然答案大概率还是对的，但白白增加不少常数，万一数据大一点就超时。

八个方向判断斜对角有个小坑：上下左右和斜对角是同时算的，边界越界条件必须四个方向都检查完整。我见过不少人因为只写了左边界检查右边界忘写，导致数组越界，老OJ报“Runtime Error”卡半天。

4.4 完整代码

#include <bits/stdc++.h> using namespace std; const int MAXRC = 105; int R, C; char grid[MAXRC][MAXRC]; bool vis[MAXRC][MAXRC]; int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1}; int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1}; void dfs(int x, int y) { vis[x][y] = true; for (int k = 0; k < 8; k++) { int nx = x + dx[k]; int ny = y + dy[k]; if (nx < 0 || nx >= R || ny < 0 || ny >= C) continue; if (vis[nx][ny] || grid[nx][ny] != 'W') continue; dfs(nx, ny); } } int main() { scanf("%d%d", &R, &C); for (int i = 0; i < R; i++) scanf("%s", grid[i]); int ponds = 0; for (int i = 0; i < R; i++) for (int j = 0; j < C; j++) if (grid[i][j] == 'W' && !vis[i][j]) { ponds++; dfs(i, j); } printf("%d\n", ponds); return 0; }

说一个老OJ的输入坑：用scanf("%s", grid[i])读取字符串时可以自动跳过每行的换行符，但是如果用getline，记得处理上一行末尾的\n。当年我在这个细节上卡过一次，本地数据都对，交上去第一格就Wa，最后发现是读入把空行当成了真实内容。

4.5 扩展：如果R和C大到1e6怎么办

白银组大概率不会考到这个规模，但如果你准备冲黄金，可以提前知道：当格子总数超过递归栈能承受的范围时，DFS会爆栈，那时候就乖乖换成BFS，用queue配合visited数组来做。思路是完全一样的，只是把递归栈换成了显式队列。下面是一个BFS替换DFS的核心片段：

queue<pair<int,int>> q; q.push({sx, sy}); vis[sx][sy] = true; while (!q.empty()) { auto [x, y] = q.front(); q.pop(); for (int k = 0; k < 8; k++) { int nx = x + dx[k], ny = y + dy[k]; if (nx < 0 || nx >= R || ny < 0 || ny >= C) continue; if (vis[nx][ny] || grid[nx][ny] != 'W') continue; vis[nx][ny] = true; q.push({nx, ny}); } }

注意BFS里入队之前就要立刻标记vis，否则同一层扩展时可能重复入队同一个格子。

5. 第四题：数字三角形——白银组的DP分水岭

5.1 题意与数据范围

最后一道题是数字三角形。约翰站在一个由整数组成的三角形顶端，第i行有i个数，他每次只能向下走到正下方或者右下方一格，直到走到底部。问他能收集到的数字之和最大是多少。R最大可以到1000，所有数字都是0到99之间的整数。

这道题在USACO里可以说是DP入门的“开山题”，白银组拿它来作为压轴再合适不过。它考的不是高级技巧，而是你脑子里有没有“状态”这个概念。很多人在这个地方第一次体会到什么叫“把大问题拆成小问题”。

5.2 为什么贪心在这里是错的

如果你第一次见这道题，很容易想出一个看起来很合理的贪心：从顶端出发，每往下走一步就选两个里比较大的那个数字接上，最后得到的路径和应该很大。这个想法错在忽略了“当前局部最优会把后面的大数字全部错过”。

我举个例子：三角形第一行是5，第二行是1和100，第三行是1000、0和0。从上往下走，第一行5接1可以到第三行的1000，但如果第二行选100，第三行就只能接0和0。显然选1才更好，可只看第二步，谁都想不到去选那个小一点的1。这种“为了远处更大的收益接受眼前小损失”的决策，贪心永远做不了，必须把全局情况摊开算。

5.3 状态定义：从顶推还是从底推

入门动态规划最经典的一句话叫“定义状态，写出转移方程”。这道题的状态可以定义成dp[i][j]：从第i行第j列这个位置出发，走到三角形底部能获得的最大数字和。那么从位置(i,j)出发，你可以去(i+1,j)或者(i+1,j+1)，所以：

dp[i][j] = tri[i][j] + max(dp[i+1][j], dp[i+1][j+1])

换句话说，当前位置的最大收益，等于当前位置的数字加上下面两个选择里更大的那个收益。算出这个方程并不难，难的是想通“从底部往上算”这件事。因为底部的每个位置（第R行）都只有一个选择，dp[R][j] = tri[R][j]直接就有值，然后往上倒推一行就能推出倒数第二行，再往上推，一直推到dp[1][1]就是答案。

我当年学DP的时候卡在这个“倒着看”上很久。后来自己手动把一棵很小的三角形画出来，从底部一行一行往上标数字，标了几遍才真正明白：动态规划并不是真的在“走”，而是在“已知下一步结果的基础上做当前决策”。这个思维一旦扭转过来，白银组的DP题基本就打通了。

5.4 滚动数组优化与原地更新

如果你开一个1000×1000的二维dp数组，内存大概4MB，完全没问题。但USACO的题通常喜欢让你想一个更省空间的写法：因为求dp[i][j]只需要用到dp[i+1][j]和dp[i+1][j+1]，也就是只依赖下一行，那么完全可以在原数组tri上直接原地累加，从倒数第二行开始，tri[i][j] = tri[i][j] + max(tri[i+1][j], tri[i+1][j+1])。最后答案就是tri[1][1]。这样连dp数组都不用开，代码短一截。

5.5 完整代码

#include <bits/stdc++.h> using namespace std; const int MAXR = 1005; int tri[MAXR][MAXR]; int main() { int R; scanf("%d", &R); for (int i = 1; i <= R; i++) for (int j = 1; j <= i; j++) scanf("%d", &tri[i][j]); for (int i = R - 1; i >= 1; i--) for (int j = 1; j <= i; j++) tri[i][j] += max(tri[i + 1][j], tri[i + 1][j + 1]); printf("%d\n", tri[1][1]); return 0; }

注意数组下标从1开始，这样tri[i][j]下一次访问tri[i+1][j+1]时不会出现j+1越界的问题，而且边界判断少很多，代码出错概率低。这是我在备考阶段慢慢固定下来的一个小习惯：能用1下标的地方尽量用1下标，尤其涉及对角线访问时，好处非常明显。

如果你觉得从底往上推容易懵，还有一种等价的写法是记忆化递归：先写一个递归函数solve(i,j)，初始化memo数组为-1，在函数里如果memo[i][j]已经算过就直接返回，否则递归往下计算并记录。这种写法更接近人的直觉，代价是栈空间占用更大。对R=1000来说两种都能过，我建议两种都写一遍，能帮你加深对DP的理解。

6. 把这套题刷透之后：白银组升段要补齐的能力清单

6.1 四道题串起来的三种能力

把这四道题放在一起看，白银组真正想考察的其实就三件事。

第一，读题能力。第一题的环形距离、第三题的八方向相邻、组合锁里两个密码都合法，这些都属于“题目明明写了，但你没看到”的坑。USACO的题目从来不会在文字上为难你，它只会把话说得特别严密，而你在考场上的任务就是把每一句都翻译成代码逻辑，一条不能漏。

第二，暴力到优化的判断力。第一题和第三题，你完全可以靠暴力和朴素DFS通过；第二题需要排序后贪心；第四题必须建立状态转移。这里面的梯度非常重要：不是每道题都需要高级算法，你要能判断“这道题数据这么小，直接模拟就行”和“这道题数据这么大，必须想贪心或DP”。

第三，调试和边界处理能力。四个坑值得反复记：环形距离的取min、贪心取货时的min、DFS的越界四向检查、DP数组下标从1开始。这些细节单独拿出来都不难，但在一个半小时的比赛里全部处理对，就是经验的积累。

6.2 我从这套题里总结的备考节奏

如果你现在正卡在白银组，我的建议是先别急着上黄金组的题。把USACO历年白银组按年份刷过去，每一套题都给自己限时两个半到三个小时，完全不看题解，交上去拿到反馈后再复盘。复盘时重点不是“我ac了没”，而是“我当时的思考路径哪里出了问题”——是没读懂题，还是想不到用排序，还是想到了DP但方程写错。这种复盘比多刷十道新题都管用。

我个人对这套题印象最深的就是第四道数字三角形。那阵子我连续卡了快两周，后来用最笨的办法：把R=5的小样例手推了七八遍，从底部一行一行往上标最大值，直到某一次突然醒悟“原来每一步都是在用已知的下层结果做决策”。从那以后，白银组的DP题再也没成为我的障碍。这种顿悟没法靠看题解获得，只能靠一遍遍亲手算、亲手写。

最后说一个很多初次接触英文题面的选手容易忽略的细节：USACO的题目描述很长，但一大半是背景故事，真正影响答题的数字、条件和约束都集中在Input和Output部分。拿到题目先看输入输出约束，再回头对照故事理解场景，会节省大量时间。另外，USACO月赛一直是标准输入输出，但Training Gateway里的老题要求写文件读写，备考时两种模式都练一练，别到赛场上才发现自己只会读文件。