刷透USACO 2007黄金组：RMQ、最短路与贪心全解析

今天想聊一套我自己刷过不止一遍的老题——USACO 2007年1月黄金组真题。USACO的黄金组（Gold Division）在国内算法训练圈里地位一直很特殊，难度介于NOIP提高组和NOI之间，考察范围很明确：数据结构、图论、DP、贪心、字符串，基本就围着这几块打转。这轮月赛里的题，放到今天看虽然没有特别极端刁钻的思维题，但每一道都把经典算法考得相当扎实，非常适合用来检验自己对基础算法的掌握程度。

尤其适合这几类人：准备CSP-S/NOIP提高组的选手，想冲USACO黄金组但还没摸清题目风格的人，以及已经工作但想系统补一补算法底子的朋友。2007年1月这套题最大的特点是“算法很正”，没有太多歪门邪道，你只要把数据结构和图论的基础功打牢，很多题一旦看穿包装，剩下的就是模板活。这也是我把它反复拿出来讲的原因——刷套题不是你见过多少偏题怪题，而是能不能在有限时间内，把见过的经典模型快速匹配到新题上。

1. 2007年1月黄金组到底在考什么

1.1 套着奶牛外衣的经典算法

USACO的老题有个非常明显的特征：题目背景永远是农场、奶牛、牧场围栏，但剥掉这层壳，里面全是教科书级别的算法模型。2007年1月这套题也不例外。我这一轮整理出的黄金组题目列表，在POJ等平台上常被一起收录，几道代表作分别是：Balanced Lineup（区间最值差）、Silver Cow Party（有向图最短路）、Best Cow Line（字典序最小构造）。

先说Balanced Lineup。题目讲的是农夫有一群身高不等的奶牛，需要反复查询某一段区间里最高牛和最矮牛的身高差。翻译过来就是标准的RMQ（Range Minimum/Maximum Query）问题：静态数组，多次询问，每次问区间最大值减最小值。这个题目最直白的做法是直接按区间扫一遍，但数据范围一大就必然超时，于是线段树和ST表就成了标准的两种解。

Silver Cow Party则是另外一类图论经典。N个农场之间有一些单向道路，每头牛要从自己家出发去X号农场参加派对，结束后再回家。由于道路是单向的，去程和回程未必是同一条路径。题目要求的是所有牛中往返总距离最长的那一个。这题的陷阱在于，如果每头牛都跑一次最短路，复杂度直接爆炸；正确做法是正反各建一张图，只跑两次Dijkstra。

Best Cow Line是第三类代表，属于贪心加字符串比较。一串字符，每次可以从队首或队尾取一个字符放到结果串末尾，要构造字典序最小的结果。看起来简单，但首尾相同的情况下怎么选，是这道题真正的深水区。

1.2 这套题为什么至今仍有训练价值

很多人有个误区：USACO 2007年的题太老了，没有参考价值。但实际刷下来你会发现，算法竞赛的核心考点这十几年并没有本质变化，变的只是数据范围、题目包装和出题角度。拿Balanced Lineup举例，当年N的范围也就是5万左右，Q也是5万，放到今天的普及组比赛里依然可以原封不动地出现。线段树、ST表这些数据结构，今天依然是CSP-S和NOIP的绝对主力。

另外，2007年这轮题还有一个好处：题目描述相对直白，不会像现代题一样绕上三层。这意味着你可以在最短时间内定位到“它在考什么算法”。对于刚接触竞赛训练的人来说，这种题是最好的思维训练材料。你已经不需要花大量时间理解题意，重点全在“怎么把学过的算法用干净利落地写出来”。当我带新人刷题的时候，经常会从这类老题开始，先把代码模板打牢，再去碰复杂的综合题。

这套题还有一个作用，就是帮你建立“算法匹配”的直觉。看到区间查询想到线段树，看到单向路径求最短想到Dijkstra，看到字典序最小想到贪心。这种条件反射一旦形成，后面刷任何新题都会快很多。

2. 区间查询类考点：Balanced Lineup里的RMQ拆解

2.1 朴素做法的瓶颈在哪里

先来看最直观的解法。既然每头奶牛的身高已经存在数组h[1..N]里，对于每次询问[l, r]，直接写个循环：

int maxV = -1, minV = INF; for (int i = l; i <= r; i++) { maxV = max(maxV, h[i]); minV = min(minV, h[i]); } printf("%d\n", maxV - minV);

这段代码逻辑完全正确，但在N和Q都是5万的数据规模下，单次查询最多扫描5万个元素，5万次询问就是25亿次操作，无论如何都是超时的。这里的瓶颈在于：前一次查询获得的信息完全没有被后一次查询利用，每次都在重复遍历。

想要优化，核心思路就一句话：把区间信息预先组织起来。要么用线段树把区间最值维护在树形节点里，要么用ST表做倍增预处理。这两种方案我当年都写过，实测下来各有优劣，下面分别展开。

2.2 线段树解法：一树双查询

线段树的思路是把整个区间不断二分，每个节点保存对应区间的最大值和最小值。建树复杂度O(N)，单次查询复杂度O(logN)。关键代码是这样：

#include <cstdio> #include <algorithm> using namespace std; const int MAXN = 50005; const int INF = 1e9; int n, q; int h[MAXN]; int maxv[MAXN << 2], minv[MAXN << 2]; void pushUp(int rt) { maxv[rt] = max(maxv[rt << 1], maxv[rt << 1 | 1]); minv[rt] = min(minv[rt << 1], minv[rt << 1 | 1]); } void build(int l, int r, int rt) { if (l == r) { maxv[rt] = minv[rt] = h[l]; return; } int mid = (l + r) >> 1; build(l, mid, rt << 1); build(mid + 1, r, rt << 1 | 1); pushUp(rt); } int queryMax(int L, int R, int l, int r, int rt) { if (L <= l && r <= R) return maxv[rt]; int mid = (l + r) >> 1, res = -INF; if (L <= mid) res = max(res, queryMax(L, R, l, mid, rt << 1)); if (R > mid) res = max(res, queryMax(L, R, mid + 1, r, rt << 1 | 1)); return res; } int queryMin(int L, int R, int l, int r, int rt) { if (L <= l && r <= R) return minv[rt]; int mid = (l + r) >> 1, res = INF; if (L <= mid) res = min(res, queryMin(L, R, l, mid, rt << 1)); if (R > mid) res = min(res, queryMin(L, R, mid + 1, r, rt << 1 | 1)); return res; } int main() { scanf("%d%d", &n, &q); for (int i = 1; i <= n; i++) scanf("%d", &h[i]); build(1, n, 1); while (q--) { int a, b; scanf("%d%d", &a, &b); printf("%d\n", queryMax(a, b, 1, n, 1) - queryMin(a, b, 1, n, 1)); } return 0; }

写线段树时有几个细节容易栽跟头。数组要开4倍空间，MAXN << 2是必须的，开小了直接越界崩溃。其次递归查询时，区间判断要写清楚L <= l && r <= R是直接返回，L <= mid和R > mid决定是否向左或向右递归。我自己第一次写的时候把mid的边界判断写反了，结果查出来的最大值经常是0，排查了半天才发现是右区间判断少了一个等号。

2.3 ST表的离线预处理优势

如果所有查询都可以在输入完成后一次性处理，ST表是比线段树更简洁的方案。它的核心是倍增预处理，令st[i][j]表示从i开始、长度为2^j的区间最值，递推公式是：

st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1])

查询的时候，对于区间[l, r]，先算出长度对应的k = floor(log2(r - l + 1))，然后取两个长度为2^k的区间覆盖[l, r]，取并集结果：

#include <cstdio> #include <algorithm> #include <cmath> using namespace std; const int MAXN = 50005; const int LOG = 16; int n, q; int maxst[MAXN][LOG], minst[MAXN][LOG]; void build() { for (int i = 1; i <= n; i++) { scanf("%d", &maxst[i][0]); minst[i][0] = maxst[i][0]; } for (int j = 1; (1 << j) <= n; j++) { for (int i = 1; i + (1 << j) - 1 <= n; i++) { maxst[i][j] = max(maxst[i][j - 1], maxst[i + (1 << (j - 1))][j - 1]); minst[i][j] = min(minst[i][j - 1], minst[i + (1 << (j - 1))][j - 1]); } } } int query(int l, int r) { int k = log2(r - l + 1); return max(maxst[l][k], maxst[r - (1 << k) + 1][k]) - min(minst[l][k], minst[r - (1 << k) + 1][k]); } int main() { scanf("%d%d", &n, &q); build(); while (q--) { int a, b; scanf("%d%d", &a, &b); printf("%d\n", query(a, b)); } return 0; }

ST表查询复杂度是O(1)，这是它最大的优势。但代价是预处理需要O(NlogN)的时间和O(NlogN)的空间，如果题目数据范围达到10的6次方以上，内存开销会变得紧张。另外注意，这里LOG取16是因为2^16 = 65536，已经能覆盖5万的数据范围，但如果你做题时N更大，一定要按数据范围去调LOG值，否则下标越界查出来的值全错。

2.4 两个写法的取舍体会

说句实在话，这道题两种解法都能过，但实际写题时我会更倾向线段树。原因是USACO这类竞赛题往往不只是单一考RMQ，线段树这个结构在后续题目里还能承担区间修改、区间加和、区间合并等更多功能，写熟练了一劳永逸。ST表虽然查询快，但遇到需要动态修改数组元素的题目就完全失效了。

如果你是想快速搞定这道题本身，ST表显然更短更不容易出bug。我的建议是：比赛时哪个熟练用哪个，但训练时两个都写一遍。因为每年USACO统计结果都显示，黄金组选手最容易丢分的地方就是线段树递归层数太深导致栈溢出、数组开小、边界条件漏判。你们刷题时可以专门练一下这类区间题，把写错的每个细节都记录下来，后面会很有帮助。

来看一下两种方案的复杂度对比：

3. 图论最短路的经典套路：Silver Cow Party反向建图

3.1 为什么不能每头牛都跑一次最短路

Silver Cow Party翻译过来是“银牛派对”。题意很直白：有N个农场，编号1到N，M条单向道路，每头牛住在一个农场，要去X号农场参加派对，结束后再回自己家。现在要计算所有牛中，往返路程的总长度最长的那头牛走的总距离。

从某个点出发到X的最短距离，以及从X回到某个点的最短距离，按理说只要把每个点都当作起点跑一次单源最短路，就能求出全部答案。但问题来了：如果对每个点都跑一遍Dijkstra，复杂度是O(N * (M + N)logN)，黄金组的数据规模下N上千、M上万，这种复杂度完全不可接受。

那怎么办？这里的关键是理解Dijkstra这类单源最短路算法的对称性：从一个点出发到所有点的最短路径，等价于把所有边反向之后，从原目标点出发到所有点的最短路径。听起来绕，实际上一句话就能说透：a点到b点的有向边，反向之后就是b点到a点的有向边；那么“所有点到X的最短路”就等价于“在反图中从X出发到所有点的最短路”。

3.2 正反建图，两次Dijkstra搞定

有了上面的结论，解法就非常清晰了。先按输入建一张原图G1，同时建一张所有边方向反转的图G2。在原图上从X跑一次Dijkstra，得到每头牛回家的最短距离；在反图上再从X跑一次Dijkstra，得到每头牛从家出发去派对的最短距离。两者相加，取最大值就是答案。

核心代码：

#include <cstdio> #include <queue> #include <cstring> #include <vector> #include <algorithm> using namespace std; const int MAXN = 1005; const int INF = 0x3f3f3f3f; struct Edge { int to, w; Edge(int t, int ww) : to(t), w(ww) {} }; vector<Edge> G1[MAXN], G2[MAXN]; int d1[MAXN], d2[MAXN]; int n, m, x; void dijkstra(vector<Edge> G[], int s, int d[]) { memset(d, 0x3f, sizeof(int) * (n + 1)); d[s] = 0; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; pq.push({0, s}); while (!pq.empty()) { auto cur = pq.top(); pq.pop(); int u = cur.second; if (cur.first > d[u]) continue; for (auto e : G[u]) { if (d[u] + e.w < d[e.to]) { d[e.to] = d[u] + e.w; pq.push({d[e.to], e.to}); } } } } int main() { scanf("%d%d%d", &n, &m, &x); for (int i = 0; i < m; i++) { int a, b, t; scanf("%d%d%d", &a, &b, &t); G1[a].push_back(Edge(b, t)); // 原图：a -> b G2[b].push_back(Edge(a, t)); // 反图：b -> a } dijkstra(G1, x, d1); // 回程：从X到每个农场 dijkstra(G2, x, d2); // 去程：反图中从X出发，等价于每个农场到X int ans = 0; for (int i = 1; i <= n; i++) { ans = max(ans, d1[i] + d2[i]); } printf("%d\n", ans); return 0; }

这里有几个点必须注意。第一，dijkstra函数里memset的长度一定要用n + 1，而不是整个数组大小，不然在函数里处理多个图时会越界。第二，优先队列用pair<int, int>时，默认先比较first，所以把距离放在第一位、节点编号放第二位，配合greater才能实现小根堆。第三，判断cur.first > d[u]时，如果队列里存的是过期的旧距离就跳过，这样能大幅减少无效扩展。

3.3 图论题的常见坑和复杂度验证

复杂度方面，堆优化Dijkstra在稀疏图上的表现是O((N + M)logN)，跑两次依然是这个量级。相比N次最短路，这是从指数级优化到接近线性的飞跃。USACO的黄金组图论题很少考单源最短路本身，更多是像这题一样，考“对建图的理解”。

这题还有一个隐性的坑，就是重边。输入数据可能对同一对农场给出多条道路，权重不同。Dijkstra本身对重边是免疫的，因为每次会用dist[u] + w去更新，多个边只会更新多次，只要dist初始为INF，就能自动选出最短的那条。但是如果你自己写邻接矩阵而不做特殊处理，就很容易被重边干扰，甚至在更新时把长边覆盖掉短边。我平时写图论题一律优先用邻接表，可以少踩很多这种坑。

另外，INF的取值也要讲究。用0x3f3f3f3f有一个天然优势：它大约是10亿，比大多数题目边权总和大一个数量级，同时用memset按字节填充时，整个int正好都变成0x3f3f3f3f，不会出现奇怪的值。如果你用2147483647当INF，一旦在松弛时加一个正数就直接溢出变成负数，整个最短路结果直接崩掉。这一点我在刚学图论时吃过很大的亏，后来就养成了习惯，所有最短路的INF统一用0x3f3f3f3f。

还有一点很有意思：如果你把d1[i] + d2[i]手算一遍，会发现这个值恰好是第i头牛从家到X、再从X回家的最短总路程。这个对称性的理解，比代码本身更重要。因为以后很多题目，比如多源最短路、次短路、路径计数问题，都会用到反向建图这个基础技巧。

4. 贪心与字符串：Best Cow Line的双端构造

4.1 题目背景和贪心策略

Best Cow Line这题是另一种味道。给你一个长度为N的字符串，每次只能从原串的开头或结尾取出一个字符，放到新串的末尾。要求最后得到的新串字典序最小。

这是典型的贪心构造问题。最直观的思路是：每次比较当前串的首尾字符，取较小的那一个放进去。这个策略绝大部分时间是对的，但有一个特殊情况必须处理——首尾字符相等时，不能随便挑一个。比如原串是“ABACABA”，如果首尾相同就随便选，很可能会构造出比最优解更大的串。

正确的贪心策略是：当首尾字符相同时，不要急着决定，继续向内层比较。比较s[l+1]和s[r-1]，哪边更小就取哪边；如果仍然相同，就继续向内比较，直到出现差异或指针相遇。本质上就是比较“原串从左到右”和“原串从右到左”两个序列的字典序大小，谁小取谁。

4.2 朴素实现和优化思路

按这个思路写朴素版代码，复杂度最坏是O(N^2)。在2007年的数据范围下这完全够用，N一般不超过2000：

#include <cstdio> using namespace std; const int MAXN = 2005; int n; char s[MAXN], ans[MAXN]; bool better(int l, int r) { while (l < r) { if (s[l] != s[r]) return s[l] < s[r]; l++; r--; } return true; } int main() { scanf("%d", &n); for (int i = 0; i < n; i++) scanf(" %c", &s[i]); int l = 0, r = n - 1, cnt = 0; while (l <= r) { if (s[l] < s[r]) ans[cnt++] = s[l++]; else if (s[l] > s[r]) ans[cnt++] = s[r--]; else { if (better(l + 1, r)) ans[cnt++] = s[l++]; else ans[cnt++] = s[r--]; } } ans[cnt] = '\0'; for (int i = 0; i < n; i++) { putchar(ans[i]); if ((i + 1) % 80 == 0) putchar('\n'); } if (n % 80) putchar('\n'); return 0; }

这个写法里有几个细节要注意。比较函数better里，l和r会不断向中间移动，但只比较字符大小，一旦发现s[l] != s[r]就返回比较结果；如果整个区间全部相同，返回true，表示从左端取。这样就能保证每次取字符的时候，都取的是字典序更优的一侧。输出部分每80个字符换一行，这是USACO老题的格式要求，如果忘记换行会WA，虽然逻辑完全正确。

4.3 进一步优化的方向

当N变大，比如到10万级别，O(N^2)的朴素比较就会超时。优化的套路一般有两种：第一种是用后缀数组预处理，把原串和反转串拼接起来，通过比较rank值快速判断两个方向的字典序大小；第二种是二分加哈希，先二分找到一个最长的公共前缀长度，再比较下一个不同字符，也能把单次比较优化到O(logN)。

我个人更推荐二分加哈希的方案，因为代码量可控，而且关键点很清晰：既然我们总在比较两个字符串的字典序，那不妨先定位它们第一个不同的位置，这正好可以用二分求LCP来实现。哈希选个双模数，基本不会出错。不过对USACO黄金组的难度来说，朴素写法已经足够，优化更多是给你留一条后路，万一遇到数据加强版，不至于手足无措。

这类“每次从两端取一个构造最优序列”的贪心模型，在竞赛里非常常见。变化形式包括：两端取数字构造最大数、两端取字符串问能否组成回文串、以及两端取元素时带权重。吃透Best Cow Line的思考过程，那类题都会迎刃而解。

5. 从刷题到实战：我的踩坑记录与训练建议

5.1 USACO提交机制和拿分策略

USACO月赛和国内OI赛制不太一样，不是只有一次提交机会。它的比赛窗口通常开放几天，你在窗口期内可以反复提交同一道题，平台会反馈当前测试点的得分情况，最终取历史最高分。这个机制对训练来说其实非常友好，因为你可以大胆尝试不同解法，看到部分分再逐步优化，而不是像ICPC一样一次提交定生死。

我第一次参加USACO的时候不懂规则，写完一版就交了，结果有几个测试点TLE。后来官方分析出来了才发现，那题只要把朴素循环改成前缀和就好，白白丢分。从那以后我学到一个经验：在黄金组比赛里，先写一个确定能拿部分分的暴力版本，再逐步改成正解。哪怕正解没写完，也能确保有保底分。

2007年1月这套题同样适用这个策略。Balanced Lineup先写一遍O(NQ)的暴力，核对结果后再上线段树；Silver Cow Party实在想不出反向建图，可以先对每个点跑Dijkstra拿部分分；Best Cow Line如果卡在贪心的正确性上，可以先写搜索对拍，看随机数据的正确率。这套“暴力先行，逐步优化”的思维模式，是打USACO最重要的基本功。

5.2 我整理的常见错误速查表

这几道题我前前后后写了很多遍，每次都会遇到一些经典错误。我整理了一张速查表，你们刷题时可以对照检查：

5.3 训练方法：如何高效刷老题

刷USACO老题，我强烈建议不要只追求“AC”这个结果。拿到一道题，先花15分钟自己思考，想不清楚就写暴力，跑出小数据的正确答案后，再带着答案去看官方分析。官方分析（contest analysis）会给出不止一种解法，还会分析每种解法的得分情况和使用场景，这是比题解博客更值钱的资料来源。

针对2007年1月这套题，我的练习顺序是：先从Best Cow Line入手，因为它对代码量要求最低，适合热身；然后做Balanced Lineup，把线段树和ST表都写一遍，最好再顺手扩展一下，把区间最大公约数、区间最大子段和等变体都实现一次；最后做Silver Cow Party，重点是理解反向建图背后的原理，并尝试用这题的思想解决其他图论题。

每道题AC之后，我还会写一个简短思路复盘，记录这题的核心结论、我犯过的错误、以及能否用其他算法重写。这样过了三个月再回头看，不需要重新推一遍全部思路，直接看复盘就能快速恢复记忆。

5.4 关于老题价值的一点个人体会

如果你去翻USACO 2007年1月的官方数据，会发现当年的满分线不算特别高，这并不意味着题目简单，而是因为那个年代的选手需要自己调试的细节更多，代码环境也没有今天这么便利。但算法内核是一样的。今天我们再刷这套题，相当于拿着后视镜去看当年选手的思维轨迹，反而能更清楚地看到“经典算法怎么一步步演变成现代套路”。

我自己在刷完这套题之后最大的收获，不是多会了几个算法模板，而是养成了一个习惯：拿到任何题目，先问自己“这题的模型是什么，最优解法依赖哪个核心性质”。Balanced Lineup依赖的是区间信息可合并，Silver Cow Party依赖的是最短路对称性，Best Cow Line依赖的是字典序比较的局部决策。这些底层认知，比单纯背代码重要得多。

如果你正准备冲USACO黄金组，我建议你先别急着刷一堆新题，把每个知识点的经典模板做到能盲写，再拿这套2007年1月的真题当自测。限时4小时，全程模拟真实比赛，做完再对照官方分析复盘。这样循环几轮，你的代码稳定性、算法匹配速度和调试能力会提升得非常快。