从USACO历年白银组里挑一套用来练“模型转换”的真题2019年2月这场一定排得上号。整套题没有一道需要背高级模板但每道题都在逼你完成一次关键翻译三头牛的移动问题要翻译成间隔拆分矩形涂色问题要翻译成二维差分种草限制问题要翻译成二分图染色。这种翻译能力恰恰是Silver晋级Gold最缺的东西。这篇文章把三道题从头到尾拆开讲包括我当年踩过的边界坑、给学生讲题时反复强调的细节以及可以直接抄走的代码框架。正在备考USACO白银组的选手或者刚接触算法竞赛想系统刷题的人都可以把这套真题当作一次完整的复盘训练。1. 2019年2月白银组全景这套题到底在考什么1.1 三道题的知识点分布与难度印象先把三道题摊开看。题号题名核心考点实现难度思维难度1Herding贪心/构造低中高2Painting the Barn二维差分中低低3Revegetation二分图判定与计数中中这个分布很有意思。Painting the Barn是最“标准”的一道只要你见过二维差分基本就是送分Revegetation是典型的图论基础题考的是二分图判定的变形Herding则是全场区分度最高的一道代码只用几行但如果没有把问题抽象成间隔模型很容易在最多移动次数上卡死。我见过不少考生在Herding上耗掉一个小时然后Painting没时间检查边界Revegetation又漏了孤立点。所以本场的核心策略是先把套路题稳稳吃掉再回头啃构造题。Silver组的题目通常不会考特别冷门的算法但非常考验“看到什么条件联想到什么工具”的反应速度这一点在这套题里体现得淋漓尽致。1.2 建议的做题顺序与时间分配如果让我重新打这场我会按 Painting the Barn → Revegetation → Herding 的顺序做。原因很简单Painting是纯套路题看到坐标范围只有1000×1000差分的信号已经很明确15分钟内可以写完并验证Revegetation的DFS染色也不难20分钟能拿下最后把剩余时间留给Herding用它做思维冲刺。USACO一场Silver通常是4小时3题时间上很充裕但前提是不在一道题上死磕。Herding如果想了30分钟还没有头绪先跳过去写满其他两题的满分代码再回头想往往效果更好。这也是一个很重要的竞赛习惯比赛的分数分布决定了你不可能每题都拿满但两题保底加一题突破往往是白银组升黄金组最稳的策略。2. Herding从“移动奶牛”到“拆分间隔”的关键一跳2.1 先把问题压缩成两个间隔题目背景不复杂数轴上有三头牛位置分别是abc。每次选最左边或最右边的牛移到另外两头之间的任意整数位置。问最少多少次、最多多少次能让三头牛占到连续的三个位置。很多人一上来就在坐标轴上模拟移动把位置画来画去这样很容易乱。我的建议是不要看奶牛只看间隔。设x b - ay c - b那么初始状态就是两个正整数(x, y)。目标状态是(1, 1)也就是三头牛相邻。一次移动对应什么如果移动左端点a它必须落到b和c之间那么原来x b - a这个间隔被丢弃而y c - b这个间隔被拆成两个新间隔比如(p - b)和(c - p)。所以移动左端点等价于把y拆成两个正整数u v新状态变成(u, v)。同理移动右端点c等价于把x拆成两个正整数u v新状态变成(u, v)。举个例子初始位置是1、4、10两个间隔是(3, 6)。如果移动左端点1到位置5新的三头牛是4、5、10间隔变成(1, 5)。你会发现原来的间隔3消失了6被拆成了1和5。这个转换看起来不起眼但它是整道题的钥匙。之后所有结论都从这个状态转移出发。2.2 最少步数0、1、2三种情况的判定先说最少步数。如果x 1且y 1已经连续答案是0。如果x 2或y 2答案是1。比如间隔(2, 7)可以移动右端点把x 2拆成1 1得到(1, 1)一步完成。其他情况答案是2。为什么其他情况一定是2因为两步可以构造。第一步先把某个间隔拆出2来第二步再把这个2拆成1 1。比如状态(x, y)且y 2移动左端点把y拆成(y - 2, 2)得到新状态(y - 2, 2)再移动对应端点把2拆成1 1完成。如果y 1那就去拆x同样成立。所以最少步数不需要BFS不需要DP直接判断两个间隔是否等于2就够了。这里有个容易混淆的点有人会以为“只要有两个相邻就能在一两步内完成”但题目要的是三头全部连续所以看的是两个间隔中是否存在一个等于2而不是看奶牛之间是否已经有一对相邻。2.3 最多步数为什么答案是max(x, y) - 1最多步数比最少步数有意思。从状态转移可以看出每走一步当前的(x, y)会变成一个全新二元组这个新二元组等于被拆的那个间隔的拆分结果。要让整个过程尽量长自然应该每次都去拆较大的间隔并且拆成1和(大间隔-1)。这样新状态里总有一个数是1另一个数比原来大间隔小1可以继续拆。如果初始是(x, y)设大间隔为m max(x, y)。第一步把m拆成1和m - 1之后的新状态是(1, m - 1)或(m - 1, 1)接下来只能拆m - 1依次得到(1, m - 2)、(1, m - 3)……直到(1, 1)。总步数就是m - 1。还是用(3, 6)来推初始大间隔是6把它拆成1和5得到(1, 5)然后拆5得到(1, 4)再拆4得到(1, 3)再拆3得到(1, 2)最后拆2得到(1, 1)。一共5步正好等于max(3, 6) - 1。这里有个特别容易踩的直觉陷阱每一步跨度都会严格变小最终跨度是2所以有人会猜最多步数是初始跨度减2。但实际答案是max(x, y) - 1而不是(x y) - 2。原因在于每次移动不是只让跨度减1而是把其中一个间隔直接吞掉另一个间隔被重新拆分。这道题的构造性很强建议自己拿几个数据手推比如(3, 6)按上面策略能走出5步如果按跨度减2算会得到7步但7步是达不到的。2.4 Herding的参考代码与易错点#include bits/stdc.h using namespace std; int main() { int a, b, c; cin a b c; int x b - a; int y c - b; int mn; if (x 1 y 1) mn 0; else if (x 2 || y 2) mn 1; else mn 2; int mx max(x, y) - 1; cout mn \n mx \n; return 0; }代码就这么短。需要注意两点。第一看清输出顺序。原题要求先输出最少移动次数再输出最多移动次数但有些转载版本的题目可能顺序不同写代码前一定确认题面。第二不要对mx做特殊判断。如果初始已经连续x y 1max(x, y) - 1 0公式依然成立不需要额外特判。我当时第一次做这题就是没转换成间隔模型在最多步数上写出了跨度减2的错误结论交上去连样例都过不了。所以我现在给学生讲这题一定会强调先写状态转移再推结论不要凭直觉猜。3. Painting the Barn1000×1000网格上差分数组的边界艺术3.1 看到固定小网格第一反应就应该是差分Painting the Barn的题面是N个矩形覆盖在一块1000×1000的围栏上求被恰好覆盖K次的面积。N可以很大坐标范围却只有0到1000。这个“小网格”条件基本就是明示了二维差分。你可能第一反应是离散化或扫描线但这题里完全没必要。1000×1000只有100万个格子用差分数组把每个矩形的覆盖贡献拆到四个角上再做一遍二维前缀和就能在O(N 10^6)的时间里算出每个格子被覆盖了几次最后扫一遍统计等于K的格子数即可。一条实用的判断标准如果坐标范围是10^5级别优先想离散化或扫描线如果坐标范围只有10^3级别直接差分硬算。USACO特别爱出这种“数据范围暗示算法”的题养成这种条件反射很值钱。很多选手不是不会差分而是不知道什么时候用差分这需要通过大量真题去磨合。3.2 差分数组的边界细节半开区间与数组大小二维差分本身不难难在边界。题目一般用(x1, y1)表示矩形左下角(x2, y2)表示右上角覆盖的是[x1, x2) × [y1, y2)这个半开区间。也就是说左下角这个格子算被覆盖但右上角坐标为x2或y2的格子不算。这样定义的好处是正好和差分操作匹配diff[x1][y1]; diff[x2][y1]--; diff[x1][y2]--; diff[x2][y2];我用简化表达时习惯记成“左上加、右上减、左下减、右下加”但实际位置取决于你把这个矩形放在坐标系里的朝向。比如一个矩形左下角是(1, 2)右上角是(4, 5)那么差分操作就是在(1, 2)加1(4, 2)减1(1, 5)减1(4, 5)加1。建议每次写代码前把四个点标在草稿纸上比自己硬背口诀稳。真正容易爆的是数组大小。因为x2和y2可以等于1000做差分时diff[x2][y1]--这里的1000是合法下标所以数组至少要开1001×1001。如果你图省事开成1000×1000矩形的右上角一旦贴到边界就直接越界。本地跑得好好的评测机上一片RE这种问题最让人崩溃因为报错位置和逻辑错误完全无关。统计答案的时候只统计i和j都在[0, 999]范围内的格子。i 1000或j 1000那一整条是差分操作的“外部缓冲区”不是围栏面积不能算进去。如果把边界行和边界列也算进去答案会凭空多出一部分而且只有贴边矩形多的时候才明显用样例很难发现。3.3 Painting the Barn的参考代码与复杂度#include bits/stdc.h using namespace std; const int MAXC 1000; int diff[MAXC 2][MAXC 2]; int main() { int N, K; cin N K; for (int i 0; i N; i) { int x1, y1, x2, y2; cin x1 y1 x2 y2; diff[x1][y1]; diff[x2][y1]--; diff[x1][y2]--; diff[x2][y2]; } // 先做列方向前缀和再做行方向前缀和 for (int i 0; i MAXC; i) { for (int j 1; j MAXC; j) { diff[i][j] diff[i][j - 1]; } } for (int i 1; i MAXC; i) { for (int j 0; j MAXC; j) { diff[i][j] diff[i - 1][j]; } } long long ans 0; for (int i 0; i MAXC; i) { for (int j 0; j MAXC; j) { if (diff[i][j] K) ans; } } cout ans \n; return 0; }复杂度是O(N 1000^2)空间O(1000^2)。N哪怕到10^5也毫无压力。最后提醒一个实用小技巧如果你担心差分符号搞混可以写一个暴力统计的小数据生成器随机生成几个矩形用二维数组直接累加和差分结果对拍。这种对拍在USACO风格的题目里非常好用尤其是Painting这种实现细节容易漏的题。随机数据对拍比自己脑补样例靠谱得多因为很多边界情况是脑补不出来的。4. Revegetation两种草色背后是二分图的连通分量计数4.1 把“草要不同”建造成一张约束图Revegetation的题面是N块牧场两种草M条限制每条限制说某两块牧场必须种不同的草问有多少种分配方案。这是一个非常典型的“把逻辑约束翻译成图”的题目。把每块牧场看成节点每个限制看成一条边那么“草不同”就等价于“相邻节点的颜色不同”。两种草就是两种颜色。于是问题变成给一张无向图染色只有两种颜色要求每条边两端颜色相反求染色方案数。这个变换不难但很多人会漏掉后半句求方案数。如果只是判断有没有解DFS判一下二分图就够了。但题目要的是方案总数所以还要考虑每个连通分量的独立性和可翻转性。4.2 DFS染色判断可行性并统计连通分量对每个未染色的节点启动一次DFS把它的颜色设为0邻居颜色全部设为1 - c。如果某个邻居已经被染成和当前节点相同的颜色那就说明图中存在奇环整个问题无解方案数为0。如果整张图都能顺利染色答案就是2的连通分量个数次方。为什么因为每个连通分量内部只要确定了任意一个节点的颜色其他所有节点的颜色就被边的关系唯一确定了。反过来把一个连通分量的所有颜色同时翻转仍然满足所有限制所以每个连通分量都有两种合法状态。不同连通分量之间没有边约束互相独立方案数相乘。于是得到2^(连通分量个数)。这里特别容易漏的是孤立点。一块没有任何限制的牧场它自成一个连通分量颜色可以任选也要乘2。我在给学生改代码的时候经常看到有人只统计了有边的连通分量导致答案少乘2。孤立点在遍历时其实会被color[i] -1这个条件自然捕获问题只在于你有没有意识到它也是一个分量。如果图里有奇环那整个答案直接是0。比如三个牧场两两互相限制三个节点形成一个三角形二染色无论如何都会冲突这就是典型的无解情况。4.3 Revegetation的参考代码与实现细节#include bits/stdc.h using namespace std; const int MAXN 100005; const long long MOD 1000000007; vectorint g[MAXN]; int color[MAXN]; bool ok true; void dfs(int u, int c) { color[u] c; for (int v : g[u]) { if (color[v] -1) { dfs(v, c ^ 1); } else if (color[v] c) { ok false; } } } int main() { int N, M; cin N M; for (int i 0; i M; i) { int u, v; cin u v; g[u].push_back(v); g[v].push_back(u); } memset(color, -1, sizeof(color)); int comps 0; for (int i 1; i N; i) { if (color[i] -1) { comps; dfs(i, 0); if (!ok) break; } } if (!ok) { cout 0 \n; } else { long long ans 1; for (int i 0; i comps; i) { ans ans * 2 % MOD; } cout ans \n; } return 0; }几个实现细节值得说。第一颜色数组初始化为-1表示未访问。DFS里用c ^ 1代替1 - c位运算快一点更重要的是不容易写错。第二数据范围大的时候DFS递归深度可能到10^5。USACO评测环境通常允许较深的递归但如果你在本地用默认栈或换到别的OJ可能会爆栈。稳妥方案是把递归改成显式栈的BFS或者干脆用队列写BFS染色。代码逻辑完全一样只是把递归换成循环。第三关于输出。答案可能是指数级的如果题面要求取模按模乘就行如果没给模数你要特别注意N的范围是否大到无法完整输出。按USACO的出题习惯这种题要么会给模数约束要么数据范围小到可以完整输出写代码前先确认这一点。我自己的习惯是即使题面没明说也会先把MOD常量和取模运算写好因为加一个取模不会影响正确性但能防止自己在大数情况下翻车。5. 复盘与后续训练从Silver到Gold还差什么5.1 本场最值得复盘的四类失分点把这套题做完我建议你专门复盘以下四类问题它们在本场出现频率很高。第一Herding的最大步数凭直觉猜。很多人会写成初始跨度减2因为“每一步跨度至少减1”这个约束没错但没考虑到每一步实际上会吞掉一个间隔。这类构造题必须用状态转移或者小规模暴力验证不能只靠上界猜答案。第二Painting的差分数组开小。这几乎是USACO差分题的头号杀手。记住差分操作需要访问x2、y2的坐标而它们可以等于1000所以数组至少1001×1001宁可多开一点也不要卡着边界开。第三Revegetation漏掉孤立点。方案数是2的连通分量次方孤立点也算连通分量。判二分图时从每个未访问节点开始DFS正好天然把孤立点算了一次只要你没有额外跳过它。第四时间分配失衡。本场最简单的Painting和Revegetation如果加起来超过50分钟说明平时对二维差分和DFS染色还不够熟练。Silver阶段的套路题应该在20分钟内稳定拿下才能给构造题留出思考时间。5.2 后续刷题方向建议如果这三道题你都能独立做出来那Silver基础已经很扎实了。接下来想冲Gold我建议往两个方向延伸。一个方向是在图论上加深。Revegetation只是两种颜色的二分图判定Gold级别会考到更复杂的带权并查集、生成树计数、缩点等。你可以把USACO同月的Gold版Revegetation拿出来对比看看同样的背景是如何升级限制条件的这会帮你理解算法竞赛里“加一个条件 换一个算法”的演变逻辑。另一个方向是数组技巧的泛化。Painting the Barn用的是二维差分Gold里可能换成扫描线、线段树维护矩形覆盖或者三维体覆盖的差分扩展。理解“覆盖次数”这类问题本质上是区间加法和查询这些基础模型要练熟。最后分享一个我自己的复习习惯。刷完一套USACO真题不要马上看题解先自己写一份考后总结内容包括每道题的核心模型是什么、我卡在哪里、如果重来一次用什么顺序做。过两周再把这道题拿出来在不看代码的情况下重新实现一遍。这个过程比刷十道新题还管用我对Herding的间隔模型印象这么深就是因为当年狠狠吃过亏。