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