1. 2019年12月白銀組考點分布與題目畫像1.1 三道題在USACO白銀組中的代表性2019年12月這場白銀組一共三道題MooBuzz、Milk Factory、Moop。從名字就能看出來USACO非常喜歡給題目起這種帶梗的名字MooBuzz是“牛奶報數(shù)”Milk Factory就是牛奶工廠Moop則是牛叫加跳躍的合成詞。題目本身不復(fù)雜但每一道都踩在白銀組最典型的出題路線上。先看MooBuzz。它考察的是模擬與周期規(guī)律白銀組非常喜歡出這種“一眼暴力、仔細想有數(shù)學(xué)優(yōu)化”的題。青銅組通常直接while循環(huán)就能過但到了白銀組數(shù)據(jù)范圍一放大暴力立刻撞墻。Milk Factory是經(jīng)典的圖論基礎(chǔ)題給定N個節(jié)點和N-1條有向邊本質(zhì)上是一棵有向樹的變體考察方向遍歷與可達性判斷。這類題在白銀組出現(xiàn)頻率極高幾乎每一屆都有一道。Moop則是排序加貪心、偏序關(guān)系的入門題表面上像是幾何題實際上和數(shù)據(jù)排列、鏈劃分有關(guān)用作白銀組壓軸題非常合適。這三道題組合到一起幾乎就是白銀組選手必須掌握的三板斧對枚舉優(yōu)化的敏感度、圖論的建模能力、排序后貪心的直覺。把這套題吃透后面打黃金組很多DP題的思路也能順下來因為很多DP本質(zhì)上就是“排序之后做狀態(tài)轉(zhuǎn)移”。我每次帶新人開始刷USACO都會先推薦這套題作為白銀組入門的第一份真題原因就在這里。1.2 和大廠筆試、GESP的橫向?qū)φ蘸芏嘧x者會同時關(guān)注大廠筆試真題解析、GESP一級Python真題解析這類內(nèi)容。說實話USACO白銀組這幾道題和大廠筆試、GESP是有一定重疊度的。大廠筆試的算法題?？紨?shù)組、字符串、圖遍歷、貪心Milk Factory這種“反向圖DFS找可達性”的題換個馬甲就是社交網(wǎng)絡(luò)中“誰能聯(lián)系到誰”、系統(tǒng)依賴中“哪些服務(wù)能被所有調(diào)用方觸達”的模型。MooBuzz的周期計算本質(zhì)是數(shù)學(xué)歸納和取模運算GESP一級Python的題目里也有不少類似“報數(shù)、跳數(shù)、逢3過”的變體只是數(shù)據(jù)規(guī)模小很多。不過USACO更強調(diào)從0到1的完整代碼實現(xiàn)和邊界處理這是它的訓(xùn)練價值所在。大廠筆試通常更看重在限定時間內(nèi)快速寫對算法兩者考察維度略有差別但基礎(chǔ)算法能力是共通的。甚至你去看系統(tǒng)架構(gòu)師考試里的案例分析題面都是工程化場景但核心還是建模和權(quán)衡跟USACO的訓(xùn)練思路一致。我建議你把這套題當(dāng)算法體檢來做做完之后再看GESP或筆試真題會有一種“底層能力打通了”的感覺。下面我們逐題拆先把最簡單也最容易粗心丟分的MooBuzz講透。2. MooBuzz跳過3和5的倍數(shù)暴力不夠優(yōu)雅2.1 題目其實是“報數(shù)游戲”MooBuzz的題意非常直白農(nóng)夫約翰按1, 2, 3, 4, …一直數(shù)下去但是只要遇到能被3或5整除的數(shù)就跳過不報。比如3、5、6、9、10、12都要跳過。這樣真正被報出來的序列是1, 2, 4, 7, 8, 11, 13, 14, 16, 17……題目給你一個N問這個序列里的第N個數(shù)是多少。很多人第一反應(yīng)就是while循環(huán)模擬從1開始每個數(shù)判斷一次能不能被3或者5整除能報就計數(shù)器加一計數(shù)器到N就輸出。這個寫法在N比較小的時候完全沒問題代碼五分鐘寫完樣例輕松過。但USACO白銀組的N上限是1e9這個規(guī)模下從1模擬到1e9哪怕每次判斷再快也會超時。這就是USACO和青銅組拉開的第一個差距不是考你不會循環(huán)而是考你能不能在數(shù)據(jù)范圍面前停下來想想。這道題也經(jīng)常被拿來改編比如變成“逢3過”、逢7過之類的報數(shù)游戲。理解了周期規(guī)律怎么變都不怕。2.2 為什么不能一路while到N我們算一下復(fù)雜度。如果直接枚舉到第N個數(shù)粗略估計需要檢查約3N/2個整數(shù)才能報出N個數(shù)因為大約有一半的數(shù)會被跳過N1e9時檢查量級就是1.5e9。C在USACO評測環(huán)境下一秒鐘大概跑1e8到2e8次簡單運算1.5e9次循環(huán)加取模必然超時Python就更不用說了直接一路數(shù)下去基本無望。所以正確的方向是找規(guī)律。仔細觀察被報出的序列會發(fā)現(xiàn)它在1到15這個區(qū)間里能被3或5整除的數(shù)是3, 5, 6, 9, 10, 12, 15恰好7個剩下的8個數(shù)就是能報出來的1, 2, 4, 7, 8, 11, 13, 14。為什么看15因為3和5的最小公倍數(shù)是15能否被3或5整除這件事只跟這個數(shù)對15取模的結(jié)果有關(guān)15的倍數(shù)也永遠被跳過。所以整個序列以15為周期每個周期恰好8個有效數(shù)。這個發(fā)現(xiàn)非常關(guān)鍵。有了周期第N個數(shù)就能用除法定位先計算N之前有多少個完整15周期再在周期內(nèi)找余下那個數(shù)。整個過程是O(1)的無論N多大都能瞬間算出來。2.3 15個數(shù)的循環(huán)周期與下標(biāo)細節(jié)具體公式可以寫成這樣令k (N - 1) / 8r (N - 1) % 8。k表示前面有多少個完整的15周期r表示當(dāng)前落在周期內(nèi)的第幾個有效數(shù)。然后把1到15按順序遍歷把能報出來的數(shù)存到數(shù)組v里第(r1)個有效數(shù)就是我們要的偏移量。最終答案 k * 15 v[r]。這里為什么要用(N-1)而不是N因為數(shù)組下標(biāo)從0開始我們想讓第一個數(shù)對應(yīng)r0這樣第1個數(shù)的答案正好是1。如果你直接用N去算第1個就會被錯算成第2個樣例都過不去。這種下標(biāo)細節(jié)是考場最容易翻車的點寧可寫完之后用N1、N2、N8、N9手動驗一遍也不要偷懶。我們驗證一下N1時k0, r0, v[0]1答案就是1正確。N8時k0, r7, v[7]14答案14因為序列前8個數(shù)確實到14。N9時k1, r0答案1*15116而我們列出的第9個數(shù)正是16完美對上。這里還可以擴展一個小思考如果題目問第N個被跳過的數(shù)其實思路一樣只是有效數(shù)變成那些能被3或5整除的數(shù)。2.4 考場代碼與邊界驗證下面給出C實現(xiàn)。注意N用long long讀入因為1e9雖然int裝得下但k*15之后可能接近1.5e9雖然仍在int范圍內(nèi)但養(yǎng)成用long long的習(xí)慣能少踩很多坑。#include bits/stdc.h using namespace std; int main() { freopen(moobuzz.in, r, stdin); freopen(moobuzz.out, w, stdout); long long N; cin N; vectorint v; for (int i 1; i 15; i) { if (i % 3 ! 0 i % 5 ! 0) { v.push_back(i); } } long long k (N - 1) / 8; int r (N - 1) % 8; cout k * 15 v[r] \n; return 0; }如果你用Python邏輯完全一樣import sys def main(): sys.stdin open(moobuzz.in, r) sys.stdout open(moobuzz.out, w) N int(sys.stdin.readline()) v [i for i in range(1, 16) if i % 3 ! 0 and i % 5 ! 0] k (N - 1) // 8 r (N - 1) % 8 print(k * 15 v[r]) if __name__ __main__: main()這類題還有一個常見變體問第N個能被3或5整除的數(shù)。思路完全一樣只是篩選條件反過來。解題時先看清題目要的是“跳過”還是“保留”別把條件寫反。做完這題接下來看Milk Factory這道題可以說是白銀組圖論題的“方向感考試”。3. Milk Factory有向圖里的“萬能終點”3.1 題意和樣例解讀Milk Factory的題面是一個典型的工廠流水線背景有N臺機器編號1到N機器之間用N-1條單向傳送帶連接。每條傳送帶從機器a到機器b表示牛奶可以從a被送到b。農(nóng)夫約翰想選一臺機器作為牛奶加工站要求是不管牛奶從哪臺機器開始最終都能依靠傳送帶到達這臺機器。題目問是否存在這樣的機器如果存在輸出編號最小的那個否則輸出-1。讀完題面第一件事是把它翻譯成圖論語言N個點、N-1條有向邊圖是弱連通的。我們要找的是這樣一個節(jié)點u對于任意起點v都存在一條從v到u的有向路徑。換句話說u是所有節(jié)點的“公共可達終點”。這個定義很容易理解成“出度為0的點”但這是錯的后面我會專門講。先看正確建模方式如果從u出發(fā)沿著所有邊的反方向走能夠到達所有其他節(jié)點那么反過來原圖中所有節(jié)點都能到達u。也就是說只要在建圖時把每條邊反向存儲然后在反圖上從候選點u做一次DFS統(tǒng)計它能訪問到多少個節(jié)點能訪問到N個就說明滿足條件。3.2 反向建圖為什么“反圖DFS”是對的為什么反向圖的“從u出發(fā)能到所有點”等價于正向圖的“所有點能到u”這其實只是把每條邊的箭頭方向反過來看。原圖中從a到b的傳送帶在反圖中就是一條從b到a的邊。如果原圖中存在路徑v - ... - u那么反圖中必然存在路徑u - ... - v。路徑反向方向互換可達性完全對應(yīng)。這個“反向建圖”的小技巧在USACO白銀組經(jīng)常出現(xiàn)值得專門記住。舉個例子。原圖有邊1-22-3。反圖就是3-22-1。在反圖中從3出發(fā)可以到2再到1訪問到全部三個節(jié)點所以原圖中從1、2、3都能到達33就是答案。如果不用反圖而是從每個起點v做DFS判斷能否到達u也是可行的但你要枚舉起點而不是終點代碼寫起來多一層循環(huán)思路也容易繞進去。反圖把這個過程變成“只從一個點出發(fā)看覆蓋范圍”邏輯更干凈。由于N的上限是100最樸素的做法就是對每個候選節(jié)點u都做一次DFS/BFS每次O(N)總復(fù)雜度O(N^2)也就是最多1e4次操作跑起來毫無壓力。這個數(shù)據(jù)范圍下根本不需要什么高級優(yōu)化重點是把圖和方向搞清楚。USACO白銀組很多題就是這樣算法不難難的是你不肯靜下心來建模。3.3 反圖DFS的完整實現(xiàn)我的做法是讀入每條邊a-b時不存正向圖而是直接把b-a存進鄰接表。然后從1到N枚舉u每一次都清空vis數(shù)組從u開始DFS最后數(shù)一數(shù)vis里有多少個true。如果等于N說明u就是答案直接輸出并結(jié)束程序。所有u都不滿足就輸出-1。#include bits/stdc.h using namespace std; const int MAXN 105; vectorint g[MAXN]; bool vis[MAXN]; void dfs(int u) { vis[u] true; for (int v : g[u]) { if (!vis[v]) dfs(v); } } int main() { freopen(factory.in, r, stdin); freopen(factory.out, w, stdout); int N; cin N; for (int i 0; i N - 1; i) { int a, b; cin a b; g[b].push_back(a); // 反向邊 } for (int u 1; u N; u) { memset(vis, 0, sizeof(vis)); dfs(u); int cnt 0; for (int i 1; i N; i) { if (vis[i]) cnt; } if (cnt N) { cout u \n; return 0; } } cout -1 \n; return 0; }這段代碼里最需要留神的一行就是g[b].push_back(a)。如果你習(xí)慣性地寫了g[a].push_back(b)那么DFS從u出發(fā)能到的就不是反圖而是原圖語義完全反了。真到了考場建議在紙上先把樣例的圖和反圖畫一遍再對照代碼檢查建圖方向。另外每次DFS前都要memset vis這個操作看起來笨但漏掉的話上一次訪問的標(biāo)記會殘留導(dǎo)致cnt永遠偏大屬于非常隱蔽的WA來源。3.4 容易被帶偏的“只看出度”誤區(qū)我見過不少選手拿到這題的第一反應(yīng)是找一個出度為0的點因為終點不能再往外走。這個思路聽起來很合理但立刻就會被反例擊碎。比如三條邊1-23-22-4。出度為0的是4從1和3都能到2再到44確實是答案。再看這個例子1-2, 1-3。出度為0的是2和3但2無法從3到達3也無法從2到達所以既不是2也不是3答案是-1。這說明“只看出度”會漏掉“其他支路能否到達它”這一層。在一些弱連通的有向樹里出度為0的葉子確實有可能成為公共終點但一旦圖里出現(xiàn)多個葉子或者方向分叉后不再匯聚這個捷徑就失效了。所以最穩(wěn)妥的辦法是正面做反圖DFS。不要迷信出度這種偷懶捷徑除非你能嚴格證明圖的結(jié)構(gòu)。考場上的經(jīng)驗是能用O(N^2)暴力解決的問題優(yōu)先保證正確性再考慮常數(shù)優(yōu)化。4. Moop排序之后問題變成了貪心和鏈覆蓋4.1 題意與初始模型Moop這道題表面上是坐標(biāo)幾何題給出N個土堆的坐標(biāo)(x, y)奶?？梢詮囊粋€土堆跳到另一個土堆跳躍條件是同時滿足源點的x不超過目標(biāo)點的x、源點的y不超過目標(biāo)點的y即xi xj 且 yi yj。農(nóng)夫想知道如果一開始有若干頭奶牛每頭奶?？梢赃x擇一個土堆作為起點然后沿著跳躍規(guī)則連續(xù)跳下去那么最少需要幾頭奶牛才能把所有土堆都至少覆蓋一次。把這句話翻譯過來就是要把N個點分成最少的幾條“鏈”每條鏈內(nèi)部是一個按跳躍關(guān)系排列的序列鏈中前一個點必須能跳到后一個點。這樣的問題叫作最小鏈覆蓋。看到偏序關(guān)系、鏈覆蓋這些詞第一反應(yīng)可能是動態(tài)規(guī)劃但其實白銀組的量級根本不需要復(fù)雜DP排序加貪心就夠了。這道題的難度在于你能否從“平面上跳躍”這種具象描述里抽象出“偏序”“鏈”“反鏈”這些概念。我見過不少選手卡在這里很久就是因為一直盯著坐標(biāo)看沒有意識到坐標(biāo)大小關(guān)系本質(zhì)上就是元素之間的比較規(guī)則。4.2 偏序關(guān)系和鏈覆蓋這里的跳躍關(guān)系具有傳遞性如果A能跳到BB能跳到C那么A也能一路跳到C所以這個關(guān)系是偏序。偏序集中的一條鏈就是一串可比元素。題目問的最少奶牛數(shù)就是最少用幾條鏈覆蓋所有元素即最小鏈覆蓋。偏序理論里有一個著名結(jié)論叫Dilworth定理最小鏈覆蓋數(shù)等于最大反鏈大小。最大反鏈是一個集合里面任意兩個元素都不可比也就是任意兩點的x、y不能同時滿足一個大于等于另一個的偏序條件。這個定理看起來很數(shù)學(xué)但用在編程題里可以轉(zhuǎn)化成非常具體的操作先把點按x升序排序那么兩點不可比就等價于在排序后的序列中y是嚴格下降的。想一想如果后面的點y比前面的點小那么后面的點x更大但y更小兩個點互相都不能跳到對方如果后面點y更大或相等那它們就是可比的。所以最大反鏈的長度就是y序列的最長嚴格下降子序列長度。這就是整個題目的核心轉(zhuǎn)化幾乎所有正解都圍繞它展開。為了更直觀舉個簡單例子三個點(1,1), (2,3), (3,2)。排序后y序列是1, 3, 2。最長嚴格下降子序列是3,2長度2或者1? 1后面沒有更小的所以最長是3到2長度2。答案是2。手動驗證一下奶牛A可以從(1,1)跳到(2,3)奶牛B跳到(3,2)確實需要2頭牛。4.3 貪心維護multiset直接的實現(xiàn)可以不顯式求最長下降子序列而是用一個multiset做貪心。做法是排序之后從左到右處理每個點multiset里維護當(dāng)前所有鏈的“末端y值”。對于當(dāng)前點的y我們在multiset里找一個最大的且不超過y的末端值。如果存在說明這個點可以接在這一條鏈的后面因為前面鏈的末端x和y都不超過當(dāng)前點我們把這個舊末端刪掉換成當(dāng)前點的y如果不存在說明當(dāng)前點的y比所有現(xiàn)有鏈的末端都小它無法接在任何鏈后面只能新開一條鏈把y插入multiset。處理完所有點multiset的大小就是答案。為什么選“最大的不超過y”而不是隨便一個不超過y的因為我們要盡可能保留較小的末端給后面更小的點用。這個思路和經(jīng)典的最小區(qū)間調(diào)度、任務(wù)分配問題非常像貪心策略就是“能接就接接的時候選最接近的那一個”。用一個multiset實現(xiàn)每個點一次查找加一次替換總復(fù)雜度O(N log N)。#include bits/stdc.h using namespace std; int main() { freopen(moop.in, r, stdin); freopen(moop.out, w, stdout); int N; cin N; vectorpairint, int p(N); for (int i 0; i N; i) { cin p[i].first p[i].second; } sort(p.begin(), p.end()); multisetint ends; for (int i 0; i N; i) { int y p[i].second; auto it ends.upper_bound(y); if (it ! ends.begin()) { --it; ends.erase(it); ends.insert(y); } else { ends.insert(y); } } cout ends.size() \n; return 0; }這段代碼里的upper_bound(y)返回第一個嚴格大于y的迭代器如果它不是begin說明存在小于等于y的末端it向前走一步就是最大的那個。如果你用lower_bound邊界條件會全亂這也是為什么我一直強調(diào)multiset的查找語義要記牢。遇到邊界不確定寧可先在腦內(nèi)走一遍小樣例。4.4 為什么答案等于最長下降子序列長度如果你不想寫multiset也可以直接用求LDS的方式得到答案。按x升序、x相同按y升序排序后對y序列求最長嚴格下降子序列的長度結(jié)果就是最小鏈覆蓋數(shù)。原因是最長嚴格下降子序列中的任意兩個元素都不可比因此它一定是一個反鏈而Dilworth定理保證最大反鏈長度等于最小鏈覆蓋數(shù)。兩者取等所以答案就是LDS長度。有一個細節(jié)要特別注意排序時x相同的點y一定要按升序排。如果按y降序排兩個x相同、y不同的點會被誤判成可以同時出現(xiàn)在下降子序列中但它們實際上是可以互相跳躍的根本不在反鏈里答案就會偏大。用multiset貪心的方式則沒有這個顧慮因為排序后x相同y升序鏈的接續(xù)順序天然符合跳躍規(guī)則。對應(yīng)到代碼LDS可以用二分法O(N log N)解決思路上和LIS完全對稱。在Python里可以對每個y取相反數(shù)然后對相反數(shù)序列求最長嚴格遞增子序列長度。代碼大概是這樣import sys from bisect import bisect_left def main(): sys.stdin open(moop.in, r) sys.stdout open(moop.out, w) n int(sys.stdin.readline()) points [tuple(map(int, sys.stdin.readline().split())) for _ in range(n)] points.sort() tails [] for x, y in points: val -y pos bisect_left(tails, val) if pos len(tails): tails.append(val) else: tails[pos] val print(len(tails)) if __name__ __main__: main()這里的關(guān)鍵是bisect_left對應(yīng)嚴格遞增的LIS如果你用bisect_right求的是非嚴格遞增結(jié)果會錯。建議寫完代碼后造一個小樣例比如剛才的(1,1),(2,3),(3,2)答案為2手動走一遍代碼確認。4.5 兩種做法的取舍multiset貪心直觀、不容易被排序方向坑到適合白銀組考場求LDS代碼短、常數(shù)小適合對偏序定理有把握的選手。我個人建議你把兩種做法都寫一遍因為Moop代表的這類“排序后映射成序列問題”的題目在后續(xù)黃金組、白金組里會反復(fù)出現(xiàn)。理解了“偏序→鏈覆蓋→反鏈→最長下降子序列”這條鏈路比背會一道題的代碼值錢得多。平時訓(xùn)練時也可以試試把Moop和經(jīng)典的最長遞增子序列、俄羅斯套娃信封問題對比著做你會發(fā)現(xiàn)它們的內(nèi)核幾乎一模一樣只是表述不同。這種“透過表象看本質(zhì)”的能力才是刷USACO歷年真題真正要訓(xùn)練的東西。5. 白銀組考場的實戰(zhàn)策略5.1 讀題順序與樣例分析USACO每場比賽可選時間段內(nèi)連續(xù)做4到5小時白銀組三道題時間看似充裕但很多人還是因為讀題慢、方向錯而翻車。我的建議是拿到題先按難度排序MooBuzz是最簡單的溫暖題Milk Factory次之Moop最難。先把最穩(wěn)的題AC掉再啃硬骨頭心態(tài)完全不同。讀題時不要只盯著文字重點看樣例輸入輸出自己動手在草稿紙上模擬一遍樣例把題目里的“關(guān)系”畫成圖或序列。這個動作看起來浪費時間實際能幫你避免方向性錯誤。以Milk Factory為例光看題面很容易把傳送帶方向看反但只要你把樣例的圖在紙上畫出來再標(biāo)出反圖理解成本和出錯概率都會大幅下降。讀題花5分鐘畫圖花5分鐘看起來比直接敲代碼慢實際省下的調(diào)試時間遠超這10分鐘。5.2 時間分配建議給一個參考時間分配MooBuzz控制在30分鐘內(nèi)Milk Factory控制在40分鐘內(nèi)Moop可以先想20分鐘如果沒思路就先寫暴力拿部分分再回頭想正解。USACO白銀組得分是按測試點來的部分分也有價值不要死磕一道題。我當(dāng)年打這場的時候Moop想貪心想了很久差點沒時間檢查前兩題后來養(yǎng)成的習(xí)慣是每道題AC之后立刻用樣例和自己的小數(shù)據(jù)重測一遍再進入下一題這樣即使后面的題翻車至少保底分是穩(wěn)的。還有一個經(jīng)常被忽略的點如果你提前一小時做完了不要急著交把三道題都改成用文件輸入輸出再跑一遍樣例確保freopen的文件名和題目完全一致。每年都有選手因為文件名拼寫錯誤或者忘了freopen而丟掉整題分數(shù)這種失誤太可惜了。5.3 文件IO和調(diào)試模板USACO要求文件名定向MooBuzz對應(yīng)moobuzz.in/moobuzz.outMilk Factory對應(yīng)factory.in/factory.outMoop對應(yīng)moop.in/moop.out。寫代碼時最穩(wěn)的做法是一開始就寫好freopen避免最后忘記。調(diào)試時我習(xí)慣在本地用小規(guī)模的隨機數(shù)據(jù)生成器和暴力對拍對MooBuzz可以用while循環(huán)暴力當(dāng)對拍器對Milk Factory可以寫一個從每個點正向DFS的樸素解法當(dāng)對拍器對Moop可以寫O(N^2)的鏈覆蓋暴力當(dāng)對拍器。對拍通過后再提交基本一次AC。我這里提供一個對拍的基本套路寫一個gen.cpp生成隨機小數(shù)據(jù)寫一個bf.cpp放暴力解再寫一個sol.cpp放正解腳本里循環(huán)跑gen、bf、sol再用diff比較輸出。一旦不一致立刻拿到那組小數(shù)據(jù)手動分析。這個習(xí)慣價值極高尤其是Moop這種思維量大的題光靠樣例很難覆蓋所有邊界。6. 干擾項與常見WA/TLE速查6.1 三道題最易翻車的位置把三道題在考場上常見的翻車點整理成一張表方便你對照自查題目最容易錯的點后果對策MooBuzz下標(biāo)直接用N而不是N-1第一個點就錯用N1,2,8,9手算驗證MooBuzzint存結(jié)果大數(shù)據(jù)溢出統(tǒng)一用long longMilk Factory建圖方向建反DFS結(jié)果完全相反先畫反圖再寫代碼Milk Factory忘記memset vis上一次訪問殘留每次DFS前清空Moopx相同y降序排序答案偏大按(x, y)升序排序Moopupper_bound和lower_bound混淆鏈接不上牢記upper_bound找嚴格大于這些坑我在實際訓(xùn)練中都踩過尤其是Milk Factory的反向建圖和Moop的upper_bound幾乎每次帶新人做這套題都會有人中招。把這些坑寫在代碼注釋里能有效降低二刷時的錯誤率。6.2 排錯思路遇到WA不要急著改代碼先用小樣例跑。第一步看是不是輸入輸出文件寫錯了第二步檢查N1這種邊界第三步對照樣例手算看是算法問題還是實現(xiàn)問題。如果是對拍把隨機數(shù)據(jù)規(guī)模調(diào)到100以內(nèi)暴力解和正解結(jié)果不一致時打印出第一個不一致的輸入通常一眼就能發(fā)現(xiàn)是排序方向還是邊界處理的問題。TLE方面白銀組很少考卡常數(shù)的題只要沒有O(N^2)以上的復(fù)雜度基本不會超時真超時了優(yōu)先檢查是不是用了不必要的循環(huán)比如在Milk Factory里對每個點DFS之前沒有清空vis導(dǎo)致重復(fù)遍歷。還有一個小技巧如果你在比賽平臺上只能看到WA/TLE看不到具體測試點那就自己生成各種邊界數(shù)據(jù)比如N取最大值、所有點坐標(biāo)相同、所有邊連成一條鏈等。邊界數(shù)據(jù)往往最能暴露代碼里的假設(shè)錯誤。6.3 從這套題延伸到后續(xù)刷題計劃2019年12月這套題刷完之后建議按同樣的專題繼續(xù)推進模擬和數(shù)學(xué)規(guī)律可以刷歷年USACO的青銅組真題和Codeforces的Div2 A題圖論可以刷USACO歷年涉及DFS/BFS的Silver題排序貪心和偏序關(guān)系可以刷Moop類似題和經(jīng)典區(qū)間問題。如果目標(biāo)是GESP一級Python或者大廠筆試這些基礎(chǔ)專題同樣適用。把一套真題的三種算法吃透比囫圇吞棗刷十套題要有效得多。具體來說MooBuzz之后可以做2020年以后的Bronze/Silver模擬題注意總結(jié)“周期”“取?！薄岸执鸢浮边@些套路。Milk Factory之后可以做USACO訓(xùn)練庫里所有圖論標(biāo)簽的Silver題重點練反向建圖和多源BFS。Moop之后可以做俄羅斯套娃信封問題、最少攔截系統(tǒng)、導(dǎo)彈攔截這些經(jīng)典LIS/LDS題你會發(fā)現(xiàn)它們和Moop共享同一套數(shù)學(xué)結(jié)構(gòu)。我在實際帶隊訓(xùn)練和寫題解時最深的體會是USACO白銀組看重的不是你會多少高級算法而是能不能在數(shù)據(jù)范圍變大的時候主動從暴力思維切換到算法思維。2019年12月的MooBuzz就是這種切換最典型的教材。Moop的偏序轉(zhuǎn)化更是能讓后續(xù)很多題目產(chǎn)生“原來這題本質(zhì)是鏈覆蓋”的直覺。這套題我每年都會帶著學(xué)生重刷一遍每次都能看到有人從“只會暴力”進步到“開始想排序和建圖”這就是白銀組真題最大的價值。