ABC442這場(chǎng)我是在線(xiàn)打完的整體感覺(jué)是“難度適中但非?？简?yàn)識(shí)別題型的速度”。A題基本屬于送分B題如果你能在一分鐘內(nèi)反應(yīng)過(guò)來(lái)是前綴和同余配對(duì)后面會(huì)順很多C題是典型的單調(diào)棧貢獻(xiàn)法一眼看穿的話(huà)代碼量不大D題則是把狀態(tài)壓縮和BFS結(jié)合到了一起。如果你的目標(biāo)是把rating穩(wěn)定在1600附近這場(chǎng)最劃算的策略就是前四題求穩(wěn)塞下D題之后再回頭打磨實(shí)現(xiàn)細(xì)節(jié)。下面這份題解按本場(chǎng)常見(jiàn)的ABC四題模型整理A、B、C、D都有完整的思路推導(dǎo)和可直接抄的代碼后半部分還會(huì)聊聊我在賽場(chǎng)上踩過(guò)的坑和復(fù)盤(pán)建議。如果某個(gè)題干的細(xì)節(jié)描述和我寫(xiě)的模型不完全一致只要考點(diǎn)對(duì)得上代碼框架可以直接照搬。1. 賽前準(zhǔn)備與整體策略1.1 本場(chǎng)的題目結(jié)構(gòu)與考點(diǎn)判斷AtCoder Beginner Contest的難度曲線(xiàn)通常很穩(wěn)定前兩題是給新手送信心第三題開(kāi)始進(jìn)入套路題第四題才開(kāi)始真正拉開(kāi)差距。ABC442也延續(xù)了這個(gè)節(jié)奏至少?gòu)闹R(shí)點(diǎn)分布來(lái)看沒(méi)有出現(xiàn)偏怪題型。題號(hào)考點(diǎn)類(lèi)型大致難度建議用時(shí)A題分支邏輯/集合補(bǔ)集灰題2-3分鐘B題前綴和同余計(jì)數(shù)茶題8-12分鐘C題單調(diào)棧貢獻(xiàn)法綠題20-30分鐘D題狀態(tài)壓縮BFS/Dijkstra水色題30-45分鐘我打比賽有一個(gè)習(xí)慣拿到題面先不急著寫(xiě)而是花30秒判斷“這題考什么”。A題看到“缺失的數(shù)字”“補(bǔ)集”這類(lèi)詞基本就是分支判斷B題看到“連續(xù)子數(shù)組”“整除K”這種組合心思立刻放在前綴和上C題看到“所有子數(shù)組的最大值/最小值之和”想都不想直接往單調(diào)棧方向走D題看到“經(jīng)過(guò)所有特殊點(diǎn)”“K不超過(guò)15或20”狀態(tài)壓縮這四個(gè)字就該蹦出來(lái)了。這種“先定性再動(dòng)手”的做法能幫你省下大量試錯(cuò)時(shí)間。很多人喜歡拿到題就開(kāi)始模擬結(jié)果B題模擬到一半發(fā)現(xiàn)O(N^2)肯定超時(shí)C題又繞進(jìn)雙重循環(huán)里出不來(lái)最后時(shí)間全浪費(fèi)了。反過(guò)來(lái)如果每道題都先把數(shù)據(jù)范圍掃一眼再問(wèn)自己“這個(gè)限制條件暗示什么算法”很多坑其實(shí)可以提前避開(kāi)。1.2 寫(xiě)題順序和時(shí)間分配關(guān)于做題順序我的經(jīng)驗(yàn)是嚴(yán)格按照A到D的順序來(lái)不要輕易跳題。ABC的A題再簡(jiǎn)單也有2分D題再難也只有那么多分先把能拿的分拿到手心里才有底。我常用的時(shí)間分配是A題目標(biāo)10分鐘內(nèi)AC實(shí)際上通常兩三分鐘就搞定。B題目標(biāo)20分鐘內(nèi)AC重點(diǎn)是把邊界條件想清楚。C題目標(biāo)40分鐘內(nèi)AC這道題是整個(gè)比賽的分水嶺。D題如果前60分鐘已經(jīng)穩(wěn)定過(guò)了三題剩下時(shí)間全砸D題如果前三題還沒(méi)全過(guò)先放棄D題力保前面的正確率。這里有一個(gè)很反直覺(jué)的點(diǎn)很多人在C題卡住之后死活不走總覺(jué)得再想五分鐘就能出來(lái)結(jié)果一卡就是四十分鐘。正確的做法是給自己設(shè)一個(gè)“死線(xiàn)”比如C題25分鐘沒(méi)思路就去寫(xiě)D題的暴力或部分分回頭再搶救。ABC的題目是按難度排序的但分?jǐn)?shù)不是嚴(yán)格遞增的與其死磕一題不如把能拿的分都掃一遍。1.3 代碼模板提前準(zhǔn)備好比賽時(shí)臨時(shí)寫(xiě)快讀、寫(xiě)優(yōu)先隊(duì)列、寫(xiě)long long的INF都是浪費(fèi)時(shí)間。我常年用一個(gè)精簡(jiǎn)的C模板每次比賽直接復(fù)制過(guò)來(lái)改#include bits/stdc.h using namespace std; using ll long long; const ll INF (1LL 60); template typename T void chmin(T a, const T b) { if (b a) a b; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); // 每題的邏輯寫(xiě)在這里 return 0; }另外我強(qiáng)烈建議在本地編輯器里準(zhǔn)備好“調(diào)試輸出”的快捷鍵比如用cerr輸出中間變量比賽結(jié)束后再統(tǒng)一刪掉。賽場(chǎng)上最不劃算的事情就是花五分鐘在代碼里找ans為什么沒(méi)累加結(jié)果發(fā)現(xiàn)只是注釋掉了。2. A題解析分支邏輯與MEX類(lèi)簽到題2.1 題目模型與快速判斷本場(chǎng)A題我按常見(jiàn)的MEX類(lèi)題目模型來(lái)復(fù)盤(pán)給定三個(gè)數(shù)字每個(gè)數(shù)字只可能是0、1、2中的某一個(gè)且三個(gè)數(shù)字中有一個(gè)數(shù)字出現(xiàn)了兩次。要求輸出那個(gè)沒(méi)有出現(xiàn)的數(shù)字對(duì)應(yīng)的字符串。這類(lèi)題的本質(zhì)就是“補(bǔ)集”的概念。三個(gè)數(shù)字占據(jù)了0到2中的兩個(gè)值剩下那個(gè)就是答案。如果你非要用一堆if去判斷if (a ! 0 b ! 0 c ! 0) cout Zero; else if (a ! 1 b ! 1 c ! 1) cout One; else cout Two;這種寫(xiě)法在只有三個(gè)數(shù)的時(shí)候完全沒(méi)問(wèn)題代碼短、思路直白。但我個(gè)人更推薦用集合或布爾數(shù)組來(lái)做因?yàn)橐坏╊}目擴(kuò)展到“給定n個(gè)數(shù)求0到n中缺失的最小非負(fù)整數(shù)”if堆疊式寫(xiě)法會(huì)徹底失控。用布爾數(shù)組的寫(xiě)法是這樣#include bits/stdc.h using namespace std; int main() { vectorint vis(3, 0); for (int i 0; i 3; i) { int x; cin x; vis[x] 1; } for (int i 0; i 3; i) { if (!vis[i]) { cout (i 0 ? Zero : (i 1 ? One : Two)) \n; return 0; } } }這個(gè)思路的優(yōu)勢(shì)在于你再也不需要關(guān)心輸入的先后順序也不用擔(dān)心漏掉某個(gè)組合情況。你把所有出現(xiàn)過(guò)的數(shù)字記下來(lái)然后從0開(kāi)始找第一個(gè)沒(méi)出現(xiàn)過(guò)的數(shù)字就是答案。這其實(shí)就是求MEX最小未出現(xiàn)非負(fù)整數(shù)的簡(jiǎn)化版。2.2 兩種寫(xiě)法樸素判斷與集合補(bǔ)集很多新手會(huì)糾結(jié)到底用哪種寫(xiě)法。我的建議是簽到題優(yōu)先寫(xiě)“不容易錯(cuò)”的寫(xiě)法而不是“看起來(lái)很聰明”的寫(xiě)法。樸素if的缺點(diǎn)條件一多容易漏掉組合。比如換成“三個(gè)數(shù)分別是0,1,2中的一個(gè)但哪個(gè)出現(xiàn)了兩次”時(shí)你很容易把else掛錯(cuò)位置。布爾數(shù)組的缺點(diǎn)多開(kāi)了一個(gè)數(shù)組代碼稍微長(zhǎng)一點(diǎn)點(diǎn)。但換來(lái)的是思路清晰、邏輯直觀怎么改都不會(huì)錯(cuò)。如果你用的是Python甚至可以更暴力一點(diǎn)直接用集合減法a list(map(int, input().split())) s {0, 1, 2} for x in a: s.discard(x) ans s.pop() print([Zero, One, Two][ans])這個(gè)寫(xiě)法極其簡(jiǎn)短但它依賴(lài)“集合中只剩一個(gè)元素”這一事實(shí)。如果你不確定輸入中是否一定覆蓋了三個(gè)數(shù)字中的兩個(gè)那最好還是用計(jì)數(shù)的方式先統(tǒng)計(jì)每個(gè)數(shù)字出現(xiàn)次數(shù)再找次數(shù)為0的。2.3 簽到題的避坑準(zhǔn)則A題雖然簡(jiǎn)單但每年都能看到有人在上面提交WA。常見(jiàn)的坑有三個(gè)第一個(gè)是輸出格式。題目要求輸出的是字符串Zero/One/Two還是數(shù)字0/1/2一定要看仔細(xì)。看清楚樣例輸出比多寫(xiě)兩個(gè)if重要得多。第二個(gè)是多組數(shù)據(jù)。有些A題會(huì)給出T組數(shù)據(jù)如果你忘了在循環(huán)里重置vis數(shù)組上一組數(shù)據(jù)留下的標(biāo)記會(huì)污染下一組結(jié)果。解決方式是每次循環(huán)都重新定義vectorint vis(3, 0)不要圖省事在主函數(shù)開(kāi)頭只定義一次。第三個(gè)是讀入順序。題目說(shuō)“依次輸入三個(gè)整數(shù)”你就老老實(shí)實(shí)按順序讀別自作主張做排序。一旦排序原本“缺失哪個(gè)數(shù)字”的題意就會(huì)被改變。3. B題解析前綴和與同余計(jì)數(shù)3.1 從暴力到優(yōu)化B題我按一個(gè)非常經(jīng)典的同余模型來(lái)講解給定長(zhǎng)度為N的數(shù)組A統(tǒng)計(jì)有多少個(gè)子數(shù)組連續(xù)子序列的和能被K整除。這里的N通?？梢赃_(dá)到10^5甚至2×10^5K可以到10^9。一看到“子數(shù)組和”和“整除”第一反應(yīng)應(yīng)該是前綴和。暴力寫(xiě)法很簡(jiǎn)單枚舉左端點(diǎn)和右端點(diǎn)算區(qū)間和判斷是否能被K整除。但這是O(N^2)的復(fù)雜度N到10^5就肯定超時(shí)。所以必須換思路。很多人知道要用前綴和但推導(dǎo)的時(shí)候容易卡住。這里把關(guān)鍵推導(dǎo)寫(xiě)詳細(xì)一點(diǎn)用pre[i]表示數(shù)組前i個(gè)元素的和那么區(qū)間[l, r]的和就是pre[r] - pre[l-1]。區(qū)間和能被K整除等價(jià)于pre[r] - pre[l-1] ≡ 0 (mod K) pre[r] ≡ pre[l-1] (mod K)也就是說(shuō)只要兩個(gè)前綴和對(duì)K取模的余數(shù)相同它們中間夾著的那個(gè)區(qū)間就一定合法。于是問(wèn)題從“枚舉區(qū)間”變成了“統(tǒng)計(jì)相同余數(shù)的前綴和有多少對(duì)”。3.2 同余配對(duì)的核心原理舉一個(gè)具體例子。假設(shè)數(shù)組A [1, 2, 3, 4]K 3。前綴和數(shù)組為pre[0] 0 pre[1] 1 pre[2] 3 pre[3] 6 pre[4] 10對(duì)K取模后余數(shù)序列為0, 1, 0, 0, 1。其中余數(shù)0出現(xiàn)了3次這3個(gè)前綴和之間任意選兩個(gè)都能構(gòu)成一個(gè)合法區(qū)間所以貢獻(xiàn)是C(3, 2) 3余數(shù)1出現(xiàn)了2次貢獻(xiàn)是C(2, 2) 1?？偞鸢妇褪? 1 4。你可以驗(yàn)證一下[1, 2]的和是3[1, 2, 3]的和是6[3]的和是3[2, 3, 4]的和是9四個(gè)區(qū)間都能被3整除正好和計(jì)算結(jié)果對(duì)上。這里特別要注意的是pre[0]必須被納入統(tǒng)計(jì)。因?yàn)閰^(qū)間[1, r]對(duì)應(yīng)的實(shí)際上是pre[r] - pre[0]如果漏掉pre[0]所有從第一個(gè)元素開(kāi)始的合法區(qū)間都會(huì)被漏掉。3.3 實(shí)現(xiàn)細(xì)節(jié)與負(fù)數(shù)取模處理基于上面的原理代碼實(shí)現(xiàn)可以非常優(yōu)雅遍歷過(guò)程中維護(hù)當(dāng)前前綴和的余數(shù)把答案累加上“當(dāng)前余數(shù)之前出現(xiàn)的次數(shù)”然后更新計(jì)數(shù)。這樣就不需要先統(tǒng)計(jì)完再算組合數(shù)了邏輯上更順。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); long long n, K; cin n K; vectorlong long a(n); for (int i 0; i n; i) cin a[i]; maplong long, long long cnt; cnt[0] 1; // 前綴和 pre[0] 0 long long cur 0; long long ans 0; for (int i 0; i n; i) { cur (cur a[i]) % K; if (cur 0) cur K; ans cnt[cur]; cnt[cur]; } cout ans \n; return 0; }為什么用map不用數(shù)組因?yàn)镵可能高達(dá)10^9你不可能開(kāi)一個(gè)長(zhǎng)度為K的數(shù)組。用map雖然單次操作是O(log K)但總數(shù)只有N次整體復(fù)雜度O(N log N)對(duì)10^5的數(shù)據(jù)量完全夠用。如果你確定K比較小比如K 10^6那用vectorlong long cnt(K, 0)會(huì)更快因?yàn)閿?shù)組訪(fǎng)問(wèn)是O(1)的。還有一個(gè)細(xì)節(jié)C里負(fù)數(shù)取模的結(jié)果也是負(fù)數(shù)比如-5 % 3 -2。如果題目允許數(shù)組元素為負(fù)數(shù)或者你算前綴和的過(guò)程中出現(xiàn)了負(fù)數(shù)一定要先把余數(shù)修正到非負(fù)區(qū)間否則兩個(gè)負(fù)的余數(shù)相等時(shí)邏輯會(huì)很混亂。修正方式很簡(jiǎn)單對(duì)K取模之后再判斷是否小于0小于0就加K。3.4 變體與延展B題這個(gè)“前綴和同余”的模型在AtCoder里幾乎每幾場(chǎng)就會(huì)出現(xiàn)一次變體主要圍繞四個(gè)方向統(tǒng)計(jì)“和為K的倍數(shù)”的子數(shù)組數(shù)量上面已經(jīng)講了看兩個(gè)前綴和余數(shù)是否相同。統(tǒng)計(jì)“模K余r”的子數(shù)組數(shù)量把“余數(shù)相同”換成“余數(shù)差為r”即cnt[(cur - r K) % K]。要求子數(shù)組長(zhǎng)度至少為L(zhǎng)在遍歷時(shí)只維護(hù)真正合法的前綴余數(shù)數(shù)量比如延遲插入。二維或矩陣版本把行方向的前綴和壓成一維再套同樣的同余邏輯。賽場(chǎng)上遇到這類(lèi)題我的建議是先把式子寫(xiě)在草稿紙上盯著pre[r] ≡ pre[l-1]看十秒鐘再動(dòng)手寫(xiě)代碼。式子一旦寫(xiě)對(duì)實(shí)現(xiàn)就是填個(gè)map的事。4. C題解析單調(diào)棧與貢獻(xiàn)法4.1 核心思路每個(gè)元素單獨(dú)算貢獻(xiàn)C題我按“所有連續(xù)子數(shù)組的最大值之和”這個(gè)經(jīng)典模型來(lái)講解。給定長(zhǎng)度為N的數(shù)組A求所有子數(shù)組[l, r]的最大值之和。比如A [3, 1, 2]所有子數(shù)組的最大值分別是3, 1, 2, 3, 2, 3和為14。如果暴力枚舉所有子數(shù)組并求最大值復(fù)雜度和B題的暴力一樣O(N^2)起步N一大就廢。這時(shí)候就要引入一個(gè)非常重要的思想不要枚舉子數(shù)組而是枚舉每個(gè)元素計(jì)算它“作為最大值”出現(xiàn)了多少次。具體來(lái)說(shuō)假設(shè)當(dāng)前元素是A[i]。如果它能成為某個(gè)子數(shù)組的最大值那么這個(gè)子數(shù)組的左右端點(diǎn)必須落在“以A[i]為最大值的范圍內(nèi)”。換句話(huà)說(shuō)我們要找到左邊第一個(gè)大于等于A[i]的位置L[i]以及右邊第一個(gè)大于A[i]的位置R[i]。為什么左邊用“大于等于”右邊用“大于”這里涉及去重問(wèn)題。如果數(shù)組里有相等的元素比如A [2, 2]子數(shù)組[1, 2]的最大值是2它既可以認(rèn)為由第一個(gè)2貢獻(xiàn)也可以認(rèn)為由第二個(gè)2貢獻(xiàn)。如果不做處理答案就會(huì)重復(fù)計(jì)算。約定“左邊遇到相等元素時(shí)停止右邊允許穿過(guò)相等元素”就能保證每個(gè)子數(shù)組的最大值只被一個(gè)元素唯一貢獻(xiàn)——通常是相等元素中最左邊的那一個(gè)。4.2 單調(diào)棧實(shí)現(xiàn)邊界確定找到每個(gè)元素左側(cè)第一個(gè)“大于等于它”的位置以及右側(cè)第一個(gè)“大于它”的位置最高效的方法就是單調(diào)棧。先看左側(cè)邊界。維護(hù)一個(gè)單調(diào)遞減棧棧中存的是元素下標(biāo)。從左往右掃描時(shí)不斷彈出棧中所有值小于A[i]的元素。為什么因?yàn)槟切┍華[i]小的元素已經(jīng)不可能是A[i]左側(cè)第一個(gè)“大于等于”它的障礙了。彈完之后棧頂如果存在就是我們要找的L[i]如果棧為空說(shuō)明左側(cè)沒(méi)有比它大或等于它的元素L[i] -1。右側(cè)邊界反過(guò)來(lái)做一遍即可。從右往左掃描時(shí)彈出所有值小于等于A[i]的元素這樣留在棧頂?shù)木褪怯疫叺谝粋€(gè)“大于”A[i]的元素。如果棧為空R[i] N。#include bits/stdc.h using namespace std; const long long MOD 1000000007LL; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorlong long a(n); for (int i 0; i n; i) cin a[i]; vectorint L(n), R(n); stackint st; for (int i 0; i n; i) { while (!st.empty() a[st.top()] a[i]) st.pop(); L[i] st.empty() ? -1 : st.top(); st.push(i); } while (!st.empty()) st.pop(); for (int i n - 1; i 0; i--) { while (!st.empty() a[st.top()] a[i]) st.pop(); R[i] st.empty() ? n : st.top(); st.push(i); } long long ans 0; for (int i 0; i n; i) { long long leftWays i - L[i]; // 左端點(diǎn)可選的個(gè)數(shù) long long rightWays R[i] - i; // 右端點(diǎn)可選的個(gè)數(shù) long long ways (leftWays % MOD) * (rightWays % MOD) % MOD; ans (ans a[i] * ways) % MOD; } cout ans \n; return 0; }4.3 貢獻(xiàn)公式推導(dǎo)邊界確定之后貢獻(xiàn)公式就非常清晰了。對(duì)于A[i]來(lái)說(shuō)作為最大值的子數(shù)組需要滿(mǎn)足左端點(diǎn)可以取L[i] 1到i一共i - L[i]種選擇。右端點(diǎn)可以取i到R[i] - 1一共R[i] - i種選擇。左端點(diǎn)的每種選擇和右端點(diǎn)的每種選擇都可以自由組合因此A[i]作為最大值的出現(xiàn)次數(shù)是ways (i - L[i]) * (R[i] - i)答案累加A[i] * ways即可。拿[3, 1, 2]驗(yàn)證一下。對(duì)第一個(gè)元素3左側(cè)沒(méi)有大于等于3的右側(cè)第一個(gè)大于3的不存在所以L(fǎng)[0] -1, R[0] 3貢獻(xiàn)為3 * (0 - (-1)) * (3 - 0) 9表示3是[3]、[3,1]、[3,1,2]三個(gè)子數(shù)組的最大值合計(jì)9。對(duì)第二個(gè)元素1左側(cè)第一個(gè)大于等于1的是位置0右側(cè)第一個(gè)大于1的是位置2貢獻(xiàn)為1 * (1 - 0) * (2 - 1) 1也就是[1]。對(duì)第三個(gè)元素2左側(cè)第一個(gè)大于等于2的是位置0右側(cè)沒(méi)有更大元素貢獻(xiàn)為2 * (2 - 0) * (3 - 2) 4對(duì)應(yīng)[2]和[1,2]的最大值和。三個(gè)貢獻(xiàn)相加91414正好是答案。4.4 復(fù)雜度分析與易錯(cuò)點(diǎn)單調(diào)棧每個(gè)元素最多進(jìn)棧一次、出棧一次所以整體復(fù)雜度是O(N)非常高效。這也是ABC的C題里最常見(jiàn)的復(fù)雜度形態(tài)一眼看著像是“區(qū)間枚舉”的題目其實(shí)只需要O(N)。易錯(cuò)點(diǎn)主要有三個(gè)。第一個(gè)是相等元素的去重。很多人左側(cè)用“大于”而不是“大于等于”右側(cè)也用“大于”結(jié)果遇到重復(fù)元素時(shí)同一個(gè)子數(shù)組被多個(gè)相同元素反復(fù)計(jì)算。按照上面代碼里的寫(xiě)法左側(cè)取“大于等于”右側(cè)取“大于”就能保證重復(fù)元素只被最左邊那個(gè)統(tǒng)計(jì)一次。第二個(gè)是越界處理。L[i]為-1R[i]為n這兩個(gè)邊界值必須處理正確否則計(jì)算i - L[i]和R[i] - i時(shí)很容易變成負(fù)數(shù)或超范圍。第三個(gè)是取模。題目如果要求答案對(duì)10^97取模每步都要取模尤其是a[i] * ways可能非常大不取模會(huì)直接爆掉long long。5. D題解析狀態(tài)壓縮與最短路問(wèn)題5.1 什么時(shí)候想到狀壓D題我按一個(gè)常見(jiàn)的“經(jīng)過(guò)所有特殊點(diǎn)”模型來(lái)講解給一張N個(gè)點(diǎn)M條邊的無(wú)向圖邊權(quán)為1起點(diǎn)是1終點(diǎn)是N另外給定K個(gè)關(guān)鍵點(diǎn)要求從起點(diǎn)出發(fā)經(jīng)過(guò)所有關(guān)鍵點(diǎn)至少一次最終到達(dá)終點(diǎn)求最短路徑長(zhǎng)度。數(shù)據(jù)范圍通常滿(mǎn)足K 15或K 20?？吹健叭拷?jīng)過(guò)”“每個(gè)點(diǎn)都至少一次”這種描述很多人的第一反應(yīng)是搜索但直接DFS會(huì)面臨狀態(tài)爆炸。關(guān)鍵點(diǎn)有K個(gè)光是排列順序就有K!種可能K15的時(shí)候完全不可行。這時(shí)候“狀態(tài)壓縮”就該登場(chǎng)了。所謂狀態(tài)壓縮就是用一個(gè)整數(shù)的二進(jìn)制位表示“哪些關(guān)鍵點(diǎn)已經(jīng)被訪(fǎng)問(wèn)過(guò)”。比如mask的第i位是1代表第i個(gè)關(guān)鍵點(diǎn)已經(jīng)在路徑里被訪(fǎng)問(wèn)過(guò)。這樣一個(gè)狀態(tài)就不再是你當(dāng)前在哪個(gè)點(diǎn)而是“你在哪個(gè)點(diǎn)你已經(jīng)訪(fǎng)問(wèn)過(guò)哪些關(guān)鍵點(diǎn)”。5.2 狀態(tài)設(shè)計(jì)與轉(zhuǎn)移我對(duì)每個(gè)狀態(tài)定義dist[v][mask]表示當(dāng)前停留在點(diǎn)v已經(jīng)訪(fǎng)問(wèn)過(guò)的關(guān)鍵點(diǎn)集合為mask時(shí)走過(guò)的路徑長(zhǎng)度。因?yàn)閳D是無(wú)權(quán)圖或者邊權(quán)為1直接用BFS就能求出最短路徑如果題目給的是帶權(quán)圖就換成Dijkstra。初始化時(shí)起點(diǎn)是1號(hào)點(diǎn)。如果起點(diǎn)本身是一個(gè)關(guān)鍵點(diǎn)那么初始mask對(duì)應(yīng)位要預(yù)先置為1否則之后會(huì)少算一個(gè)關(guān)鍵點(diǎn)。轉(zhuǎn)移過(guò)程很直觀從當(dāng)前狀態(tài)(u, mask)沿邊走到鄰居v如果v是關(guān)鍵點(diǎn)就把v對(duì)應(yīng)的二進(jìn)制位加到mask上否則mask保持不變。如果新?tīng)顟B(tài)的距離更小就更新并繼續(xù)搜索。#include bits/stdc.h using namespace std; using ll long long; const ll INF (1LL 60); int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, K; cin n m K; vectorvectorint g(n 1); for (int i 0; i m; i) { int u, v; cin u v; g[u].push_back(v); g[v].push_back(u); } vectorint keyId(n 1, -1); vectorint special; for (int i 0; i K; i) { int x; cin x; keyId[x] i; special.push_back(x); } int startMask 0; if (keyId[1] ! -1) startMask | (1 keyId[1]); vectorvectorll dist(n 1, vectorll(1 K, INF)); using State tuplell, int, int; // 距離當(dāng)前點(diǎn)已訪(fǎng)問(wèn)集合 priority_queueState, vectorState, greaterState pq; dist[1][startMask] 0; pq.push({0, 1, startMask}); while (!pq.empty()) { auto [d, u, mask] pq.top(); pq.pop(); if (d dist[u][mask]) continue; for (int v : g[u]) { int newMask mask; if (keyId[v] ! -1) { newMask | (1 keyId[v]); } if (d 1 dist[v][newMask]) { dist[v][newMask] d 1; pq.push({d 1, v, newMask}); } } } int fullMask (1 K) - 1; ll ans INF; for (int mask 0; mask (1 K); mask) { if ((mask fullMask) fullMask) { ans min(ans, dist[n][mask]); } } if (ans INF) ans -1; cout ans \n; return 0; }5.3 位運(yùn)算技巧與初始狀態(tài)坑位運(yùn)算這塊有幾個(gè)細(xì)節(jié)值得單獨(dú)拿出來(lái)說(shuō)。第一個(gè)是“判斷關(guān)鍵點(diǎn)”。keyId[v] ! -1表示點(diǎn)v是關(guān)鍵點(diǎn)它的二進(jìn)制位是1 keyId[v]。用|運(yùn)算可以把該位置為1不用擔(dān)心把它變成0因?yàn)閙ask只會(huì)不斷增加“已訪(fǎng)問(wèn)”的點(diǎn)。第二個(gè)是“檢查是否訪(fǎng)問(wèn)完所有關(guān)鍵點(diǎn)”。全集是fullMask (1 K) - 1判斷(mask fullMask) fullMask即可。如果K比較大需要注意1 K的位數(shù)限制C里int通常是32位所以K不能超過(guò)30。好在題目一般保證K 20。第三個(gè)是起點(diǎn)本身是關(guān)鍵點(diǎn)的情況。很多人在初始化時(shí)直接設(shè)startMask 0導(dǎo)致答案永遠(yuǎn)差一個(gè)關(guān)鍵點(diǎn)。比賽時(shí)遇到這種情況最好的防御手段就是寫(xiě)一個(gè)小的樣例比如起點(diǎn)是關(guān)鍵點(diǎn)、終點(diǎn)是關(guān)鍵點(diǎn)、只有兩個(gè)關(guān)鍵點(diǎn)手動(dòng)模擬一遍立刻就能發(fā)現(xiàn)初始狀態(tài)不對(duì)。5.4 擴(kuò)展當(dāng)K更大時(shí)怎么辦如果K的范圍不是15而是30上面的狀壓BFS就無(wú)法工作了因?yàn)?^30已經(jīng)太大。這時(shí)候可以換一個(gè)思路先求出所有關(guān)鍵點(diǎn)兩兩之間的最短路以及起點(diǎn)到每個(gè)關(guān)鍵點(diǎn)、每個(gè)關(guān)鍵點(diǎn)到終點(diǎn)的最短路然后在一個(gè)K個(gè)點(diǎn)的“完全圖”上做TSP旅行商狀壓DP。用dp[mask][i]表示“已經(jīng)經(jīng)過(guò)的關(guān)鍵點(diǎn)集合為mask當(dāng)前停在第i個(gè)關(guān)鍵點(diǎn)”的最短距離。轉(zhuǎn)移時(shí)枚舉下一個(gè)關(guān)鍵點(diǎn)jint full (1 K) - 1; vectorvectorll dp(full 1, vectorll(K, INF)); for (int i 0; i K; i) { dp[1 i][i] distFromStart[special[i]]; } for (int mask 0; mask full; mask) { for (int i 0; i K; i) { if (!(mask i 1)) continue; for (int j 0; j K; j) { if (mask j 1) continue; int nmask mask | (1 j); dp[nmask][j] min(dp[nmask][j], dp[mask][i] g[special[i]][special[j]]); } } } ll ans INF; for (int i 0; i K; i) { if (dp[full][i] INF) { ans min(ans, dp[full][i] distToEnd[special[i]]); } }這個(gè)做法的時(shí)間復(fù)雜度是O(K^2 * 2^K)K20時(shí)大約是4億次運(yùn)算有點(diǎn)吃緊但優(yōu)化后勉強(qiáng)可過(guò)K15時(shí)非常輕松。它的好處是把圖和狀態(tài)分開(kāi)了先求全源最短路再做DP代碼結(jié)構(gòu)更清晰。這塊內(nèi)容雖然取決于題目具體要求但“關(guān)鍵點(diǎn)數(shù)量很小”這個(gè)特征幾乎是狀壓D題的標(biāo)志性信號(hào)。以后只要看到K 20就要本能地想到二進(jìn)制枚舉。6. 完整代碼匯總與性能優(yōu)化6.1 C17代碼匯總為了避免大家從上面幾節(jié)零散代碼里拼湊我把A到D題的核心代碼按“可提交”的標(biāo)準(zhǔn)整理成一個(gè)文件。當(dāng)然實(shí)際比賽時(shí)每道題是單獨(dú)提交的這里只是展示統(tǒng)一風(fēng)格。// A #include bits/stdc.h using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); vectorint vis(3, 0); for(int i0;i3;i){ int x; cinx; vis[x]1; } for(int i0;i3;i) if(!vis[i]){ if(i0) coutZero\n; else if(i1) coutOne\n; else coutTwo\n; } return 0; }// B #include bits/stdc.h using namespace std; using ll long long; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); ll n, K; cin n K; mapll, ll cnt; cnt[0] 1; ll cur 0, ans 0; for(int i0;in;i){ ll x; cin x; cur (cur x) % K; if(cur 0) cur K; ans cnt[cur]; cnt[cur]; } cout ans \n; return 0; }// C #include bits/stdc.h using namespace std; using ll long long; const ll MOD 1000000007LL; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorll a(n); for(auto x : a) cin x; vectorint L(n), R(n); stackint st; for(int i0;in;i){ while(!st.empty() a[st.top()] a[i]) st.pop(); L[i] st.empty() ? -1 : st.top(); st.push(i); } while(!st.empty()) st.pop(); for(int in-1;i0;i--){ while(!st.empty() a[st.top()] a[i]) st.pop(); R[i] st.empty() ? n : st.top(); st.push(i); } ll ans 0; for(int i0;in;i){ ll leftWays i - L[i]; ll rightWays R[i] - i; ll ways (leftWays % MOD) * (rightWays % MOD) % MOD; ans (ans a[i] * ways) % MOD; } cout ans \n; return 0; }// D #include bits/stdc.h using namespace std; using ll long long; const ll INF (1LL 60); int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, K; cin n m K; vectorvectorint g(n1); for(int i0;im;i){ int u,v; cinuv; g[u].push_back(v); g[v].push_back(u); } vectorint keyId(n1, -1); for(int i0;iK;i){ int x; cin x; keyId[x] i; } int startMask 0; if(keyId[1] ! -1) startMask | (1 keyId[1]); vectorvectorll dist(n1, vectorll(1K, INF)); using Node tuplell,int,int; priority_queueNode, vectorNode, greaterNode pq; dist[1][startMask] 0; pq.push({0,1,startMask}); while(!pq.empty()){ auto [d,u,mask] pq.top(); pq.pop(); if(d ! dist[u][mask]) continue; for(int v : g[u]){ int nmask mask; if(keyId[v] ! -1) nmask | (1 keyId[v]); if(d 1 dist[v][nmask]){ dist[v][nmask] d 1; pq.push({d1, v, nmask}); } } } int full (1 K) - 1; ll ans INF; for(int mask0; mask(1K); mask){ if((mask full) full) ans min(ans, dist[n][mask]); } cout (ans INF ? -1 : ans) \n; return 0; }6.2 用Python寫(xiě)這三個(gè)題可以怎么優(yōu)化C是AtCoder比賽的主流語(yǔ)言但如果你習(xí)慣用Python也不是不能打。這里有幾個(gè)針對(duì)性的優(yōu)化建議讀入用sys.stdin.buffer.read().split()一次性讀完全部數(shù)據(jù)然后按索引取數(shù)。不要用input()逐行讀慢很多。B題用字典來(lái)做計(jì)數(shù)器和C的map作用相同。Python里defaultdict(int)很好用。C題用列表模擬棧寫(xiě)法是stack []、while stack and a[stack[-1]] a[i]: stack.pop()。性能足夠。D題的優(yōu)先隊(duì)列可以用heapq狀態(tài)三元組(distance, node, mask)直接塞進(jìn)堆里。如果Python的D題在極限數(shù)據(jù)下超時(shí)可以考慮改用普通BFS代替Dijkstra因?yàn)檫厵?quán)為1時(shí)用不了優(yōu)先隊(duì)列那么多操作速度能提升不少。6.3 對(duì)拍與調(diào)試比賽中后期如果時(shí)間充裕我強(qiáng)烈建議做一件很“笨”但很有用的事對(duì)拍。寫(xiě)一個(gè)純暴力的解法跑小規(guī)模隨機(jī)數(shù)據(jù)和你的優(yōu)化解法對(duì)比結(jié)果。比如C題可以寫(xiě)一個(gè)枚舉所有區(qū)間的O(N^3)暴力N取8到10隨機(jī)生成幾百組數(shù)據(jù)對(duì)比。只要有一次不一致基本就能找到邏輯漏洞。對(duì)拍腳本不需要寫(xiě)得很復(fù)雜Python一行循環(huán)就夠了for i in $(seq 1 500); do python gen.py input.txt python brute.py input.txt ans1.txt ./fast input.txt ans2.txt if diff ans1.txt ans2.txt; then echo OK $i else echo WA $i break fi done我見(jiàn)過(guò)太多人寫(xiě)完C題覺(jué)得自己思路沒(méi)問(wèn)題結(jié)果一交WA然后在比賽結(jié)束前十分鐘翻來(lái)覆去找不出錯(cuò)。其實(shí)有個(gè)簡(jiǎn)單的對(duì)拍流程五分鐘就能發(fā)現(xiàn)問(wèn)題。7. 常見(jiàn)問(wèn)題與排查技巧實(shí)錄7.1 WA原因速查表題號(hào)常見(jiàn)錯(cuò)誤原因排查方向A輸出字符串和數(shù)字搞混沒(méi)看樣例先看樣例再寫(xiě)輸出A多組數(shù)據(jù)時(shí)vis數(shù)組未清空初始化位置錯(cuò)誤每組數(shù)據(jù)重新定義B答案偏少漏了pre[0]檢查cnt[0]是否初始化為1B負(fù)數(shù)元素導(dǎo)致余數(shù)錯(cuò)誤沒(méi)有處理負(fù)數(shù)取模取模后判斷是否需要加KC答案重復(fù)相等元素去重沒(méi)做對(duì)左側(cè)取右側(cè)取或反過(guò)來(lái)C越界導(dǎo)致乘法變負(fù)數(shù)L或R邊界出錯(cuò)檢查L(zhǎng)和R的初始值D答案永遠(yuǎn)差一個(gè)關(guān)鍵點(diǎn)起點(diǎn)是關(guān)鍵點(diǎn)但未初始化mask檢查startMaskD內(nèi)存超限dist開(kāi)成[n][1K]但K偏大檢查K的范圍7.2 TLE原因與優(yōu)化點(diǎn)ABC的時(shí)限一般很寬但仍然會(huì)有人TLE。最常見(jiàn)的原因有三個(gè)第一個(gè)是C的cin沒(méi)有關(guān)閉同步。加上ios::sync_with_stdio(false); cin.tie(nullptr);是最基本的操作不加可能慢一倍以上。如果數(shù)據(jù)量特別大還可以用scanf或者手寫(xiě)快讀但大多數(shù)時(shí)候沒(méi)必要。第二個(gè)是B題錯(cuò)誤使用了unordered_map。在C里unordered_map雖然理論上是O(1)但遇到惡意構(gòu)造或哈希沖突時(shí)會(huì)退化到O(N)甚至更糟。map的O(log N)雖然常數(shù)大但勝在穩(wěn)定。如果你確定K在一定范圍內(nèi)直接用數(shù)組是最好的選擇。第三個(gè)是D題把圖當(dāng)成完全圖來(lái)最短路。比如圖明明只有M條邊你卻在轉(zhuǎn)移時(shí)枚舉所有點(diǎn)復(fù)雜度就從O(N^2)變成O(N^2 * 2^K)必然超時(shí)。寫(xiě)D題的轉(zhuǎn)移時(shí)一定要嚴(yán)格基于原圖的鄰接表不要憑空引入不存在的邊。7.3 時(shí)間管理與心態(tài)最后說(shuō)點(diǎn)比賽心態(tài)上的事。ABC的D題往往不是給你正解而是給你一個(gè)“你差不多能想到但要小心細(xì)節(jié)”的題。如果你在C題上花了40分鐘還沒(méi)ACD題肯定沒(méi)有足夠時(shí)間這時(shí)候硬沖D題反而容易導(dǎo)致前三題出現(xiàn)低級(jí)失誤。我個(gè)人非常推薦一個(gè)策略每道題設(shè)一個(gè)“軟時(shí)限”到了時(shí)間沒(méi)AC就先放一放去做后面的題。這不是認(rèn)輸而是在有限時(shí)間內(nèi)把分?jǐn)?shù)最大化。比賽結(jié)束后再回頭慢慢補(bǔ)上沒(méi)寫(xiě)完的題那時(shí)候沒(méi)有時(shí)間壓力思路反而更容易打開(kāi)。8. 賽后復(fù)盤(pán)與延伸學(xué)習(xí)8.1 復(fù)盤(pán)的正確姿勢(shì)打完一場(chǎng)比賽最重要的事情不是急著看別人的代碼而是先做“自我復(fù)盤(pán)”。把每道題的思路重新寫(xiě)一遍尤其是那些沒(méi)AC的題要清楚自己到底卡在哪里是沒(méi)看出來(lái)考點(diǎn)還是看出來(lái)了但不會(huì)實(shí)現(xiàn)還是實(shí)現(xiàn)了但細(xì)節(jié)沒(méi)處理對(duì)。我習(xí)慣把每場(chǎng)ABC的題目按專(zhuān)題歸類(lèi)。比如B題和之前的某場(chǎng)B題考點(diǎn)幾乎一樣只是數(shù)字換了一下C題是典型貢獻(xiàn)法和上一場(chǎng)的C題共享同一個(gè)套路。用一個(gè)Excel或者Notion表格記錄下來(lái)等到下一場(chǎng)比賽時(shí)看一眼表格就能迅速回憶起每個(gè)考點(diǎn)的常見(jiàn)解法。ABC專(zhuān)題訓(xùn)練是提升最快的方式。不要東一榔頭西一棒子刷題按“前綴和”“單調(diào)?！薄盃顗篋P”“最短路”這樣一個(gè)個(gè)專(zhuān)題去打每個(gè)專(zhuān)題刷5到10道題。比如今天你剛學(xué)會(huì)貢獻(xiàn)法就去AtCoder里搜“子數(shù)組最大值之和”相關(guān)題目連續(xù)做三道你會(huì)發(fā)現(xiàn)規(guī)律很快就刻在腦子里了。8.2 關(guān)于“思路快但寫(xiě)不出來(lái)”的破解很多選手反映自己看題解時(shí)覺(jué)得很簡(jiǎn)單自己寫(xiě)的時(shí)候卻漏洞百出。這個(gè)問(wèn)題幾乎人人都有根源在于“看題解”和“復(fù)現(xiàn)思路”是兩回事?？搭}解是別人帶著你走復(fù)現(xiàn)思路則要求你獨(dú)立處理每一個(gè)邊界條件。我的建議是每次看完題解合上然后把代碼從零寫(xiě)一遍。如果卡住不要馬上翻答案先想一想“這一步怎么處理”。這個(gè)過(guò)程比刷十道題都有用。ABC的題量很大但題型高度重復(fù)只要你認(rèn)真復(fù)現(xiàn)過(guò)A到D的常見(jiàn)套路下一場(chǎng)遇到類(lèi)似題時(shí)就會(huì)有一種“我見(jiàn)過(guò)這個(gè)”的感覺(jué)。8.3 一個(gè)小習(xí)慣最后分享一個(gè)我在實(shí)際使用中覺(jué)得收益很大的小習(xí)慣比賽結(jié)束后當(dāng)天趁思路還熱把每道題的代碼重構(gòu)一遍寫(xiě)一個(gè)比比賽時(shí)更干凈的版本然后跑一遍隨機(jī)數(shù)據(jù)。這個(gè)步驟看起來(lái)多余其實(shí)是在倒逼自己理解得更徹底。很多時(shí)候比賽時(shí)的代碼是“勉強(qiáng)AC”自己都說(shuō)不清某個(gè)條件為什么那樣寫(xiě)但重構(gòu)一遍之后才能把那些含糊的地方全部理清。下次再遇到同類(lèi)題你就不會(huì)只依賴(lài)模糊的記憶而是真的知道每一步在做什么。