刷透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。题目讲的是农夫有一群身高不等的奶牛需要反复查询某一段区间里最高牛和最矮牛的身高差。翻译过来就是标准的RMQRange 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统计结果都显示黄金组选手最容易丢分的地方就是线段树递归层数太深导致栈溢出、数组开小、边界条件漏判。你们刷题时可以专门练一下这类区间题把写错的每个细节都记录下来后面会很有帮助。来看一下两种方案的复杂度对比方案预处理单次查询空间适用场景朴素遍历O(1)O(N)O(N)数据极小线段树O(N)O(logN)O(4N)需要动态修改ST表O(NlogN)O(1)O(NlogN)静态查询密集3. 图论最短路的经典套路Silver Cow Party反向建图3.1 为什么不能每头牛都跑一次最短路Silver Cow Party翻译过来是“银牛派对”。题意很直白有N个农场编号1到NM条单向道路每头牛住在一个农场要去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) {} }; vectorEdge G1[MAXN], G2[MAXN]; int d1[MAXN], d2[MAXN]; int n, m, x; void dijkstra(vectorEdge G[], int s, int d[]) { memset(d, 0x3f, sizeof(int) * (n 1)); d[s] 0; priority_queuepairint, int, vectorpairint, int, greaterpairint, 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而不是整个数组大小不然在函数里处理多个图时会越界。第二优先队列用pairint, 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[l1]和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 我整理的常见错误速查表这几道题我前前后后写了很多遍每次都会遇到一些经典错误。我整理了一张速查表你们刷题时可以对照检查错误类型表现原因解决方式数组越界程序崩溃或答案错乱线段树开2倍空间而非4倍线段树统一用MAXN 2递归栈溢出大样例直接爆栈线段树递归深度太大可改为非递归或扩大栈空间INF取值不当最短路答案异常大或为负距离加权重时整型溢出统一用0x3f3f3f3f忘记反向建图Silver Cow Party结果偏小只跑了一次Dijkstra原图和反图各建一张双端比较时方向错Best Cow Line字典序错误better函数指针向中间移动时搞反多写几组ABACABA类数据验证输入输出格式错本地正确但提交WA没按80字符换行输出细读题目输出要求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小时全程模拟真实比赛做完再对照官方分析复盘。这样循环几轮你的代码稳定性、算法匹配速度和调试能力会提升得非常快。