ABC442這場我是在線打完的整體感覺是“難度適中但非?？简?yàn)識(shí)別題型的速度”。A題基本屬于送分B題如果你能在一分鐘內(nèi)反應(yīng)過來是前綴和同余配對(duì)后面會(huì)順很多C題是典型的單調(diào)棧貢獻(xiàn)法一眼看穿的話代碼量不大D題則是把狀態(tài)壓縮和BFS結(jié)合到了一起。如果你的目標(biāo)是把rating穩(wěn)定在1600附近這場最劃算的策略就是前四題求穩(wěn)塞下D題之后再回頭打磨實(shí)現(xiàn)細(xì)節(jié)。下面這份題解按本場常見的ABC四題模型整理A、B、C、D都有完整的思路推導(dǎo)和可直接抄的代碼后半部分還會(huì)聊聊我在賽場上踩過的坑和復(fù)盤建議。如果某個(gè)題干的細(xì)節(jié)描述和我寫的模型不完全一致只要考點(diǎn)對(duì)得上代碼框架可以直接照搬。1. 賽前準(zhǔn)備與整體策略1.1 本場的題目結(jié)構(gòu)與考點(diǎn)判斷AtCoder Beginner Contest的難度曲線通常很穩(wěn)定前兩題是給新手送信心第三題開始進(jìn)入套路題第四題才開始真正拉開差距。ABC442也延續(xù)了這個(gè)節(jié)奏至少從知識(shí)點(diǎn)分布來看沒有出現(xiàn)偏怪題型。題號(hào)考點(diǎn)類型大致難度建議用時(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í)慣拿到題面先不急著寫而是花30秒判斷“這題考什么”。A題看到“缺失的數(shù)字”“補(bǔ)集”這類詞基本就是分支判斷B題看到“連續(xù)子數(shù)組”“整除K”這種組合心思立刻放在前綴和上C題看到“所有子數(shù)組的最大值/最小值之和”想都不想直接往單調(diào)棧方向走D題看到“經(jīng)過所有特殊點(diǎn)”“K不超過15或20”狀態(tài)壓縮這四個(gè)字就該蹦出來了。這種“先定性再動(dòng)手”的做法能幫你省下大量試錯(cuò)時(shí)間。很多人喜歡拿到題就開始模擬結(jié)果B題模擬到一半發(fā)現(xiàn)O(N^2)肯定超時(shí)C題又繞進(jìn)雙重循環(huán)里出不來最后時(shí)間全浪費(fèi)了。反過來如果每道題都先把數(shù)據(jù)范圍掃一眼再問自己“這個(gè)限制條件暗示什么算法”很多坑其實(shí)可以提前避開。1.2 寫題順序和時(shí)間分配關(guān)于做題順序我的經(jīng)驗(yàn)是嚴(yán)格按照A到D的順序來不要輕易跳題。ABC的A題再簡單也有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)定過了三題剩下時(shí)間全砸D題如果前三題還沒全過先放棄D題力保前面的正確率。這里有一個(gè)很反直覺的點(diǎn)很多人在C題卡住之后死活不走總覺得再想五分鐘就能出來結(jié)果一卡就是四十分鐘。正確的做法是給自己設(shè)一個(gè)“死線”比如C題25分鐘沒思路就去寫D題的暴力或部分分回頭再搶救。ABC的題目是按難度排序的但分?jǐn)?shù)不是嚴(yán)格遞增的與其死磕一題不如把能拿的分都掃一遍。1.3 代碼模板提前準(zhǔn)備好比賽時(shí)臨時(shí)寫快讀、寫優(yōu)先隊(duì)列、寫long long的INF都是浪費(fèi)時(shí)間。我常年用一個(gè)精簡的C模板每次比賽直接復(fù)制過來改#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); // 每題的邏輯寫在這里 return 0; }另外我強(qiáng)烈建議在本地編輯器里準(zhǔn)備好“調(diào)試輸出”的快捷鍵比如用cerr輸出中間變量比賽結(jié)束后再統(tǒng)一刪掉。賽場上最不劃算的事情就是花五分鐘在代碼里找ans為什么沒累加結(jié)果發(fā)現(xiàn)只是注釋掉了。2. A題解析分支邏輯與MEX類簽到題2.1 題目模型與快速判斷本場A題我按常見的MEX類題目模型來復(fù)盤給定三個(gè)數(shù)字每個(gè)數(shù)字只可能是0、1、2中的某一個(gè)且三個(gè)數(shù)字中有一個(gè)數(shù)字出現(xiàn)了兩次。要求輸出那個(gè)沒有出現(xiàn)的數(shù)字對(duì)應(yīng)的字符串。這類題的本質(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;這種寫法在只有三個(gè)數(shù)的時(shí)候完全沒問題代碼短、思路直白。但我個(gè)人更推薦用集合或布爾數(shù)組來做因?yàn)橐坏╊}目擴(kuò)展到“給定n個(gè)數(shù)求0到n中缺失的最小非負(fù)整數(shù)”if堆疊式寫法會(huì)徹底失控。用布爾數(shù)組的寫法是這樣#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)過的數(shù)字記下來然后從0開始找第一個(gè)沒出現(xiàn)過的數(shù)字就是答案。這其實(shí)就是求MEX最小未出現(xiàn)非負(fù)整數(shù)的簡化版。2.2 兩種寫法樸素判斷與集合補(bǔ)集很多新手會(huì)糾結(jié)到底用哪種寫法。我的建議是簽到題優(yōu)先寫“不容易錯(cuò)”的寫法而不是“看起來很聰明”的寫法。樸素if的缺點(diǎn)條件一多容易漏掉組合。比如換成“三個(gè)數(shù)分別是0,1,2中的一個(gè)但哪個(gè)出現(xiàn)了兩次”時(shí)你很容易把else掛錯(cuò)位置。布爾數(shù)組的缺點(diǎn)多開了一個(gè)數(shù)組代碼稍微長一點(diǎn)點(diǎn)。但換來的是思路清晰、邏輯直觀怎么改都不會(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è)寫法極其簡短但它依賴“集合中只剩一個(gè)元素”這一事實(shí)。如果你不確定輸入中是否一定覆蓋了三個(gè)數(shù)字中的兩個(gè)那最好還是用計(jì)數(shù)的方式先統(tǒng)計(jì)每個(gè)數(shù)字出現(xiàn)次數(shù)再找次數(shù)為0的。2.3 簽到題的避坑準(zhǔn)則A題雖然簡單但每年都能看到有人在上面提交WA。常見的坑有三個(gè)第一個(gè)是輸出格式。題目要求輸出的是字符串Zero/One/Two還是數(shù)字0/1/2一定要看仔細(xì)。看清楚樣例輸出比多寫兩個(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ù)開頭只定義一次。第三個(gè)是讀入順序。題目說“依次輸入三個(gè)整數(shù)”你就老老實(shí)實(shí)按順序讀別自作主張做排序。一旦排序原本“缺失哪個(gè)數(shù)字”的題意就會(huì)被改變。3. B題解析前綴和與同余計(jì)數(shù)3.1 從暴力到優(yōu)化B題我按一個(gè)非常經(jī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)該是前綴和。暴力寫法很簡單枚舉左端點(diǎn)和右端點(diǎn)算區(qū)間和判斷是否能被K整除。但這是O(N^2)的復(fù)雜度N到10^5就肯定超時(shí)。所以必須換思路。很多人知道要用前綴和但推導(dǎo)的時(shí)候容易卡住。這里把關(guān)鍵推導(dǎo)寫詳細(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)也就是說只要兩個(gè)前綴和對(duì)K取模的余數(shù)相同它們中間夾著的那個(gè)區(qū)間就一定合法。于是問題從“枚舉區(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è)元素開始的合法區(qū)間都會(huì)被漏掉。3.3 實(shí)現(xiàn)細(xì)節(jié)與負(fù)數(shù)取模處理基于上面的原理代碼實(shí)現(xiàn)可以非常優(yōu)雅遍歷過程中維護(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你不可能開一個(gè)長度為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ù)組訪問是O(1)的。還有一個(gè)細(xì)節(jié)C里負(fù)數(shù)取模的結(jié)果也是負(fù)數(shù)比如-5 % 3 -2。如果題目允許數(shù)組元素為負(fù)數(shù)或者你算前綴和的過程中出現(xiàn)了負(fù)數(shù)一定要先把余數(shù)修正到非負(fù)區(qū)間否則兩個(gè)負(fù)的余數(shù)相等時(shí)邏輯會(huì)很混亂。修正方式很簡單對(duì)K取模之后再判斷是否小于0小于0就加K。3.4 變體與延展B題這個(gè)“前綴和同余”的模型在AtCoder里幾乎每幾場就會(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ù)組長度至少為L在遍歷時(shí)只維護(hù)真正合法的前綴余數(shù)數(shù)量比如延遲插入。二維或矩陣版本把行方向的前綴和壓成一維再套同樣的同余邏輯。賽場上遇到這類題我的建議是先把式子寫在草稿紙上盯著pre[r] ≡ pre[l-1]看十秒鐘再動(dòng)手寫代碼。式子一旦寫對(duì)實(shí)現(xiàn)就是填個(gè)map的事。4. C題解析單調(diào)棧與貢獻(xiàn)法4.1 核心思路每個(gè)元素單獨(dú)算貢獻(xiàn)C題我按“所有連續(xù)子數(shù)組的最大值之和”這個(gè)經(jī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)了多少次。具體來說假設(shè)當(dāng)前元素是A[i]。如果它能成為某個(gè)子數(shù)組的最大值那么這個(gè)子數(shù)組的左右端點(diǎn)必須落在“以A[i]為最大值的范圍內(nèi)”。換句話說我們要找到左邊第一個(gè)大于等于A[i]的位置L[i]以及右邊第一個(gè)大于A[i]的位置R[i]。為什么左邊用“大于等于”右邊用“大于”這里涉及去重問題。如果數(shù)組里有相等的元素比如A [2, 2]子數(shù)組[1, 2]的最大值是2它既可以認(rèn)為由第一個(gè)2貢獻(xiàn)也可以認(rèn)為由第二個(gè)2貢獻(xiàn)。如果不做處理答案就會(huì)重復(fù)計(jì)算。約定“左邊遇到相等元素時(shí)停止右邊允許穿過相等元素”就能保證每個(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]如果棧為空說明左側(cè)沒有比它大或等于它的元素L[i] -1。右側(cè)邊界反過來做一遍即可。從右往左掃描時(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]來說作為最大值的子數(shù)組需要滿足左端點(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è)沒有大于等于3的右側(cè)第一個(gè)大于3的不存在所以L[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è)沒有更大元素貢獻(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題里最常見的復(fù)雜度形態(tài)一眼看著像是“區(qū)間枚舉”的題目其實(shí)只需要O(N)。易錯(cuò)點(diǎn)主要有三個(gè)。第一個(gè)是相等元素的去重。很多人左側(cè)用“大于”而不是“大于等于”右側(cè)也用“大于”結(jié)果遇到重復(fù)元素時(shí)同一個(gè)子數(shù)組被多個(gè)相同元素反復(fù)計(jì)算。按照上面代碼里的寫法左側(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)壓縮與最短路問題5.1 什么時(shí)候想到狀壓D題我按一個(gè)常見的“經(jīng)過所有特殊點(diǎn)”模型來講解給一張N個(gè)點(diǎn)M條邊的無向圖邊權(quán)為1起點(diǎn)是1終點(diǎn)是N另外給定K個(gè)關(guān)鍵點(diǎn)要求從起點(diǎn)出發(fā)經(jīng)過所有關(guān)鍵點(diǎn)至少一次最終到達(dá)終點(diǎn)求最短路徑長度。數(shù)據(jù)范圍通常滿足K 15或K 20。看到“全部經(jīng)過”“每個(gè)點(diǎn)都至少一次”這種描述很多人的第一反應(yīng)是搜索但直接DFS會(huì)面臨狀態(tài)爆炸。關(guān)鍵點(diǎn)有K個(gè)光是排列順序就有K!種可能K15的時(shí)候完全不可行。這時(shí)候“狀態(tài)壓縮”就該登場了。所謂狀態(tài)壓縮就是用一個(gè)整數(shù)的二進(jìn)制位表示“哪些關(guān)鍵點(diǎn)已經(jīng)被訪問過”。比如mask的第i位是1代表第i個(gè)關(guān)鍵點(diǎn)已經(jīng)在路徑里被訪問過。這樣一個(gè)狀態(tài)就不再是你當(dāng)前在哪個(gè)點(diǎn)而是“你在哪個(gè)點(diǎn)你已經(jīng)訪問過哪些關(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)訪問過的關(guān)鍵點(diǎn)集合為mask時(shí)走過的路徑長度。因?yàn)閳D是無權(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)移過程很直觀從當(dāng)前狀態(tài)(u, mask)沿邊走到鄰居v如果v是關(guān)鍵點(diǎn)就把v對(duì)應(yīng)的二進(jìn)制位加到mask上否則mask保持不變。如果新狀態(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)已訪問集合 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ú)拿出來說。第一個(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ì)不斷增加“已訪問”的點(diǎn)。第二個(gè)是“檢查是否訪問完所有關(guān)鍵點(diǎn)”。全集是fullMask (1 K) - 1判斷(mask fullMask) fullMask即可。如果K比較大需要注意1 K的位數(shù)限制C里int通常是32位所以K不能超過30。好在題目一般保證K 20。第三個(gè)是起點(diǎn)本身是關(guān)鍵點(diǎn)的情況。很多人在初始化時(shí)直接設(shè)startMask 0導(dǎo)致答案永遠(yuǎn)差一個(gè)關(guān)鍵點(diǎn)。比賽時(shí)遇到這種情況最好的防御手段就是寫一個(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就無法工作了因?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ā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)可過K15時(shí)非常輕松。它的好處是把圖和狀態(tà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寫這三個(gè)題可以怎么優(yōu)化C是AtCoder比賽的主流語言但如果你習(xí)慣用Python也不是不能打。這里有幾個(gè)針對(duì)性的優(yōu)化建議讀入用sys.stdin.buffer.read().split()一次性讀完全部數(shù)據(jù)然后按索引取數(shù)。不要用input()逐行讀慢很多。B題用字典來做計(jì)數(shù)器和C的map作用相同。Python里defaultdict(int)很好用。C題用列表模擬棧寫法是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ì)拍。寫一個(gè)純暴力的解法跑小規(guī)模隨機(jī)數(shù)據(jù)和你的優(yōu)化解法對(duì)比結(jié)果。比如C題可以寫一個(gè)枚舉所有區(qū)間的O(N^3)暴力N取8到10隨機(jī)生成幾百組數(shù)據(jù)對(duì)比。只要有一次不一致基本就能找到邏輯漏洞。對(duì)拍腳本不需要寫得很復(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我見過太多人寫完C題覺得自己思路沒問題結(jié)果一交WA然后在比賽結(jié)束前十分鐘翻來覆去找不出錯(cuò)。其實(shí)有個(gè)簡單的對(duì)拍流程五分鐘就能發(fā)現(xiàn)問題。7. 常見問題與排查技巧實(shí)錄7.1 WA原因速查表題號(hào)常見錯(cuò)誤原因排查方向A輸出字符串和數(shù)字搞混沒看樣例先看樣例再寫輸出A多組數(shù)據(jù)時(shí)vis數(shù)組未清空初始化位置錯(cuò)誤每組數(shù)據(jù)重新定義B答案偏少漏了pre[0]檢查cnt[0]是否初始化為1B負(fù)數(shù)元素導(dǎo)致余數(shù)錯(cuò)誤沒有處理負(fù)數(shù)取模取模后判斷是否需要加KC答案重復(fù)相等元素去重沒做對(duì)左側(cè)取右側(cè)取或反過來C越界導(dǎo)致乘法變負(fù)數(shù)L或R邊界出錯(cuò)檢查L和R的初始值D答案永遠(yuǎn)差一個(gè)關(guān)鍵點(diǎn)起點(diǎn)是關(guān)鍵點(diǎn)但未初始化mask檢查startMaskD內(nèi)存超限dist開成[n][1K]但K偏大檢查K的范圍7.2 TLE原因與優(yōu)化點(diǎn)ABC的時(shí)限一般很寬但仍然會(huì)有人TLE。最常見的原因有三個(gè)第一個(gè)是C的cin沒有關(guān)閉同步。加上ios::sync_with_stdio(false); cin.tie(nullptr);是最基本的操作不加可能慢一倍以上。如果數(shù)據(jù)量特別大還可以用scanf或者手寫快讀但大多數(shù)時(shí)候沒必要。第二個(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)成完全圖來最短路。比如圖明明只有M條邊你卻在轉(zhuǎn)移時(shí)枚舉所有點(diǎn)復(fù)雜度就從O(N^2)變成O(N^2 * 2^K)必然超時(shí)。寫D題的轉(zhuǎn)移時(shí)一定要嚴(yán)格基于原圖的鄰接表不要憑空引入不存在的邊。7.3 時(shí)間管理與心態(tài)最后說點(diǎn)比賽心態(tài)上的事。ABC的D題往往不是給你正解而是給你一個(gè)“你差不多能想到但要小心細(xì)節(jié)”的題。如果你在C題上花了40分鐘還沒ACD題肯定沒有足夠時(shí)間這時(shí)候硬沖D題反而容易導(dǎo)致前三題出現(xiàn)低級(jí)失誤。我個(gè)人非常推薦一個(gè)策略每道題設(shè)一個(gè)“軟時(shí)限”到了時(shí)間沒AC就先放一放去做后面的題。這不是認(rèn)輸而是在有限時(shí)間內(nèi)把分?jǐn)?shù)最大化。比賽結(jié)束后再回頭慢慢補(bǔ)上沒寫完的題那時(shí)候沒有時(shí)間壓力思路反而更容易打開。8. 賽后復(fù)盤與延伸學(xué)習(xí)8.1 復(fù)盤的正確姿勢(shì)打完一場比賽最重要的事情不是急著看別人的代碼而是先做“自我復(fù)盤”。把每道題的思路重新寫一遍尤其是那些沒AC的題要清楚自己到底卡在哪里是沒看出來考點(diǎn)還是看出來了但不會(huì)實(shí)現(xiàn)還是實(shí)現(xiàn)了但細(xì)節(jié)沒處理對(duì)。我習(xí)慣把每場ABC的題目按專題歸類。比如B題和之前的某場B題考點(diǎn)幾乎一樣只是數(shù)字換了一下C題是典型貢獻(xiàn)法和上一場的C題共享同一個(gè)套路。用一個(gè)Excel或者Notion表格記錄下來等到下一場比賽時(shí)看一眼表格就能迅速回憶起每個(gè)考點(diǎn)的常見解法。ABC專題訓(xùn)練是提升最快的方式。不要東一榔頭西一棒子刷題按“前綴和”“單調(diào)?！薄盃顗篋P”“最短路”這樣一個(gè)個(gè)專題去打每個(gè)專題刷5到10道題。比如今天你剛學(xué)會(huì)貢獻(xiàn)法就去AtCoder里搜“子數(shù)組最大值之和”相關(guān)題目連續(xù)做三道你會(huì)發(fā)現(xiàn)規(guī)律很快就刻在腦子里了。8.2 關(guān)于“思路快但寫不出來”的破解很多選手反映自己看題解時(shí)覺得很簡單自己寫的時(shí)候卻漏洞百出。這個(gè)問題幾乎人人都有根源在于“看題解”和“復(fù)現(xiàn)思路”是兩回事?？搭}解是別人帶著你走復(fù)現(xiàn)思路則要求你獨(dú)立處理每一個(gè)邊界條件。我的建議是每次看完題解合上然后把代碼從零寫一遍。如果卡住不要馬上翻答案先想一想“這一步怎么處理”。這個(gè)過程比刷十道題都有用。ABC的題量很大但題型高度重復(fù)只要你認(rèn)真復(fù)現(xiàn)過A到D的常見套路下一場遇到類似題時(shí)就會(huì)有一種“我見過這個(gè)”的感覺。8.3 一個(gè)小習(xí)慣最后分享一個(gè)我在實(shí)際使用中覺得收益很大的小習(xí)慣比賽結(jié)束后當(dāng)天趁思路還熱把每道題的代碼重構(gòu)一遍寫一個(gè)比比賽時(shí)更干凈的版本然后跑一遍隨機(jī)數(shù)據(jù)。這個(gè)步驟看起來多余其實(shí)是在倒逼自己理解得更徹底。很多時(shí)候比賽時(shí)的代碼是“勉強(qiáng)AC”自己都說不清某個(gè)條件為什么那樣寫但重構(gòu)一遍之后才能把那些含糊的地方全部理清。下次再遇到同類題你就不會(huì)只依賴模糊的記憶而是真的知道每一步在做什么。