USACO白银组真题我前前后后刷过不少每次有人让我推荐练手材料我都会把2009年11月这场翻出来。很多人做USACO历年真题有个毛病只盯最近一两年的题觉得老题没价值。但这场白银组的题恰好卡在“语法已经会了算法思维刚开始建”这个位置上三道题分别覆盖区间模拟、网格连通块和背包DP难度分布非常典型。如果你在冲黄金组或者想用算法题补大厂笔试的基础能力这场题建议完整做一遍。下面按我复盘时用的复述版本把三道题拆开讲附上可直接提交的代码和当年容易踩的坑。1. 整体设计与解题思路拆解1.1 白银组到底在考什么USACO的分组逻辑很清晰铜组考你会不会写程序白银组考你会不会设计算法黄金组考你算法库全不全。2009年11月这套白银组题正好把白银组的“分水岭”性质体现得特别明显。三道题没有一道需要高级数据结构但每一道都要求你先从题目描述里抽出本质再选择合适的算法而不是拿到题就从头到尾硬模拟。第一题本质是“多次区间操作后的单点查询”第二题本质是“二维网格上的连通块计数”第三题本质是“有限预算下的最优选择”。这三种模型到现在仍然是各类笔试和竞赛的高频考点。我当时把这套题做完之后最大的感受是老题虽然题面土考点一点不过时。1.2 做题顺序与时间分配建议这场题按我的经验建议自己掐时间按150分钟练习。第一题控制在30分钟内第二题35分钟内第三题40分钟内剩下时间检查边界和文件读写。先别急着看数据范围就开写把三题都读一遍按“模拟题、图论题、DP题”分类心里有底再动手。做题顺序我建议从第二题开始因为连通块计数写起来套路固定不容易翻车。然后把第一题做了最后集中精力死磕背包。当然这只是我的习惯如果你对模拟题更顺手按自己节奏来也行但一定要留出至少20分钟复查。注意老USACO题库有个特色输入输出文件名经常要求是 input.txt 和 output.txt新平台则不做要求。提交前先确认题目说明别因为文件读写问题白交几发。2. 第一题区间重排模拟2.1 题目复述与数据范围这一场的第一题我按常见的复述版本整理下来是这样给定N个整数排成一列接下来有M次操作每次操作给出一个区间[l, r]和一个标志op。op为0时把区间内的数按从小到大重新排序op为1时把区间内的数按从大到小重新排序。所有操作结束后有Q次询问每次问当前第x个位置上的数是多少。数据范围我给的是N、M不超过5000Q不超过10000每次区间满足1≤l≤r≤N。这个范围不算大但也别小看它如果每次操作都用最笨的办法把整段区间复制出来再插回去复杂度会非常难看。2.2 朴素做法为什么能过看到这道题第一反应是“每次把区间的数字拿出来排个序再放回去”。用C的sort可以轻松做到核心就是区间下标转换。假设数组用0下标存储读入的l和r要先减1然后对 a.begin()l 到 a.begin()r1 这一段排序因为sort的结束迭代器是开区间所以r要加1。每次操作复杂度是O(L log L)L是区间长度M次操作下来整体是O(M * N log N)在N和M都是5000的情况下最坏也就几千万次比较运行时间完全没问题。我当时还担心会不会超时实测下来老题的数据比较温和暴力排序就能全过。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, q; // 老题若要求文件读写就把下面两行取消注释 // ifstream fin(input.txt); // ofstream fout(output.txt); cin n m q; vectorint a(n); for (int i 0; i n; i) cin a[i]; while (m--) { int op, l, r; cin op l r; --l; --r; // 转为0基下标 if (op 0) { sort(a.begin() l, a.begin() r 1); } else { sort(a.begin() l, a.begin() r 1, greaterint()); } } while (q--) { int idx; cin idx; cout a[idx - 1] \n; } return 0; }2.3 这道题真正想考察的点很多人觉得这题就是个sort套娃没啥技术含量但实际上它有三个隐藏考点。第一个是下标换算。USACO的老题习惯用1基下标描述区间而C的sort是0基半开区间这个转换一旦出错要么WA要么RE。第二个是sort的边界语义begin()r1必须写对少一个位置就会把最后一个元素漏掉。第三个是稳定性和辅助空间的权衡虽然这题用sort没问题但如果数据量放大到十万级同样的思路就得换成分块或线段树那时候才是真正的算法题。所以白银组考试很多时候不是考你会不会某个高级算法而是考你在简单模型下能不能把代码写对。这一题能帮你把“区间操作”这个基础概念打牢后面学线段树、树状数组都会用到。3. 第二题网格连通块计数3.1 题目复述与输入细节第二题是个典型的二维网格题。题面说的是在一片H行W列的矩形区域里有些格子里有太空碎片用字符*表示空地用.表示。如果两个碎片格子上下左右相邻就属于同一片碎片区域。问整个区域里有多少片独立的碎片区。数据范围H和W乘起来最多25万个格子。这个题需要读入字符串因为输入里每行是一整串没有空格的字符不能用cin int直接处理。我见过不少人在这一步翻车写了半天逻辑结果读入就错了。3.2 DFS版本与递归风险连通块计数最自然的做法是挨个格子扫描遇到没访问过的碎片就开启一次深搜把所有相邻碎片都标记掉计数器加一。DFS代码写起来很短这也是大多数人最先想到的方案。但25万个格子的规模用递归DFS是有风险的。极端情况下整张图全是碎片递归深度可能达到25万层C默认栈空间不够直接爆掉。虽然很多评测环境不会真踩到那个极限但比赛中没必要赌这个。如果你想练DFS没问题比赛时更推荐BFS。3.3 BFS版本为什么更稳BFS用队列保存待扩展的点不存在递归深度问题写起来也不复杂而且思路和DFS完全一样从入口点出发向上下左右四个方向扩散把能走到的点全部标记。这里有一个特别重要的细节标记访问状态要在入队的时候做不是在出队的时候做。如果出队才标记同一个点可能被多个邻居重复入队队列膨胀最坏情况会超时。这个坑我早期踩过不止一次后来养成了习惯凡是BFS一律在push之前先vis[nx][ny] true。#include bits/stdc.h using namespace std; const int dx[4] {-1, 1, 0, 0}; const int dy[4] {0, 0, -1, 1}; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int H, W; cin H W; vectorstring grid(H); for (int i 0; i H; i) cin grid[i]; vectorvectorbool vis(H, vectorbool(W, false)); queuepairint, int q; int ans 0; for (int i 0; i H; i) { for (int j 0; j W; j) { if (grid[i][j] * !vis[i][j]) { ans; q.push({i, j}); vis[i][j] true; while (!q.empty()) { auto [x, y] q.front(); q.pop(); for (int d 0; d 4; d) { int nx x dx[d]; int ny y dy[d]; if (nx 0 || nx H || ny 0 || ny W) continue; if (grid[nx][ny] ! * || vis[nx][ny]) continue; vis[nx][ny] true; q.push({nx, ny}); } } } } } cout ans \n; return 0; }3.4 别把行列读反了这道题还有一个很隐蔽的坑输入的第一行到底是“行 列”还是“列 行”。有的版本写H W有的版本写W H如果不仔细看题很容易把读入顺序搞反然后所有坐标判断全部错乱。我的习惯是先读入两个数然后按题面明确标注的变量名来存比如int rows, cols;这样后续代码就不容易绕晕。另外方向数组建议写成独立的dx和dy不要用pair数组不然循环里写起来很啰嗦还容易下标写错。边界判断统一写成nx 0 || nx rows || ny 0 || ny cols这个模板要背熟任何二维网格题都能直接套。3.5 拓展并查集思路如果你对并查集比较熟可以试试用并查集做连通块计数。把每个碎片格子的坐标映射成一维编号相邻的碎片格子做union最后统计有多少个根节点是碎片格子。这种写法在处理动态添加碎片、边加边询问的场景下比BFS灵活但静态图里BFS和并查集都能过。我个人建议第二题就用BFS练熟毕竟是白银组最常见解法以后打比赛也通用。4. 第三题背包型DP4.1 题目复述与数据范围第三题我复述出来是这个样子农夫有N种草料每种草料只有一袋第i袋的价格是p_i吃完能提供的能量是e_i。农夫手里最多能花V元问在预算内最多能获得多少能量。这就是经典0/1背包N不超过500V不超过5000。题目不算难但它是白银组里非常典型的DP题考察的是“状态设计”和“转移顺序”两个核心点。4.2 状态设计与转移方程定义dp[j]表示“预算不超过j时能获得的最大能量”。初始时dp[0]0其余dp值也为0因为什么都不买能量就是0。处理第i种草料时如果它价格是cost能量是value那么状态转移只有两种可能不买它那dp[j]保持不变买它那需要从预算中腾出cost并且这个人必须先在没有买当前物品的状态上加上value。所以转移方程写成dp[j] max(dp[j], dp[j - cost] value)这里的核心是第二维循环要从大到小。如果从小到大遍历j那么当j变大时dp[j - cost]可能已经在这一轮被更新过意味着同一袋草料被重复买了0/1背包就退化成完全背包了。这个区别是背包问题里最经典的考点笔试和竞赛都喜欢在这里挖坑。4.3 为什么必须倒序循环我举个生活中的例子帮你理解。假设你手里有一张100元预算的购物清单每种零食只有一份你想知道怎么买最划算。如果从预算低往高算你先算出10元能买什么再算20元时就会把“10元的结果”当作基础有可能把同一包零食算了两次。倒过来从100元往低算你更新大额预算时用的还是上一轮的小额结果天然避免重复购买。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, V; cin N V; vectorint cost(N), value(N); for (int i 0; i N; i) { cin cost[i] value[i]; } vectorint dp(V 1, 0); for (int i 0; i N; i) { for (int j V; j cost[i]; j--) { dp[j] max(dp[j], dp[j - cost[i]] value[i]); } } cout dp[V] \n; return 0; }同样的逻辑Python版本也很短适合平时练手n, v map(int, input().split()) cost [] value [] for _ in range(n): c, e map(int, input().split()) cost.append(c) value.append(e) dp [0] * (v 1) for i in range(n): for j in range(v, cost[i] - 1, -1): dp[j] max(dp[j], dp[j - cost[i]] value[i]) print(dp[v])4.4 背包问题的常见变体这题做完之后我强烈建议把变体也一起练了因为USACO后面经常考类似但不完全相同的题。完全背包就是把内层循环改成从小到大多重背包就是把每种物品拆成多件0/1背包或者用二进制拆分优化。还有一个高频变体是“恰好装满背包”此时的初始化要把dp[0]设为0其他位置设为负无穷只有能刚好凑出的预算才被更新最后判断dp[V]是否仍为负无穷。白银组考试不会把变体出得太深但在同一场里换一下约束条件很多人就会被绕进去。你可以自己改改数据比如每种草料有无限袋或者每袋除了价格和能量还有一个数量限制再用上面的模板跑一遍彻底吃透背包DP的来龙去脉。5. 常见问题与排查技巧实录5.1 老题文件读写问题USACO早期的题目无论铜组白银组经常要求从input.txt读入把结果写到output.txt。在本地测试时和在线评测时标准不一样第一件要做的事就是看题目顶部的说明。新平台一般用标准输入输出老题库则可能用文件读写。如果提交后发现全部WA先检查是不是忘了加文件重定向。freopen(input.txt, r, stdin); freopen(output.txt, w, stdout);这两行放在main开头即可。不少新手在本地用控制台测试的时候把这两行注释掉提交的时候又忘记打开一来一回就丢了大量时间。5.2 数组越界和递归栈溢出网格题里数组越界的典型表现是运行时错误但有时候系统不会直接给你RE而是出现内存污染导致某些点莫名WA。边界判断一定要写在访问数组之前顺序不能反。先判断坐标范围再访问grid[nx][ny]这个顺序错位是很多二维题的隐形杀手。递归DFS在25万规模下会爆栈我的建议是统一使用BFS。不要心存侥幸竞赛环境栈空间通常开得不大稳妥的代码才有竞争力。5.3 sort边界与下标转换区间排序题最常见的错误是结束迭代器写错。sort(a.begin()l, a.begin()r)只排了[l, r)这半开区间想排闭区间[l, r]必须写成a.begin()r1。白银组这种题WA一次多半就是这个原因。另外读入的区间是1基数组是0基转下标时记得l和r都要减1不要只减l不减r。5.4 背包细节背包题最容易出的问题有三个。第一内层循环顺序写反导致重复购买第二初始化全部为0导致“恰好装满”这类问法结果错第三数组开小了V最多5000你开个1000的数组跑越界都不一定报错但答案肯定不对。我整理了一个速查表做题前可以扫一眼问题典型症状排查方向文件读写遗漏本地正常提交全WA检查题目要求加freopensort区间右边界错某个元素没被排序确认r1写没写下标转换漏减一输出结果整体偏移一位检查l、r是否都转成0基BFS重复入队大数据点超时检查vis是否在push前标记行列读反连样例都对不上看题意是H W还是W H背包内层顺序反答案偏大确认j从大到小遍历数组开小部分测试RE按最大数据范围5开5.5 多组数据没清空有些变体题会给出多组测试数据如果使用静态数组上一组的数据没清空下一组就会带着脏数据跑。保险做法是每次Case开始重新创建vector让作用域替你管理生命周期。这是写任何竞赛代码都适用的小技巧。6. 复盘心得我第一次做这场题的时候第二题用的递归DFS数据点到一半直接栈溢出当时还不明白为什么本地小数据能过提交就崩。后来换BFS一遍过才知道递归深度这回事。还有一次在背包题里把内层循环写成了从小到大样例全过提交后错了一片查了半天才反应过来是重复选了同一个物品。这些错误都不是什么高深问题但白银组就是专门考这些基础细节。如果你现在能在一个半小时内把这场三道题全部一遍过大厂笔试里的基础算法题基本不会拖你后腿。这一场的老题面我按复述版本写的官方题号和名称可能有些出入但核心考点不会变对不上时按数据结构类型去匹配就好。