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