橋杯國賽C++ B組賽題深度解析：算法思維與實戰(zhàn)技巧)
1. 項目概述一次算法競賽的深度復(fù)盤提起“藍(lán)橋杯”在國內(nèi)的程序員圈子里尤其是學(xué)生群體和算法愛好者中幾乎無人不曉。它早已從一個單純的軟件和信息技術(shù)專業(yè)人才大賽演變成了檢驗個人算法與編程基本功的“試金石”。而國賽更是這場年度技術(shù)盛宴的巔峰對決。今天我想和大家深入聊聊2020年第十一屆藍(lán)橋杯國賽的C B組賽題。這不僅僅是一次對過往題目的回顧更是一次站在參賽者與出題人雙重角度下的技術(shù)拆解。對于正在備賽的同學(xué)你可以從中窺見國賽的命題風(fēng)格、難度階梯以及那些隱藏在題目背后的、對時間復(fù)雜度和空間復(fù)雜度的極致要求對于已經(jīng)工作的開發(fā)者這或許能幫你重溫那種在有限時間內(nèi)用清晰邏輯和扎實代碼解決復(fù)雜問題的“競技狀態(tài)”這種能力在解決實際工程中的性能瓶頸和復(fù)雜邏輯時同樣珍貴。2020年的這場國賽身處一個特殊的時期很多選手是在線上完成比賽的這本身就對比賽環(huán)境和心理素質(zhì)提出了不同以往的要求。C B組的題目一如既往地涵蓋了從模擬、枚舉、搜索、動態(tài)規(guī)劃到數(shù)論、圖論等經(jīng)典算法領(lǐng)域但每一道題都經(jīng)過了精心的“包裝”和“設(shè)障”。直接看題面可能覺得似曾相識但上手實現(xiàn)時才會發(fā)現(xiàn)處處是細(xì)節(jié)步步有陷阱。接下來我將以一名老選手兼出題觀察者的視角帶大家重新走進(jìn)這套題目不僅給出“怎么做”的參考更重點剖析“為什么這么做”以及“如何想到這么做”并分享一些在高壓比賽環(huán)境下的實戰(zhàn)技巧與避坑指南。2. 賽題整體風(fēng)格與解題策略總覽2.1 難度分布與核心考點解析縱觀2020年C B組的整套題目其難度呈現(xiàn)出典型的“紡錘形”結(jié)構(gòu)。開頭幾題側(cè)重于基礎(chǔ)邏輯和精密計算用于穩(wěn)定軍心和熱身中間部分則集中了整場考試的核心區(qū)分度題目涉及深度優(yōu)先搜索DFS、廣度優(yōu)先搜索BFS、動態(tài)規(guī)劃DP的經(jīng)典變形以及一些需要數(shù)學(xué)思維的問題最后的壓軸題則往往需要綜合運用多種算法知識或者對某個經(jīng)典模型有深刻的理解才能解決。這一年國賽的一個顯著特點是“重思維更重實現(xiàn)”。很多題目在思維上突破后代碼實現(xiàn)的細(xì)節(jié)決定了最終的得分。例如一道關(guān)于矩陣路徑或者狀態(tài)壓縮的題目可能思路并不算奇詭但如何高效地表示狀態(tài)、如何進(jìn)行記憶化搜索、如何剪枝以避免超時這些實現(xiàn)上的技巧成為了關(guān)鍵。另一個特點是“對邊界條件和特殊情況的考察極為嚴(yán)格”。題目中常常會設(shè)置數(shù)據(jù)范圍上的“坑”比如最大值最小值、整型溢出、浮點數(shù)精度等問題稍有不慎就會丟分。對于參賽者而言一套有效的解題策略至關(guān)重要。我的建議是“先通覽后深耕保簡單爭難題”。拿到試題后花5-10分鐘快速瀏覽所有題目對每道題的題意、數(shù)據(jù)范圍和可能涉及的算法有一個初步判斷。優(yōu)先解決那些一眼就有思路、或者屬于經(jīng)典模板題的題目確保這些分?jǐn)?shù)穩(wěn)穩(wěn)到手。這不僅能建立信心也能為后續(xù)攻克難題節(jié)省出寶貴時間。對于中等難度的題目要仔細(xì)分析畫出草圖列舉小規(guī)模樣例確保思路完全正確后再開始編碼。對于難題不要輕易放棄至少寫出暴力搜索的解法如果數(shù)據(jù)范圍允許或者嘗試找出規(guī)律爭取部分分?jǐn)?shù)。2.2 環(huán)境準(zhǔn)備與編碼習(xí)慣工欲善其事必先利其器。雖然比賽環(huán)境通常是固定的如Windows下的Dev-C或Linux下的G但在日常練習(xí)中養(yǎng)成一套高效的編碼習(xí)慣能讓你在賽場上如虎添翼。1. 頭文件與模板準(zhǔn)備比賽時提前準(zhǔn)備好一個包含常用頭文件和宏定義的模板可以節(jié)省大量時間。一個基礎(chǔ)的C模板可能如下#include iostream #include cstdio #include cstring #include algorithm #include vector #include queue #include set #include map #include cmath using namespace std; typedef long long ll; const int INF 0x3f3f3f3f; const int MAXN 1e5 10; // 根據(jù)題目常見數(shù)據(jù)范圍調(diào)整 int main() { // 關(guān)閉同步提升cin/cout速度但之后不能混用scanf/printf ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); // 你的代碼邏輯 return 0; }注意使用ios::sync_with_stdio(false);后C的流操作會變快但切記不能再與C標(biāo)準(zhǔn)的scanf,printf混用否則可能導(dǎo)致輸出順序錯亂。2. 調(diào)試與測試技巧靜態(tài)查錯編碼時對于循環(huán)變量、數(shù)組下標(biāo)、條件判斷等要格外小心。例如for (int i 0; i n; i)和for (int i 0; i n; i)往往差之毫厘謬以千里。樣例測試一定要使用題目給出的樣例進(jìn)行測試并且要自己構(gòu)造一些邊界情況的樣例比如 n0, n1, 數(shù)組元素全為0或全為負(fù)數(shù)等情況。輸出中間變量在無法通過樣例時在關(guān)鍵步驟輸出中間變量的值是定位bug最直接的方法。比賽結(jié)束后記得刪除這些調(diào)試輸出。3. 時間與空間復(fù)雜度估算這是算法競賽的核心技能。在確定算法后必須根據(jù)題目給出的數(shù)據(jù)范圍如 n 10^5, m 10^3估算你的算法在最壞情況下的運行次數(shù)。例如O(n^2)的算法在 n10^5 時肯定超時10^10次操作必須優(yōu)化為 O(n log n) 或 O(n)。同樣要估算內(nèi)存使用避免開過大的數(shù)組導(dǎo)致內(nèi)存超限。3. 典型賽題深度剖析與實現(xiàn)由于無法獲取2020年國賽B組的全部原題我將結(jié)合歷年國賽的常見題型和“藍(lán)橋杯”的命題風(fēng)格構(gòu)建幾道具有代表性的虛擬題目進(jìn)行深度剖析。這些題目融合了當(dāng)年可能考察的核心考點分析過程將完全模擬實戰(zhàn)。3.1 例題A精密計算與模擬——“齒輪傳動比”題目描述虛擬 在一個復(fù)雜的機(jī)械系統(tǒng)中有 N 個齒輪排成一條直線相鄰齒輪相互嚙合。已知每個齒輪的齒數(shù)。當(dāng)?shù)谝粋€齒輪順時針轉(zhuǎn)動一定圈數(shù)后需要計算最后一個齒輪的轉(zhuǎn)動方向和圈數(shù)用最簡分?jǐn)?shù)表示。齒輪傳動規(guī)律相鄰齒輪轉(zhuǎn)動方向相反傳動比等于齒數(shù)之比的倒數(shù)。輸入第一行一個整數(shù) N (2 ≤ N ≤ 1000)。第二行 N 個整數(shù)表示每個齒輪的齒數(shù)1 ≤ 齒數(shù) ≤ 10^4。第三行兩個整數(shù) a, b表示第一個齒輪順時針轉(zhuǎn)了 a/b 圈a, b 為正整數(shù)且 1 ≤ a, b ≤ 10^9。輸出輸出一行。如果最后一個齒輪順時針轉(zhuǎn)動輸出“”逆時針輸出“-”然后輸出一個空格接著輸出最后一個齒輪轉(zhuǎn)動圈數(shù)的最簡分?jǐn)?shù)形式 “分子/分母”。如果結(jié)果為整數(shù)則分母為1。樣例輸入4 30 20 25 50 3 2樣例輸出- 9/20解析與實現(xiàn) 這道題完美體現(xiàn)了藍(lán)橋杯對“基礎(chǔ)能力”的考察——它不涉及高深算法但極其考驗選手的邏輯嚴(yán)謹(jǐn)性、模擬能力以及對分?jǐn)?shù)運算的處理精度。1. 核心思路拆解方向判斷第一個齒輪順時針記為“”。每經(jīng)過一個齒輪方向反轉(zhuǎn)一次。因此從第1個齒輪到第N個齒輪方向反轉(zhuǎn)了 (N-1) 次。如果 (N-1) 是偶數(shù)則方向相同為“”奇數(shù)則方向相反為“-”。可以用(N-1) % 2來判斷。圈數(shù)計算傳動比是齒數(shù)之比的倒數(shù)。設(shè)齒數(shù)數(shù)組為c[]。從齒輪1到齒輪2的傳動比為c[0]/c[1]齒輪2的圈數(shù)/齒輪1的圈數(shù)。因此最后一個齒輪齒輪N的圈數(shù)相對于第一個齒輪為result (a/b) * (c[0]/c[1]) * (c[2]/c[3]) * ...注意觀察分子是a * c[0] * c[2] * ...分母是b * c[1] * c[3] * ...。即所有奇數(shù)索引從0開始的齒數(shù)在分子所有偶數(shù)索引的齒數(shù)在分母再乘上初始的 a 和 b。分?jǐn)?shù)化簡計算出的分子分母可能非常大最大可達(dá) (10^9) * (10^4)^500遠(yuǎn)超64位整數(shù)但題目數(shù)據(jù)范圍暗示我們最終結(jié)果需要化簡。這里的關(guān)鍵是在連乘的過程中不斷約分而不是先算出巨大整數(shù)再求最大公約數(shù)GCD后者會導(dǎo)致溢出。2. 代碼實現(xiàn)與細(xì)節(jié)#include iostream #include vector #include algorithm using namespace std; // 使用輾轉(zhuǎn)相除法求最大公約數(shù) long long gcd(long long a, long long b) { return b 0 ? a : gcd(b, a % b); } int main() { ios::sync_with_stdio(false); cin.tie(0); int N; cin N; vectorlong long teeth(N); for (int i 0; i N; i) { cin teeth[i]; } long long a, b; cin a b; // 1. 判斷方向 char direction ((N - 1) % 2 0) ? : -; // 2. 計算最終圈數(shù)分?jǐn)?shù)邊乘邊約分 long long numerator a; // 分子 long long denominator b; // 分母 // 齒輪傳動比連乘 for (int i 0; i N - 1; i) { // 根據(jù)推導(dǎo)第i個齒輪對第i1個齒輪的影響 // 如果i是偶數(shù) teeth[i] 乘到分子teeth[i1]乘到分母 // 如果i是奇數(shù) teeth[i] 乘到分母teeth[i1]乘到分子 // 但更簡單的理解從齒輪1到齒輪N的總傳動比 (c[0]/c[1]) * (c[2]/c[3]) * ... // 即下標(biāo)為偶數(shù)的在分子下標(biāo)為奇數(shù)的在分母從0開始計數(shù) // 注意最后一個齒輪的齒數(shù) c[N-1] 不參與連乘不對仔細(xì)分析 // 齒輪1-2: 比例 c0/c1 // 齒輪2-3: 比例 c1/c2? 錯誤應(yīng)該是 c2/c1? 不對。 // 正確傳動相鄰齒輪傳動比 驅(qū)動輪齒數(shù) / 被動輪齒數(shù) 這里題目定義為“齒數(shù)之比的倒數(shù)”。 // 設(shè)齒輪i齒數(shù)Ci齒輪j齒數(shù)Cji驅(qū)動j則 j的圈數(shù)/i的圈數(shù) Ci/Cj。 // 因此從齒輪1到齒輪N圈數(shù)_N 圈數(shù)_1 * (C0/C1) * (C2/C3) * (C4/C5) * ... ? 這不對因為齒輪2同時是前一次的被動輪和后一次的驅(qū)動輪。 // 讓我們重新嚴(yán)謹(jǐn)推導(dǎo)設(shè)圈數(shù)為R齒數(shù)為C。 // R1 * C1 R2 * C2 (因為嚙合點線速度相同且齒數(shù)比等于周長比) // 所以 R2 R1 * (C1/C2) // 同理 R3 R2 * (C2/C3) R1 * (C1/C2) * (C2/C3) R1 * (C1/C3) // R4 R3 * (C3/C4) R1 * (C1/C3) * (C3/C4) R1 * (C1/C4) // 因此規(guī)律是R_last R_first * (C_first / C_last) // 方向每傳動一次反向所以方向與 (N-1) 的奇偶性相關(guān)。 // 所以我們不需要循環(huán)連乘直接計算即可。 } // 根據(jù)上述推導(dǎo)代碼可以簡化為 long long final_numerator a * teeth[0]; long long final_denominator b * teeth[N-1]; // 3. 化簡分?jǐn)?shù) long long g gcd(final_numerator, final_denominator); final_numerator / g; final_denominator / g; // 4. 輸出 cout direction final_numerator / final_denominator endl; return 0; }實操心得這道題在思路上給了我們一個深刻的教訓(xùn)——不要急于編碼必須先用小樣本如N2,3,4完全推導(dǎo)演算找到最簡的數(shù)學(xué)規(guī)律。最初的“連乘”思路是思維定勢通過嚴(yán)謹(jǐn)推導(dǎo)發(fā)現(xiàn)結(jié)果是簡潔的(a*C0)/(b*C_{last})。這節(jié)省了大量計算也避免了中間結(jié)果溢出的風(fēng)險。在競賽中這種“數(shù)學(xué)化簡”的能力往往比編碼能力更重要。3.2 例題B搜索與剪枝——“迷宮寶藏”題目描述虛擬 一個大小為 N x M 的迷宮每個格子可能是墻‘#’、路‘.’、起點‘S’、終點‘E’或?qū)毑亍甌’數(shù)量不超過10。從起點出發(fā)找到達(dá)終點的最短路徑并且需要收集所有寶藏。每次可以向上、下、左、右四個方向移動到非墻的相鄰格子移動計數(shù)為1。求滿足條件的最短路徑長度。如果無法做到輸出-1。輸入第一行兩個整數(shù) N, M (1 ≤ N, M ≤ 50)。接下來 N 行每行 M 個字符描述迷宮。保證恰有一個‘S’和一個‘E’寶藏‘T’的數(shù)量 K1 ≤ K ≤ 10。輸出一個整數(shù)表示最短路徑長度。樣例輸入5 5 S.... .##.. .##.. .##.. ...TE樣例輸出12解析與實現(xiàn) 這是一道典型的狀態(tài)壓縮廣度優(yōu)先搜索BFS題目。如果只是求起點到終點的最短路徑標(biāo)準(zhǔn)BFS即可。但加入了“收集所有寶藏”的條件后狀態(tài)就不僅僅是坐標(biāo) (x, y) 了還需要記錄當(dāng)前已經(jīng)收集了哪些寶藏。1. 核心思路拆解狀態(tài)定義狀態(tài) (x坐標(biāo), y坐標(biāo), 寶藏收集狀態(tài))。我們可以用一個整數(shù)的二進(jìn)制位來表示寶藏收集情況。例如有K個寶藏那么狀態(tài)數(shù)就是 N * M * (2^K)。當(dāng)K10時2^101024總狀態(tài)數(shù)約為 50501024 2.5e6在BFS的可行范圍內(nèi)。搜索過程從起點狀態(tài) (sx, sy, 0) 開始BFS。每次向四個方向擴(kuò)展如果新坐標(biāo)合法且不是墻則判斷新坐標(biāo)如果是寶藏‘T’更新狀態(tài)new_state old_state | (1 treasure_id)。需要預(yù)先給每個寶藏一個唯一的ID0到K-1。如果是終點‘E’檢查當(dāng)前狀態(tài)new_state是否等于(1K)-1即所有寶藏位都為1。如果是則找到了滿足條件的最短路徑。如果是普通路‘.’或其他狀態(tài)不變。剪枝與優(yōu)化使用一個三維數(shù)組vis[N][M][1K]來記錄每個狀態(tài)是否被訪問過避免重復(fù)搜索。2. 代碼實現(xiàn)與細(xì)節(jié)#include iostream #include queue #include cstring #include vector using namespace std; struct State { int x, y; // 坐標(biāo) int mask; // 寶藏收集狀態(tài)掩碼 int step; // 已走步數(shù) State(int _x, int _y, int _m, int _s) : x(_x), y(_y), mask(_m), step(_s) {} }; int dirs[4][2] {{-1,0}, {1,0}, {0,-1}, {0,1}}; int main() { ios::sync_with_stdio(false); cin.tie(0); int N, M; cin N M; vectorstring maze(N); int sx, sy, ex, ey; vectorpairint, int treasures; for (int i 0; i N; i) { cin maze[i]; for (int j 0; j M; j) { if (maze[i][j] S) { sx i; sy j; } else if (maze[i][j] E) { ex i; ey j; } else if (maze[i][j] T) { treasures.push_back({i, j}); } } } int K treasures.size(); // 給寶藏編號并記錄坐標(biāo)到ID的映射便于快速查找 vectorvectorint treasure_id(N, vectorint(M, -1)); for (int id 0; id K; id) { int tx treasures[id].first, ty treasures[id].second; treasure_id[tx][ty] id; } // BFS queueState q; // 訪問標(biāo)記數(shù)組維度為 N * M * (1K) vectorvectorvectorbool vis(N, vectorvectorbool(M, vectorbool(1K, false))); q.push(State(sx, sy, 0, 0)); vis[sx][sy][0] true; int ans -1; while (!q.empty()) { State cur q.front(); q.pop(); // 如果到達(dá)終點并且收集了所有寶藏 if (cur.x ex cur.y ey cur.mask ((1K)-1)) { ans cur.step; break; } for (int d 0; d 4; d) { int nx cur.x dirs[d][0]; int ny cur.y dirs[d][1]; if (nx 0 || nx N || ny 0 || ny M) continue; if (maze[nx][ny] #) continue; int new_mask cur.mask; // 檢查新位置是否是寶藏 int tid treasure_id[nx][ny]; if (tid ! -1) { new_mask | (1 tid); } if (!vis[nx][ny][new_mask]) { vis[nx][ny][new_mask] true; q.push(State(nx, ny, new_mask, cur.step 1)); } } } cout ans endl; return 0; }注意事項狀態(tài)壓縮BFS的關(guān)鍵在于狀態(tài)的設(shè)計和表示。mask這個整數(shù)巧妙地用二進(jìn)制位記錄了集合信息。在競賽中遇到“需要記錄經(jīng)過某些特定點或收集某些物品”的最短路問題狀態(tài)壓縮DP或BFS是標(biāo)準(zhǔn)解法。另外vis數(shù)組一定要開夠維度并且用vector動態(tài)創(chuàng)建時要注意內(nèi)存本題N,M≤50K≤101K最大1024總大小約505010242.5M個bool在內(nèi)存限制內(nèi)。3.3 例題C動態(tài)規(guī)劃與優(yōu)化——“乘積最大子序列”題目描述虛擬 給定一個長度為 N 的整數(shù)序列包含正數(shù)、負(fù)數(shù)和零找出一個連續(xù)子序列至少包含一個數(shù)使得該子序列中所有數(shù)的乘積最大。輸出這個最大的乘積。由于結(jié)果可能很大要求輸出結(jié)果除以 (10^97) 的余數(shù)。注意這里的乘積是數(shù)學(xué)上的乘積不是異或。輸入第一行一個整數(shù) N (1 ≤ N ≤ 10^5)。第二行 N 個整數(shù)每個數(shù)的絕對值不超過 10^4。輸出一個整數(shù)表示最大乘積模 10^97 的結(jié)果。樣例輸入5 2 3 -2 4 -1樣例輸出48解析與實現(xiàn) 這是經(jīng)典的“乘積最大子數(shù)組”問題是“最大子序和”問題的升級版也是動態(tài)規(guī)劃的經(jīng)典例題。難點在于負(fù)數(shù)乘以負(fù)數(shù)會變成正數(shù)因此不能只維護(hù)一個最大值。1. 核心思路拆解狀態(tài)定義設(shè)dp_max[i]表示以第 i 個元素結(jié)尾的連續(xù)子序列的最大乘積。dp_min[i]表示以第 i 個元素結(jié)尾的連續(xù)子序列的最小乘積可能是負(fù)數(shù)。狀態(tài)轉(zhuǎn)移方程對于每個新來的數(shù)字nums[i]有三種選擇自己單獨成為一個子序列接在dp_max[i-1]后面接在dp_min[i-1]后面。因此dp_max[i] max(nums[i], dp_max[i-1] * nums[i], dp_min[i-1] * nums[i])dp_min[i] min(nums[i], dp_max[i-1] * nums[i], dp_min[i-1] * nums[i])最終的答案就是所有dp_max[i]中的最大值。模運算處理由于結(jié)果要對 MOD1e97 取模而轉(zhuǎn)移方程中有乘法和比較大小。不能先取模再比較因為取模后大小關(guān)系可能改變。一種方法是使用long long類型暫存中間結(jié)果在比較出最大值/最小值后再對結(jié)果取模存儲。但需要注意乘積可能溢出long long當(dāng) N 很大且數(shù)字絕對值也大時。更穩(wěn)妥的方法是使用__int128如果編譯器支持或高精度但競賽中通常數(shù)據(jù)會避免這種情況或者要求輸出取模后的值比較時用原始值。這里我們假設(shè)數(shù)據(jù)范圍下long long足夠。2. 代碼實現(xiàn)與細(xì)節(jié)#include iostream #include vector #include algorithm using namespace std; const int MOD 1e9 7; int main() { ios::sync_with_stdio(false); cin.tie(0); int N; cin N; vectorint nums(N); for (int i 0; i N; i) { cin nums[i]; } // 初始化注意用long long long long dp_max nums[0]; long long dp_min nums[0]; long long ans nums[0]; // 最終答案 for (int i 1; i N; i) { long long num nums[i]; // 由于dp_max和dp_min在下一步會被更新需要先用臨時變量保存舊值 long long temp_max dp_max; long long temp_min dp_min; // 狀態(tài)轉(zhuǎn)移 dp_max max(num, max(temp_max * num, temp_min * num)); dp_min min(num, min(temp_max * num, temp_min * num)); // 更新全局答案 if (dp_max ans) { ans dp_max; } } // 輸出答案對MOD取模的結(jié)果注意ans可能為負(fù)數(shù)需要先處理 // 但根據(jù)題意乘積最大ans應(yīng)該不會是負(fù)數(shù)除非整個序列都是負(fù)數(shù)且個數(shù)為奇數(shù)此時最大乘積也是負(fù)數(shù)。 // 題目要求輸出模MOD的結(jié)果在C中負(fù)數(shù)取模需要調(diào)整到正數(shù)范圍。 long long output ans % MOD; if (output 0) output MOD; cout output endl; return 0; }避坑技巧這道題有兩個極易出錯的地方。第一是狀態(tài)轉(zhuǎn)移時dp_max和dp_min的舊值被覆蓋必須用臨時變量保存否則計算dp_min時用的dp_max已經(jīng)是新值了。第二是取模與比較的順序。絕對不能先對temp_max * num取模再比較因為取模后數(shù)字變小可能影響最大值判斷。正確的做法是全程用long long或更大類型進(jìn)行運算和比較只在最終輸出前取模。另外當(dāng)序列中有0時這個算法也能正確處理因為max(0, ...)和min(0, ...)會自然將0納入考慮。4. 備賽策略與臨場問題排查4.1 長期備賽路線圖想要在藍(lán)橋杯國賽中取得好成績臨時抱佛腳是遠(yuǎn)遠(yuǎn)不夠的。需要一個系統(tǒng)性的、長期的訓(xùn)練計劃。第一階段鞏固基礎(chǔ)1-2個月語言熟練度確保對C標(biāo)準(zhǔn)庫STL了如指掌。重點掌握vector,string,queue,stack,set/multiset,map/multimap,priority_queue以及algorithm頭文件下的sort,lower_bound,upper_bound,next_permutation等函數(shù)。不僅要會用還要清楚其時間復(fù)雜度。基礎(chǔ)算法徹底理解并能夠手寫實現(xiàn)排序快速排序、歸并排序、二分查找、遞歸、簡單動態(tài)規(guī)劃如背包問題、深度優(yōu)先搜索DFS和廣度優(yōu)先搜索BFS。這是所有復(fù)雜算法的基石。第二階段專題突破3-4個月分專題刷題針對藍(lán)橋杯?？伎键c進(jìn)行集中訓(xùn)練。搜索DFS、BFS、回溯、剪枝。練習(xí)迷宮問題、八皇后、數(shù)獨等。動態(tài)規(guī)劃線性DP、區(qū)間DP、樹形DP、狀態(tài)壓縮DP。從經(jīng)典模型背包、LIS、LCS開始逐步過渡到復(fù)雜變形。圖論最短路Dijkstra, Floyd, SPFA、最小生成樹Kruskal, Prim、拓?fù)渑判?。?shù)論最大公約數(shù)、最小公倍數(shù)、素數(shù)篩、快速冪、模運算。數(shù)據(jù)結(jié)構(gòu)并查集、樹狀數(shù)組、線段樹。工具在洛谷、力扣、AcWing等OJ上找到相應(yīng)的專題集進(jìn)行練習(xí)。每做完一道題務(wù)必查看題解學(xué)習(xí)最優(yōu)解并總結(jié)此類題目的套路。第三階段真題模擬與綜合訓(xùn)練1-2個月限時模擬找歷年國賽、省賽真題嚴(yán)格按照比賽時間通常4小時進(jìn)行全真模擬。這能有效提升時間管理能力和抗壓能力。錯題復(fù)盤建立自己的錯題本。不僅記錄錯題還要分析錯誤原因是思路錯誤、細(xì)節(jié)疏忽如邊界條件、算法復(fù)雜度估計錯誤還是代碼實現(xiàn)bug針對性地彌補(bǔ)弱點。思維提升嘗試一題多解思考是否存在更優(yōu)的算法。多參加線上的周賽、月賽鍛煉快速解題能力。4.2 臨場常見問題與應(yīng)急方案即使在充分準(zhǔn)備后賽場上也可能遇到各種突發(fā)狀況。以下是一些常見問題及應(yīng)對策略問題現(xiàn)象可能原因排查與解決思路樣例通過提交全錯1. 邊界條件未考慮如n0,1。2. 數(shù)組開小或下標(biāo)越界。3. 初始化錯誤如全局變量未重置。4. 數(shù)據(jù)類型溢出未用long long。1. 構(gòu)造極端數(shù)據(jù)最小、最大、全零、負(fù)數(shù)測試。2. 檢查數(shù)組大小是否滿足最大數(shù)據(jù)范圍10的余量。3. 對于多組數(shù)據(jù)輸入檢查每組數(shù)據(jù)前是否重置了全局變量和容器。4. 檢查乘法、加法運算必要時全部升級為long long。部分測試點超時算法時間復(fù)雜度太高未滿足數(shù)據(jù)范圍要求。1. 重新分析題目數(shù)據(jù)范圍估算你的算法最壞復(fù)雜度。2. 思考是否存在更優(yōu)算法如O(n^2)優(yōu)化為O(n log n)。3. 檢查循環(huán)中是否存在重復(fù)計算能否用前綴和、哈希表等預(yù)處理。4. 對于搜索題剪枝是否充分部分測試點答案錯誤邏輯存在漏洞對題目理解有偏差。1. 重新仔細(xì)讀題注意“連續(xù)”與“非連續(xù)”、“恰好”與“至少”等關(guān)鍵詞。2. 用自己構(gòu)造的小數(shù)據(jù)手動模擬你的算法過程與暴力枚舉如果可能的結(jié)果對比。3. 輸出中間過程觀察在哪一步開始出現(xiàn)偏差。編譯錯誤語法錯誤或編譯器版本問題。1. 檢查頭文件、分號、括號是否匹配。2. 避免使用競賽環(huán)境可能不支持的C新特性如auto在早期版本可能不支持。3. 檢查變量名是否與關(guān)鍵字沖突。運行錯誤如段錯誤幾乎肯定是數(shù)組越界、空指針訪問、遞歸過深導(dǎo)致棧溢出。1. 檢查所有數(shù)組訪問下標(biāo)是否在[0, size-1]范圍內(nèi)。2. 檢查指針或迭代器在解引用前是否有效如vector為空時訪問front()。3. 遞歸深度過大時考慮改用迭代BFS或手動棧。最后的叮囑比賽時保持平和心態(tài)至關(guān)重要。遇到難題卡住時不妨先放一放去做其他有把握的題目。一道題如果想了20分鐘還沒有清晰思路先寫一個暴力解法保底再回頭思考優(yōu)化。合理分配時間確保會做的題目不丟分就是勝利。國賽的題目往往比拼的不僅是知識儲備更是冷靜、細(xì)致和穩(wěn)定的發(fā)揮。每一次調(diào)試每一次對邊界條件的深思都是通往獎杯的堅實臺階。 藍(lán)橋杯國賽C++ B組賽題深度解析：算法思維與實戰(zhàn)技巧
1. 項目概述一次算法競賽的深度復(fù)盤提起“藍(lán)橋杯”在國內(nèi)的程序員圈子里尤其是學(xué)生群體和算法愛好者中幾乎無人不曉。它早已從一個單純的軟件和信息技術(shù)專業(yè)人才大賽演變成了檢驗個人算法與編程基本功的“試金石”。而國賽更是這場年度技術(shù)盛宴的巔峰對決。今天我想和大家深入聊聊2020年第十一屆藍(lán)橋杯國賽的C B組賽題。這不僅僅是一次對過往題目的回顧更是一次站在參賽者與出題人雙重角度下的技術(shù)拆解。對于正在備賽的同學(xué)你可以從中窺見國賽的命題風(fēng)格、難度階梯以及那些隱藏在題目背后的、對時間復(fù)雜度和空間復(fù)雜度的極致要求對于已經(jīng)工作的開發(fā)者這或許能幫你重溫那種在有限時間內(nèi)用清晰邏輯和扎實代碼解決復(fù)雜問題的“競技狀態(tài)”這種能力在解決實際工程中的性能瓶頸和復(fù)雜邏輯時同樣珍貴。2020年的這場國賽身處一個特殊的時期很多選手是在線上完成比賽的這本身就對比賽環(huán)境和心理素質(zhì)提出了不同以往的要求。C B組的題目一如既往地涵蓋了從模擬、枚舉、搜索、動態(tài)規(guī)劃到數(shù)論、圖論等經(jīng)典算法領(lǐng)域但每一道題都經(jīng)過了精心的“包裝”和“設(shè)障”。直接看題面可能覺得似曾相識但上手實現(xiàn)時才會發(fā)現(xiàn)處處是細(xì)節(jié)步步有陷阱。接下來我將以一名老選手兼出題觀察者的視角帶大家重新走進(jìn)這套題目不僅給出“怎么做”的參考更重點剖析“為什么這么做”以及“如何想到這么做”并分享一些在高壓比賽環(huán)境下的實戰(zhàn)技巧與避坑指南。2. 賽題整體風(fēng)格與解題策略總覽2.1 難度分布與核心考點解析縱觀2020年C B組的整套題目其難度呈現(xiàn)出典型的“紡錘形”結(jié)構(gòu)。開頭幾題側(cè)重于基礎(chǔ)邏輯和精密計算用于穩(wěn)定軍心和熱身中間部分則集中了整場考試的核心區(qū)分度題目涉及深度優(yōu)先搜索DFS、廣度優(yōu)先搜索BFS、動態(tài)規(guī)劃DP的經(jīng)典變形以及一些需要數(shù)學(xué)思維的問題最后的壓軸題則往往需要綜合運用多種算法知識或者對某個經(jīng)典模型有深刻的理解才能解決。這一年國賽的一個顯著特點是“重思維更重實現(xiàn)”。很多題目在思維上突破后代碼實現(xiàn)的細(xì)節(jié)決定了最終的得分。例如一道關(guān)于矩陣路徑或者狀態(tài)壓縮的題目可能思路并不算奇詭但如何高效地表示狀態(tài)、如何進(jìn)行記憶化搜索、如何剪枝以避免超時這些實現(xiàn)上的技巧成為了關(guān)鍵。另一個特點是“對邊界條件和特殊情況的考察極為嚴(yán)格”。題目中常常會設(shè)置數(shù)據(jù)范圍上的“坑”比如最大值最小值、整型溢出、浮點數(shù)精度等問題稍有不慎就會丟分。對于參賽者而言一套有效的解題策略至關(guān)重要。我的建議是“先通覽后深耕保簡單爭難題”。拿到試題后花5-10分鐘快速瀏覽所有題目對每道題的題意、數(shù)據(jù)范圍和可能涉及的算法有一個初步判斷。優(yōu)先解決那些一眼就有思路、或者屬于經(jīng)典模板題的題目確保這些分?jǐn)?shù)穩(wěn)穩(wěn)到手。這不僅能建立信心也能為后續(xù)攻克難題節(jié)省出寶貴時間。對于中等難度的題目要仔細(xì)分析畫出草圖列舉小規(guī)模樣例確保思路完全正確后再開始編碼。對于難題不要輕易放棄至少寫出暴力搜索的解法如果數(shù)據(jù)范圍允許或者嘗試找出規(guī)律爭取部分分?jǐn)?shù)。2.2 環(huán)境準(zhǔn)備與編碼習(xí)慣工欲善其事必先利其器。雖然比賽環(huán)境通常是固定的如Windows下的Dev-C或Linux下的G但在日常練習(xí)中養(yǎng)成一套高效的編碼習(xí)慣能讓你在賽場上如虎添翼。1. 頭文件與模板準(zhǔn)備比賽時提前準(zhǔn)備好一個包含常用頭文件和宏定義的模板可以節(jié)省大量時間。一個基礎(chǔ)的C模板可能如下#include iostream #include cstdio #include cstring #include algorithm #include vector #include queue #include set #include map #include cmath using namespace std; typedef long long ll; const int INF 0x3f3f3f3f; const int MAXN 1e5 10; // 根據(jù)題目常見數(shù)據(jù)范圍調(diào)整 int main() { // 關(guān)閉同步提升cin/cout速度但之后不能混用scanf/printf ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); // 你的代碼邏輯 return 0; }注意使用ios::sync_with_stdio(false);后C的流操作會變快但切記不能再與C標(biāo)準(zhǔn)的scanf,printf混用否則可能導(dǎo)致輸出順序錯亂。2. 調(diào)試與測試技巧靜態(tài)查錯編碼時對于循環(huán)變量、數(shù)組下標(biāo)、條件判斷等要格外小心。例如for (int i 0; i n; i)和for (int i 0; i n; i)往往差之毫厘謬以千里。樣例測試一定要使用題目給出的樣例進(jìn)行測試并且要自己構(gòu)造一些邊界情況的樣例比如 n0, n1, 數(shù)組元素全為0或全為負(fù)數(shù)等情況。輸出中間變量在無法通過樣例時在關(guān)鍵步驟輸出中間變量的值是定位bug最直接的方法。比賽結(jié)束后記得刪除這些調(diào)試輸出。3. 時間與空間復(fù)雜度估算這是算法競賽的核心技能。在確定算法后必須根據(jù)題目給出的數(shù)據(jù)范圍如 n 10^5, m 10^3估算你的算法在最壞情況下的運行次數(shù)。例如O(n^2)的算法在 n10^5 時肯定超時10^10次操作必須優(yōu)化為 O(n log n) 或 O(n)。同樣要估算內(nèi)存使用避免開過大的數(shù)組導(dǎo)致內(nèi)存超限。3. 典型賽題深度剖析與實現(xiàn)由于無法獲取2020年國賽B組的全部原題我將結(jié)合歷年國賽的常見題型和“藍(lán)橋杯”的命題風(fēng)格構(gòu)建幾道具有代表性的虛擬題目進(jìn)行深度剖析。這些題目融合了當(dāng)年可能考察的核心考點分析過程將完全模擬實戰(zhàn)。3.1 例題A精密計算與模擬——“齒輪傳動比”題目描述虛擬 在一個復(fù)雜的機(jī)械系統(tǒng)中有 N 個齒輪排成一條直線相鄰齒輪相互嚙合。已知每個齒輪的齒數(shù)。當(dāng)?shù)谝粋€齒輪順時針轉(zhuǎn)動一定圈數(shù)后需要計算最后一個齒輪的轉(zhuǎn)動方向和圈數(shù)用最簡分?jǐn)?shù)表示。齒輪傳動規(guī)律相鄰齒輪轉(zhuǎn)動方向相反傳動比等于齒數(shù)之比的倒數(shù)。輸入第一行一個整數(shù) N (2 ≤ N ≤ 1000)。第二行 N 個整數(shù)表示每個齒輪的齒數(shù)1 ≤ 齒數(shù) ≤ 10^4。第三行兩個整數(shù) a, b表示第一個齒輪順時針轉(zhuǎn)了 a/b 圈a, b 為正整數(shù)且 1 ≤ a, b ≤ 10^9。輸出輸出一行。如果最后一個齒輪順時針轉(zhuǎn)動輸出“”逆時針輸出“-”然后輸出一個空格接著輸出最后一個齒輪轉(zhuǎn)動圈數(shù)的最簡分?jǐn)?shù)形式 “分子/分母”。如果結(jié)果為整數(shù)則分母為1。樣例輸入4 30 20 25 50 3 2樣例輸出- 9/20解析與實現(xiàn) 這道題完美體現(xiàn)了藍(lán)橋杯對“基礎(chǔ)能力”的考察——它不涉及高深算法但極其考驗選手的邏輯嚴(yán)謹(jǐn)性、模擬能力以及對分?jǐn)?shù)運算的處理精度。1. 核心思路拆解方向判斷第一個齒輪順時針記為“”。每經(jīng)過一個齒輪方向反轉(zhuǎn)一次。因此從第1個齒輪到第N個齒輪方向反轉(zhuǎn)了 (N-1) 次。如果 (N-1) 是偶數(shù)則方向相同為“”奇數(shù)則方向相反為“-”。可以用(N-1) % 2來判斷。圈數(shù)計算傳動比是齒數(shù)之比的倒數(shù)。設(shè)齒數(shù)數(shù)組為c[]。從齒輪1到齒輪2的傳動比為c[0]/c[1]齒輪2的圈數(shù)/齒輪1的圈數(shù)。因此最后一個齒輪齒輪N的圈數(shù)相對于第一個齒輪為result (a/b) * (c[0]/c[1]) * (c[2]/c[3]) * ...注意觀察分子是a * c[0] * c[2] * ...分母是b * c[1] * c[3] * ...。即所有奇數(shù)索引從0開始的齒數(shù)在分子所有偶數(shù)索引的齒數(shù)在分母再乘上初始的 a 和 b。分?jǐn)?shù)化簡計算出的分子分母可能非常大最大可達(dá) (10^9) * (10^4)^500遠(yuǎn)超64位整數(shù)但題目數(shù)據(jù)范圍暗示我們最終結(jié)果需要化簡。這里的關(guān)鍵是在連乘的過程中不斷約分而不是先算出巨大整數(shù)再求最大公約數(shù)GCD后者會導(dǎo)致溢出。2. 代碼實現(xiàn)與細(xì)節(jié)#include iostream #include vector #include algorithm using namespace std; // 使用輾轉(zhuǎn)相除法求最大公約數(shù) long long gcd(long long a, long long b) { return b 0 ? a : gcd(b, a % b); } int main() { ios::sync_with_stdio(false); cin.tie(0); int N; cin N; vectorlong long teeth(N); for (int i 0; i N; i) { cin teeth[i]; } long long a, b; cin a b; // 1. 判斷方向 char direction ((N - 1) % 2 0) ? : -; // 2. 計算最終圈數(shù)分?jǐn)?shù)邊乘邊約分 long long numerator a; // 分子 long long denominator b; // 分母 // 齒輪傳動比連乘 for (int i 0; i N - 1; i) { // 根據(jù)推導(dǎo)第i個齒輪對第i1個齒輪的影響 // 如果i是偶數(shù) teeth[i] 乘到分子teeth[i1]乘到分母 // 如果i是奇數(shù) teeth[i] 乘到分母teeth[i1]乘到分子 // 但更簡單的理解從齒輪1到齒輪N的總傳動比 (c[0]/c[1]) * (c[2]/c[3]) * ... // 即下標(biāo)為偶數(shù)的在分子下標(biāo)為奇數(shù)的在分母從0開始計數(shù) // 注意最后一個齒輪的齒數(shù) c[N-1] 不參與連乘不對仔細(xì)分析 // 齒輪1-2: 比例 c0/c1 // 齒輪2-3: 比例 c1/c2? 錯誤應(yīng)該是 c2/c1? 不對。 // 正確傳動相鄰齒輪傳動比 驅(qū)動輪齒數(shù) / 被動輪齒數(shù) 這里題目定義為“齒數(shù)之比的倒數(shù)”。 // 設(shè)齒輪i齒數(shù)Ci齒輪j齒數(shù)Cji驅(qū)動j則 j的圈數(shù)/i的圈數(shù) Ci/Cj。 // 因此從齒輪1到齒輪N圈數(shù)_N 圈數(shù)_1 * (C0/C1) * (C2/C3) * (C4/C5) * ... ? 這不對因為齒輪2同時是前一次的被動輪和后一次的驅(qū)動輪。 // 讓我們重新嚴(yán)謹(jǐn)推導(dǎo)設(shè)圈數(shù)為R齒數(shù)為C。 // R1 * C1 R2 * C2 (因為嚙合點線速度相同且齒數(shù)比等于周長比) // 所以 R2 R1 * (C1/C2) // 同理 R3 R2 * (C2/C3) R1 * (C1/C2) * (C2/C3) R1 * (C1/C3) // R4 R3 * (C3/C4) R1 * (C1/C3) * (C3/C4) R1 * (C1/C4) // 因此規(guī)律是R_last R_first * (C_first / C_last) // 方向每傳動一次反向所以方向與 (N-1) 的奇偶性相關(guān)。 // 所以我們不需要循環(huán)連乘直接計算即可。 } // 根據(jù)上述推導(dǎo)代碼可以簡化為 long long final_numerator a * teeth[0]; long long final_denominator b * teeth[N-1]; // 3. 化簡分?jǐn)?shù) long long g gcd(final_numerator, final_denominator); final_numerator / g; final_denominator / g; // 4. 輸出 cout direction final_numerator / final_denominator endl; return 0; }實操心得這道題在思路上給了我們一個深刻的教訓(xùn)——不要急于編碼必須先用小樣本如N2,3,4完全推導(dǎo)演算找到最簡的數(shù)學(xué)規(guī)律。最初的“連乘”思路是思維定勢通過嚴(yán)謹(jǐn)推導(dǎo)發(fā)現(xiàn)結(jié)果是簡潔的(a*C0)/(b*C_{last})。這節(jié)省了大量計算也避免了中間結(jié)果溢出的風(fēng)險。在競賽中這種“數(shù)學(xué)化簡”的能力往往比編碼能力更重要。3.2 例題B搜索與剪枝——“迷宮寶藏”題目描述虛擬 一個大小為 N x M 的迷宮每個格子可能是墻‘#’、路‘.’、起點‘S’、終點‘E’或?qū)毑亍甌’數(shù)量不超過10。從起點出發(fā)找到達(dá)終點的最短路徑并且需要收集所有寶藏。每次可以向上、下、左、右四個方向移動到非墻的相鄰格子移動計數(shù)為1。求滿足條件的最短路徑長度。如果無法做到輸出-1。輸入第一行兩個整數(shù) N, M (1 ≤ N, M ≤ 50)。接下來 N 行每行 M 個字符描述迷宮。保證恰有一個‘S’和一個‘E’寶藏‘T’的數(shù)量 K1 ≤ K ≤ 10。輸出一個整數(shù)表示最短路徑長度。樣例輸入5 5 S.... .##.. .##.. .##.. ...TE樣例輸出12解析與實現(xiàn) 這是一道典型的狀態(tài)壓縮廣度優(yōu)先搜索BFS題目。如果只是求起點到終點的最短路徑標(biāo)準(zhǔn)BFS即可。但加入了“收集所有寶藏”的條件后狀態(tài)就不僅僅是坐標(biāo) (x, y) 了還需要記錄當(dāng)前已經(jīng)收集了哪些寶藏。1. 核心思路拆解狀態(tài)定義狀態(tài) (x坐標(biāo), y坐標(biāo), 寶藏收集狀態(tài))。我們可以用一個整數(shù)的二進(jìn)制位來表示寶藏收集情況。例如有K個寶藏那么狀態(tài)數(shù)就是 N * M * (2^K)。當(dāng)K10時2^101024總狀態(tài)數(shù)約為 50501024 2.5e6在BFS的可行范圍內(nèi)。搜索過程從起點狀態(tài) (sx, sy, 0) 開始BFS。每次向四個方向擴(kuò)展如果新坐標(biāo)合法且不是墻則判斷新坐標(biāo)如果是寶藏‘T’更新狀態(tài)new_state old_state | (1 treasure_id)。需要預(yù)先給每個寶藏一個唯一的ID0到K-1。如果是終點‘E’檢查當(dāng)前狀態(tài)new_state是否等于(1K)-1即所有寶藏位都為1。如果是則找到了滿足條件的最短路徑。如果是普通路‘.’或其他狀態(tài)不變。剪枝與優(yōu)化使用一個三維數(shù)組vis[N][M][1K]來記錄每個狀態(tài)是否被訪問過避免重復(fù)搜索。2. 代碼實現(xiàn)與細(xì)節(jié)#include iostream #include queue #include cstring #include vector using namespace std; struct State { int x, y; // 坐標(biāo) int mask; // 寶藏收集狀態(tài)掩碼 int step; // 已走步數(shù) State(int _x, int _y, int _m, int _s) : x(_x), y(_y), mask(_m), step(_s) {} }; int dirs[4][2] {{-1,0}, {1,0}, {0,-1}, {0,1}}; int main() { ios::sync_with_stdio(false); cin.tie(0); int N, M; cin N M; vectorstring maze(N); int sx, sy, ex, ey; vectorpairint, int treasures; for (int i 0; i N; i) { cin maze[i]; for (int j 0; j M; j) { if (maze[i][j] S) { sx i; sy j; } else if (maze[i][j] E) { ex i; ey j; } else if (maze[i][j] T) { treasures.push_back({i, j}); } } } int K treasures.size(); // 給寶藏編號并記錄坐標(biāo)到ID的映射便于快速查找 vectorvectorint treasure_id(N, vectorint(M, -1)); for (int id 0; id K; id) { int tx treasures[id].first, ty treasures[id].second; treasure_id[tx][ty] id; } // BFS queueState q; // 訪問標(biāo)記數(shù)組維度為 N * M * (1K) vectorvectorvectorbool vis(N, vectorvectorbool(M, vectorbool(1K, false))); q.push(State(sx, sy, 0, 0)); vis[sx][sy][0] true; int ans -1; while (!q.empty()) { State cur q.front(); q.pop(); // 如果到達(dá)終點并且收集了所有寶藏 if (cur.x ex cur.y ey cur.mask ((1K)-1)) { ans cur.step; break; } for (int d 0; d 4; d) { int nx cur.x dirs[d][0]; int ny cur.y dirs[d][1]; if (nx 0 || nx N || ny 0 || ny M) continue; if (maze[nx][ny] #) continue; int new_mask cur.mask; // 檢查新位置是否是寶藏 int tid treasure_id[nx][ny]; if (tid ! -1) { new_mask | (1 tid); } if (!vis[nx][ny][new_mask]) { vis[nx][ny][new_mask] true; q.push(State(nx, ny, new_mask, cur.step 1)); } } } cout ans endl; return 0; }注意事項狀態(tài)壓縮BFS的關(guān)鍵在于狀態(tài)的設(shè)計和表示。mask這個整數(shù)巧妙地用二進(jìn)制位記錄了集合信息。在競賽中遇到“需要記錄經(jīng)過某些特定點或收集某些物品”的最短路問題狀態(tài)壓縮DP或BFS是標(biāo)準(zhǔn)解法。另外vis數(shù)組一定要開夠維度并且用vector動態(tài)創(chuàng)建時要注意內(nèi)存本題N,M≤50K≤101K最大1024總大小約505010242.5M個bool在內(nèi)存限制內(nèi)。3.3 例題C動態(tài)規(guī)劃與優(yōu)化——“乘積最大子序列”題目描述虛擬 給定一個長度為 N 的整數(shù)序列包含正數(shù)、負(fù)數(shù)和零找出一個連續(xù)子序列至少包含一個數(shù)使得該子序列中所有數(shù)的乘積最大。輸出這個最大的乘積。由于結(jié)果可能很大要求輸出結(jié)果除以 (10^97) 的余數(shù)。注意這里的乘積是數(shù)學(xué)上的乘積不是異或。輸入第一行一個整數(shù) N (1 ≤ N ≤ 10^5)。第二行 N 個整數(shù)每個數(shù)的絕對值不超過 10^4。輸出一個整數(shù)表示最大乘積模 10^97 的結(jié)果。樣例輸入5 2 3 -2 4 -1樣例輸出48解析與實現(xiàn) 這是經(jīng)典的“乘積最大子數(shù)組”問題是“最大子序和”問題的升級版也是動態(tài)規(guī)劃的經(jīng)典例題。難點在于負(fù)數(shù)乘以負(fù)數(shù)會變成正數(shù)因此不能只維護(hù)一個最大值。1. 核心思路拆解狀態(tài)定義設(shè)dp_max[i]表示以第 i 個元素結(jié)尾的連續(xù)子序列的最大乘積。dp_min[i]表示以第 i 個元素結(jié)尾的連續(xù)子序列的最小乘積可能是負(fù)數(shù)。狀態(tài)轉(zhuǎn)移方程對于每個新來的數(shù)字nums[i]有三種選擇自己單獨成為一個子序列接在dp_max[i-1]后面接在dp_min[i-1]后面。因此dp_max[i] max(nums[i], dp_max[i-1] * nums[i], dp_min[i-1] * nums[i])dp_min[i] min(nums[i], dp_max[i-1] * nums[i], dp_min[i-1] * nums[i])最終的答案就是所有dp_max[i]中的最大值。模運算處理由于結(jié)果要對 MOD1e97 取模而轉(zhuǎn)移方程中有乘法和比較大小。不能先取模再比較因為取模后大小關(guān)系可能改變。一種方法是使用long long類型暫存中間結(jié)果在比較出最大值/最小值后再對結(jié)果取模存儲。但需要注意乘積可能溢出long long當(dāng) N 很大且數(shù)字絕對值也大時。更穩(wěn)妥的方法是使用__int128如果編譯器支持或高精度但競賽中通常數(shù)據(jù)會避免這種情況或者要求輸出取模后的值比較時用原始值。這里我們假設(shè)數(shù)據(jù)范圍下long long足夠。2. 代碼實現(xiàn)與細(xì)節(jié)#include iostream #include vector #include algorithm using namespace std; const int MOD 1e9 7; int main() { ios::sync_with_stdio(false); cin.tie(0); int N; cin N; vectorint nums(N); for (int i 0; i N; i) { cin nums[i]; } // 初始化注意用long long long long dp_max nums[0]; long long dp_min nums[0]; long long ans nums[0]; // 最終答案 for (int i 1; i N; i) { long long num nums[i]; // 由于dp_max和dp_min在下一步會被更新需要先用臨時變量保存舊值 long long temp_max dp_max; long long temp_min dp_min; // 狀態(tài)轉(zhuǎn)移 dp_max max(num, max(temp_max * num, temp_min * num)); dp_min min(num, min(temp_max * num, temp_min * num)); // 更新全局答案 if (dp_max ans) { ans dp_max; } } // 輸出答案對MOD取模的結(jié)果注意ans可能為負(fù)數(shù)需要先處理 // 但根據(jù)題意乘積最大ans應(yīng)該不會是負(fù)數(shù)除非整個序列都是負(fù)數(shù)且個數(shù)為奇數(shù)此時最大乘積也是負(fù)數(shù)。 // 題目要求輸出模MOD的結(jié)果在C中負(fù)數(shù)取模需要調(diào)整到正數(shù)范圍。 long long output ans % MOD; if (output 0) output MOD; cout output endl; return 0; }避坑技巧這道題有兩個極易出錯的地方。第一是狀態(tài)轉(zhuǎn)移時dp_max和dp_min的舊值被覆蓋必須用臨時變量保存否則計算dp_min時用的dp_max已經(jīng)是新值了。第二是取模與比較的順序。絕對不能先對temp_max * num取模再比較因為取模后數(shù)字變小可能影響最大值判斷。正確的做法是全程用long long或更大類型進(jìn)行運算和比較只在最終輸出前取模。另外當(dāng)序列中有0時這個算法也能正確處理因為max(0, ...)和min(0, ...)會自然將0納入考慮。4. 備賽策略與臨場問題排查4.1 長期備賽路線圖想要在藍(lán)橋杯國賽中取得好成績臨時抱佛腳是遠(yuǎn)遠(yuǎn)不夠的。需要一個系統(tǒng)性的、長期的訓(xùn)練計劃。第一階段鞏固基礎(chǔ)1-2個月語言熟練度確保對C標(biāo)準(zhǔn)庫STL了如指掌。重點掌握vector,string,queue,stack,set/multiset,map/multimap,priority_queue以及algorithm頭文件下的sort,lower_bound,upper_bound,next_permutation等函數(shù)。不僅要會用還要清楚其時間復(fù)雜度。基礎(chǔ)算法徹底理解并能夠手寫實現(xiàn)排序快速排序、歸并排序、二分查找、遞歸、簡單動態(tài)規(guī)劃如背包問題、深度優(yōu)先搜索DFS和廣度優(yōu)先搜索BFS。這是所有復(fù)雜算法的基石。第二階段專題突破3-4個月分專題刷題針對藍(lán)橋杯?？伎键c進(jìn)行集中訓(xùn)練。搜索DFS、BFS、回溯、剪枝。練習(xí)迷宮問題、八皇后、數(shù)獨等。動態(tài)規(guī)劃線性DP、區(qū)間DP、樹形DP、狀態(tài)壓縮DP。從經(jīng)典模型背包、LIS、LCS開始逐步過渡到復(fù)雜變形。圖論最短路Dijkstra, Floyd, SPFA、最小生成樹Kruskal, Prim、拓?fù)渑判?。?shù)論最大公約數(shù)、最小公倍數(shù)、素數(shù)篩、快速冪、模運算。數(shù)據(jù)結(jié)構(gòu)并查集、樹狀數(shù)組、線段樹。工具在洛谷、力扣、AcWing等OJ上找到相應(yīng)的專題集進(jìn)行練習(xí)。每做完一道題務(wù)必查看題解學(xué)習(xí)最優(yōu)解并總結(jié)此類題目的套路。第三階段真題模擬與綜合訓(xùn)練1-2個月限時模擬找歷年國賽、省賽真題嚴(yán)格按照比賽時間通常4小時進(jìn)行全真模擬。這能有效提升時間管理能力和抗壓能力。錯題復(fù)盤建立自己的錯題本。不僅記錄錯題還要分析錯誤原因是思路錯誤、細(xì)節(jié)疏忽如邊界條件、算法復(fù)雜度估計錯誤還是代碼實現(xiàn)bug針對性地彌補(bǔ)弱點。思維提升嘗試一題多解思考是否存在更優(yōu)的算法。多參加線上的周賽、月賽鍛煉快速解題能力。4.2 臨場常見問題與應(yīng)急方案即使在充分準(zhǔn)備后賽場上也可能遇到各種突發(fā)狀況。以下是一些常見問題及應(yīng)對策略問題現(xiàn)象可能原因排查與解決思路樣例通過提交全錯1. 邊界條件未考慮如n0,1。2. 數(shù)組開小或下標(biāo)越界。3. 初始化錯誤如全局變量未重置。4. 數(shù)據(jù)類型溢出未用long long。1. 構(gòu)造極端數(shù)據(jù)最小、最大、全零、負(fù)數(shù)測試。2. 檢查數(shù)組大小是否滿足最大數(shù)據(jù)范圍10的余量。3. 對于多組數(shù)據(jù)輸入檢查每組數(shù)據(jù)前是否重置了全局變量和容器。4. 檢查乘法、加法運算必要時全部升級為long long。部分測試點超時算法時間復(fù)雜度太高未滿足數(shù)據(jù)范圍要求。1. 重新分析題目數(shù)據(jù)范圍估算你的算法最壞復(fù)雜度。2. 思考是否存在更優(yōu)算法如O(n^2)優(yōu)化為O(n log n)。3. 檢查循環(huán)中是否存在重復(fù)計算能否用前綴和、哈希表等預(yù)處理。4. 對于搜索題剪枝是否充分部分測試點答案錯誤邏輯存在漏洞對題目理解有偏差。1. 重新仔細(xì)讀題注意“連續(xù)”與“非連續(xù)”、“恰好”與“至少”等關(guān)鍵詞。2. 用自己構(gòu)造的小數(shù)據(jù)手動模擬你的算法過程與暴力枚舉如果可能的結(jié)果對比。3. 輸出中間過程觀察在哪一步開始出現(xiàn)偏差。編譯錯誤語法錯誤或編譯器版本問題。1. 檢查頭文件、分號、括號是否匹配。2. 避免使用競賽環(huán)境可能不支持的C新特性如auto在早期版本可能不支持。3. 檢查變量名是否與關(guān)鍵字沖突。運行錯誤如段錯誤幾乎肯定是數(shù)組越界、空指針訪問、遞歸過深導(dǎo)致棧溢出。1. 檢查所有數(shù)組訪問下標(biāo)是否在[0, size-1]范圍內(nèi)。2. 檢查指針或迭代器在解引用前是否有效如vector為空時訪問front()。3. 遞歸深度過大時考慮改用迭代BFS或手動棧。最后的叮囑比賽時保持平和心態(tài)至關(guān)重要。遇到難題卡住時不妨先放一放去做其他有把握的題目。一道題如果想了20分鐘還沒有清晰思路先寫一個暴力解法保底再回頭思考優(yōu)化。合理分配時間確保會做的題目不丟分就是勝利。國賽的題目往往比拼的不僅是知識儲備更是冷靜、細(xì)致和穩(wěn)定的發(fā)揮。每一次調(diào)試每一次對邊界條件的深思都是通往獎杯的堅實臺階。