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