數(shù)篩法到動態(tài)規(guī)劃優(yōu)化)
1. 項目概述一次國賽真題的深度復(fù)盤之旅看到這個標題相信很多正在備戰(zhàn)藍橋杯尤其是目標國賽的C/C選手都會心頭一緊。“國賽C/CB組”、“未完待續(xù)”這幾個關(guān)鍵詞組合在一起立刻勾勒出一幅充滿挑戰(zhàn)與求知欲的圖景。這不僅僅是一份普通的題解更像是一位同行在激烈競賽后帶著尚未平復(fù)的心緒迫不及待地開始對頂級賽事真題進行的一次系統(tǒng)性拆解與復(fù)盤。對于所有志在攀登算法競賽高峰的開發(fā)者而言國賽真題是檢驗實力、洞察趨勢最寶貴的試金石。然而真題資源往往稀缺官方通常只提供題目而詳細的思路、踩坑記錄和優(yōu)化心法才是真正幫助后來者實現(xiàn)突破的關(guān)鍵。今天我們就以這個“未完待續(xù)”的題解為契機假設(shè)自己就是那位參賽歸來的選手對2021年第十二屆藍橋杯國賽C/C B組的真題進行一次全面的、深度的、帶有強烈個人實戰(zhàn)色彩的解析。我們的目標不是簡單地給出答案而是還原解題時的完整思考鏈條從第一眼看到題目時的直覺到多種思路的碰撞與取舍再到編碼實現(xiàn)中那些魔鬼般的細節(jié)最后是對于更高維度優(yōu)化的探討。我會分享我在模擬解題過程中“踩過的坑”、“靈光一現(xiàn)的優(yōu)化”以及“事后看來可以做得更好的地方”希望這份超過5000字的詳實記錄能成為你備賽路上的一塊堅實墊腳石。2. 整體賽題分析與解題策略總覽第十二屆國賽的題目整體上延續(xù)了藍橋杯“重思維、考基礎(chǔ)、有區(qū)分度”的特點。B組的題目相較于A組在數(shù)學(xué)模型和算法深度上要求稍低但對編程技巧、代碼效率和邊界情況的考察依然嚴苛。拿到一套題首先得有全局觀。通常前幾題是簽到或簡單題用于穩(wěn)定心態(tài)和爭取時間中間部分考察經(jīng)典算法如動態(tài)規(guī)劃、搜索、圖論的應(yīng)用與變形最后的壓軸題則往往需要比較深刻的洞察力或復(fù)雜的數(shù)據(jù)結(jié)構(gòu)/算法組合。我的策略通常是“三輪遞進法”第一輪快速通讀用10-15分鐘瀏覽所有題目對每道題的題意、數(shù)據(jù)范圍和可能考點做出初步判斷。標記出一眼就有思路的“簽到題”和需要仔細琢磨的“硬骨頭”。第二輪穩(wěn)扎穩(wěn)打從最簡單的題目開始入手確保這些分數(shù)穩(wěn)穩(wěn)拿到。在實現(xiàn)簡單題的同時大腦后臺會持續(xù)思考難題的關(guān)鍵點。第三輪攻堅克難集中精力解決剩下的中等和難題。此時要合理分配時間對于有思路但實現(xiàn)復(fù)雜的題先寫出基礎(chǔ)版本保證部分分再嘗試優(yōu)化對于完全沒思路的果斷跳過檢查前面題目的正確性。對于“未完待續(xù)”的題解我們不妨假設(shè)作者就是按照比賽節(jié)奏先解決了部分題目并進行分享。我們接下來的解析也將遵循一種合理的解題順序兼顧難度和思維連貫性。2.1 環(huán)境準備與心態(tài)調(diào)整在深入每一道題之前有兩個非技術(shù)因素至關(guān)重要環(huán)境和心態(tài)。環(huán)境國賽通常使用指定的IDE如Dev-C但日常練習(xí)我強烈建議使用自己最熟悉的工具例如Visual Studio Code GCC/Clang配合簡單的輸入輸出重定向進行測試。準備好一個本地測試腳本能快速編譯、運行并對比樣例輸出可以節(jié)省大量時間。# 一個簡單的測試腳本示例 (test.sh) g -stdc11 -O2 -o sol solution.cpp ./sol input.txt my_output.txt diff -w my_output.txt expected_output.txt心態(tài)國賽時長4小時壓力巨大。遇到卡頓比如調(diào)試半小時找不到bug時最容易慌亂。我的經(jīng)驗是設(shè)置時間盒。比如給一道題分配最多1小時包括思考、編碼和調(diào)試。如果超時仍未解決保存當(dāng)前代碼切換到另一道題或回頭檢查。往往在思考其他問題后回頭再看會有新的靈感。此外一定要仔細閱讀數(shù)據(jù)范圍這直接決定了算法的時間復(fù)雜度上限是選擇暴力還是優(yōu)化算法的根本依據(jù)。3. 真題逐題深度解析與實現(xiàn)由于是“未完待續(xù)”我們假設(shè)從部分已解題開始并補充完整后續(xù)題目的解析。以下解析包含題目大意、核心思路、代碼實現(xiàn)以及至關(guān)重要的注意事項。3.1 試題A純質(zhì)數(shù)假設(shè)題題目大意計算1到N之間其本身是質(zhì)數(shù)并且其每一位十進制數(shù)也都是質(zhì)數(shù)即每位只能是2,3,5,7的數(shù)字個數(shù)。N可能很大例如10^7。核心思路雙重判斷首先這個數(shù)必須是質(zhì)數(shù)。其次分解其每一位數(shù)字檢查是否都在集合{2,3,5,7}中。算法選擇判斷單個質(zhì)數(shù)可以用試除法時間復(fù)雜度O(√n)。判斷每一位通過不斷取模和整除10來分解數(shù)字。優(yōu)化點對于大范圍N對每個數(shù)都進行O(√n)的質(zhì)數(shù)判斷會超時。需要使用埃拉托斯特尼篩法預(yù)先篩選出所有范圍內(nèi)的質(zhì)數(shù)然后在這些質(zhì)數(shù)中檢查數(shù)位條件。數(shù)位檢查可以在篩法過程中或篩完后進行。一個關(guān)鍵的剪枝如果一個數(shù)的任何一位包含0,1,4,6,8,9它肯定不是純質(zhì)數(shù)無需進行質(zhì)數(shù)判斷。這個判斷成本極低O(位數(shù))可以提前過濾掉大量數(shù)字。代碼實現(xiàn)與注釋#include iostream #include vector #include cmath using namespace std; bool isDigitPrime(int x) { // 檢查每一位是否為2,3,5,7 while (x) { int d x % 10; if (d ! 2 d ! 3 d ! 5 d ! 7) { return false; } x / 10; } return true; } int main() { int N; cin N; vectorbool isPrime(N 1, true); isPrime[0] isPrime[1] false; // 埃氏篩法 for (int i 2; i * i N; i) { if (isPrime[i]) { for (int j i * i; j N; j i) { isPrime[j] false; } } } int ans 0; // 遍歷所有數(shù)先檢查數(shù)位再判斷質(zhì)數(shù)對于非質(zhì)數(shù)數(shù)位檢查也很快 for (int i 2; i N; i) { if (isDigitPrime(i) isPrime[i]) { ans; } } cout ans endl; return 0; }注意事項與踩坑點注意埃氏篩法的內(nèi)層循環(huán)起始點應(yīng)該是j i * i而不是j i i。從i*i開始標記是因為更小的i的倍數(shù)已經(jīng)被之前的質(zhì)數(shù)標記過了。這是寫篩法時非常容易出錯的地方。 另一個坑點1不是質(zhì)數(shù)在初始化篩法數(shù)組和遍歷計數(shù)時一定要從2開始。數(shù)位檢查函數(shù)中如果輸入是0循環(huán)會直接跳過返回true但0不在我們考慮范圍內(nèi)且篩法中isPrime[0]已被設(shè)為false所以不會影響結(jié)果但邏輯上要清晰。3.2 試題B完全日期假設(shè)題題目大意定義日期“完全”為將年月日連成一個8位數(shù)如20210101這個數(shù)的所有位數(shù)之和是一個完全平方數(shù)。給定起止日期統(tǒng)計期間有多少個“完全日期”。核心思路日期處理這是核心。需要能正確遍歷給定范圍內(nèi)的每一天并處理閏年、月份天數(shù)變化。自己實現(xiàn)日期遞增函數(shù)或使用C的chrono庫但競賽環(huán)境可能有限制。數(shù)位和計算將8位整數(shù)分解求和。完全平方數(shù)判斷計算出的數(shù)位和sum判斷是否存在整數(shù)t使得t*t sum。可以預(yù)處理一個布爾數(shù)組標記1到100因為8位數(shù)最大和是8*972以內(nèi)的完全平方數(shù)。代碼實現(xiàn)與注釋#include iostream using namespace std; // 預(yù)處理完全平方數(shù)表 bool isPerfectSquare[100] {false}; // 下標即數(shù)字值為是否為完全平方數(shù) // 判斷閏年 bool isLeapYear(int y) { return (y % 4 0 y % 100 ! 0) || (y % 400 0); } // 獲取某年某月的天數(shù) int daysOfMonth(int y, int m) { if (m 2) { return isLeapYear(y) ? 29 : 28; } if (m 4 || m 6 || m 9 || m 11) { return 30; } return 31; } // 計算數(shù)位和 int digitSum(int num) { int sum 0; while (num) { sum num % 10; num / 10; } return sum; } int main() { // 初始化平方數(shù)表 for (int i 1; i * i 100; i) { isPerfectSquare[i * i] true; } int y1, m1, d1, y2, m2, d2; // 假設(shè)輸入格式為 y1 m1 d1 y2 m2 d2 // 這里為了演示直接賦值一個范圍 y1 2001, m1 1, d1 1; y2 2021, m2 12, d2 31; int ans 0; int y y1, m m1, d d1; // 循環(huán)遍歷每一天直到超過結(jié)束日期 while (!(y y2 || (y y2 m m2) || (y y2 m m2 d d2))) { int dateNum y * 10000 m * 100 d; // 組成8位數(shù) int sum digitSum(dateNum); if (isPerfectSquare[sum]) { ans; } // 日期遞增 d; if (d daysOfMonth(y, m)) { d 1; m; if (m 12) { m 1; y; } } } cout ans endl; return 0; }注意事項與踩坑點日期遍歷的邊界條件是極易出錯的地方。循環(huán)條件while (!(y y2 ...))確保了在日期嚴格大于終止日期時停止。也可以寫成while (y y2 || (y y2 m m2) || (y y2 m m2 d d2))但要注意d d2。閏年判斷規(guī)則必須記牢能被4整除但不能被100整除或者能被400整除。2月的天數(shù)處理依賴于這個函數(shù)。性能直接遍歷每一天在日期跨度大時比如百年也是可行的因為總天數(shù)大約在3萬左右計算量很小。重點在于日期遞增邏輯的正確性。3.3 試題C最小權(quán)值動態(tài)規(guī)劃典型題題目大意對一棵有N個節(jié)點的二叉樹定義其權(quán)值為所有節(jié)點的“權(quán)值”之和。每個節(jié)點的“權(quán)值”定義為以其為根的子樹中所有節(jié)點到它的距離之和。現(xiàn)在給定N求所有可能結(jié)構(gòu)的二叉樹的最小權(quán)值。核心思路解析 這道題是動態(tài)規(guī)劃的經(jīng)典應(yīng)用需要一定的抽象和建模能力。理解題意所謂“所有可能結(jié)構(gòu)的二叉樹”是指所有不同形態(tài)的二叉樹考慮左右子樹形態(tài)。我們需要找出所有形態(tài)中權(quán)值最小的那個。問題轉(zhuǎn)化假設(shè)我們定義dp[i]為有i個節(jié)點時所能得到的最小權(quán)值。考慮如何從子問題推導(dǎo)。狀態(tài)轉(zhuǎn)移對于一棵有i個節(jié)點的樹我們可以將根節(jié)點拿出來剩下的i-1個節(jié)點分配給左子樹和右子樹。設(shè)左子樹有j個節(jié)點則右子樹有i-1-j個節(jié)點j從0到i-1。根節(jié)點本身的貢獻左子樹所有j個節(jié)點到根的距離為1右子樹所有i-1-j個節(jié)點到根的距離也為1。所以根節(jié)點帶來的權(quán)值增加為j (i-1-j) i-1。左右子樹的貢獻左子樹本身的權(quán)值是dp[j]但注意左子樹中每個節(jié)點到根的距離等于它到左子樹根的距離再加1。因此左子樹的所有節(jié)點對總權(quán)值的貢獻除了自身的dp[j]還要加上j * 1因為每個節(jié)點到新根的距離都增加了1。右子樹同理。轉(zhuǎn)移方程dp[i] min_{j0}^{i-1} { (i-1) dp[j] j dp[i-1-j] (i-1-j) }簡化后dp[i] min_{j0}^{i-1} { dp[j] dp[i-1-j] i - 1 }這里i-1是根節(jié)點的直接貢獻dp[j] j是左子樹的總貢獻自身權(quán)值距離增量dp[i-1-j] (i-1-j)是右子樹的總貢獻。 進一步觀察dp[j] j可以看作是一個新的狀態(tài)f[j]。但直接按上式計算即可。初始化dp[0] 0空樹權(quán)值為0。dp[1] 0只有一個節(jié)點距離和為0。代碼實現(xiàn)與注釋#include iostream #include vector #include climits using namespace std; int main() { int N; cin N; vectorlong long dp(N 1, LLONG_MAX); // 權(quán)值可能很大用long long dp[0] 0; dp[1] 0; // 初始化 for (int i 2; i N; i) { for (int j 0; j i; j) { // j為左子樹節(jié)點數(shù) int left j; int right i - 1 - j; // 計算當(dāng)前分配方案下的權(quán)值 long long cur dp[left] dp[right] i - 1; // 注意dp[left]已經(jīng)包含了左子樹內(nèi)部的距離和 // 加上 (i-1) 是根節(jié)點帶來的貢獻所有子節(jié)點到根距離為1。 // 為什么不是加上 left right因為 left right i-1。 // 更嚴謹?shù)耐茖?dǎo)總權(quán)值 根貢獻(i-1) 左子樹貢獻(dp[left] left) 右子樹貢獻(dp[right] right) // dp[left] dp[right] (i-1) left right dp[left] dp[right] 2*(i-1)這里需要仔細核對。 // 讓我們重新推導(dǎo)這是最容易出錯的地方 } } cout dp[N] endl; return 0; }停下來這里發(fā)現(xiàn)了問題。上面的推導(dǎo)和注釋出現(xiàn)了矛盾。這說明在壓力下動態(tài)規(guī)劃的狀態(tài)定義和轉(zhuǎn)移方程極易搞混。我們必須靜下心來重新嚴謹推導(dǎo)。重新推導(dǎo)動態(tài)規(guī)劃狀態(tài) 定義dp[i]為有 i 個節(jié)點的二叉樹其最小權(quán)值是多少。注意這個權(quán)值定義是樹中所有節(jié)點到其子樹根節(jié)點的距離之和。但題目定義是每個節(jié)點的權(quán)值是其子樹中所有節(jié)點到它的距離之和然后對所有節(jié)點求和。對于整棵樹而言如果我們選定了樹根那么總權(quán)值就是根節(jié)點的權(quán)值 左子樹的總權(quán)值 右子樹的總權(quán)值。然而左子樹的總權(quán)值在左子樹自己的坐標系下是dp[left]但放在整棵樹下左子樹每個節(jié)點到整棵樹根的距離等于它到左子樹根的距離再加1。所以左子樹對總權(quán)值的貢獻是dp[left] left因為 left 個節(jié)點每個距離1。右子樹同理。因此正確的轉(zhuǎn)移方程應(yīng)該是dp[i] min_{j0}^{i-1} { (i-1) (dp[j] j) (dp[i-1-j] (i-1-j)) }化簡dp[i] min_{j0}^{i-1} { dp[j] dp[i-1-j] i - 1 j (i-1-j) } min_{j0}^{i-1} { dp[j] dp[i-1-j] 2*(i-1) } min_{j0}^{i-1} { dp[j] dp[i-1-j] } 2*(i-1)修正后的代碼#include iostream #include vector #include climits using namespace std; int main() { int N; cin N; vectorlong long dp(N 1, LLONG_MAX); dp[0] 0; // 空樹 dp[1] 0; // 只有一個節(jié)點 for (int i 2; i N; i) { long long minVal LLONG_MAX; for (int j 0; j i; j) { // j 左子樹節(jié)點數(shù) int left j; int right i - 1 - j; // 左右子樹節(jié)點數(shù)必須合法非負 if (left 0 right 0) { long long cur dp[left] dp[right]; if (cur minVal) { minVal cur; } } } dp[i] minVal 2LL * (i - 1); // 加上根節(jié)點帶來的固定增量 } cout dp[N] endl; return 0; }注意事項與踩坑點這是本題最核心的陷阱。動態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移方程必須經(jīng)過嚴格驗證最好用小的例子如N2,3手動計算看是否符合程序輸出。我第一版的錯誤推導(dǎo)就是一個活生生的教訓(xùn)。 數(shù)據(jù)范圍N可能較大比如2000dp值增長很快必須使用long long。 時間復(fù)雜度O(N^2)對于N2000是可行的400萬次操作。3.4 試題D大寫字符串處理基礎(chǔ)題題目大意給定一個只包含大小寫字母的字符串將其中的小寫字母轉(zhuǎn)換成大寫字母。核心思路這題是絕對的簽到題考察基本的字符處理。兩種方法使用Ctoupper函數(shù)。利用ASCII碼小寫字母a到z對應(yīng)97-122大寫字母A到Z對應(yīng)65-90。小寫轉(zhuǎn)大寫只需c - a A或c - 32。代碼實現(xiàn)與注釋#include iostream #include string #include cctype using namespace std; int main() { string s; cin s; // 或 getline(cin, s) 如果包含空格 for (char c : s) { // 使用引用直接修改原字符串 c toupper(c); // 方法一庫函數(shù) // 方法二if (c a c z) c c - a A; } cout s endl; return 0; }注意事項與踩坑點雖然簡單但要注意輸入字符串是否可能包含空格。如果題目說明是“一行字符串”則可能需要使用getline(cin, s)。仔細看題 使用范圍循環(huán)for (char c : s)時記得加引用否則修改的是副本。3.5 試題E123前綴和與數(shù)學(xué)規(guī)律題題目大意有一個無限長的序列1, 1,2, 1,2,3, 1,2,3,4, ...。即先放1再放1,2再放1,2,3以此類推。多次詢問每次詢問區(qū)間[L, R]內(nèi)所有數(shù)的和。核心思路解析問題規(guī)模L和R可以非常大比如10^12不可能直接模擬生成序列。尋找規(guī)律序列是分塊的。第i塊包含數(shù)字1到i。第1塊長度1數(shù)字和1。第2塊長度2數(shù)字和123。第3塊長度3數(shù)字和1236。第i塊長度i數(shù)字和i*(i1)/2。定位與求和給定一個位置pos需要知道它在第幾塊以及在該塊內(nèi)的第幾個位置。如何找到pos所在的塊號k滿足條件12... (k-1) pos 12...k。即k*(k-1)/2 pos k*(k1)/2。可以通過解不等式或二分查找得到k。知道塊號k后該塊起始位置的前綴和是S(k-1) sum_{i1}^{k-1} (i*(i1)/2)。這個公式可以簡化sum i*(i1)/2 1/2 * (sum i^2 sum i) 1/2 * (n(n1)(2n1)/6 n(n1)/2) n(n1)(n2)/6。所以前m塊的總數(shù)字和不是位置和是F(m) m*(m1)*(m2)/6。對于位置pos假設(shè)它在第k塊中的偏移量為offset (offset pos - k*(k-1)/2)。那么從第1塊到pos位置的總和可以分兩部分計算前k-1塊的總和F(k-1)。第k塊中前offset個數(shù)的和12...offset offset*(offset1)/2。因此區(qū)間[L,R]的和等于sumToPos(R) - sumToPos(L-1)。代碼實現(xiàn)與注釋#include iostream #include cmath using namespace std; using ll long long; // 計算前x塊的總數(shù)字和 ll sumOfBlocks(ll x) { return x * (x 1) * (x 2) / 6; } // 計算從序列開始到位置pos的總和 ll sumToPos(ll pos) { if (pos 0) return 0; // 二分查找pos所在的塊號k ll l 1, r 2e6; // 估算一個上界因為k*(k1)/2 pos, k約等于sqrt(2*pos) while (l r) { ll mid (l r) / 2; if (mid * (mid 1) / 2 pos) { r mid; } else { l mid 1; } } ll k l; // pos所在的塊號 // 前k-1塊的總和 ll res sumOfBlocks(k - 1); // 在第k塊中的偏移量從1開始 ll offset pos - (k - 1) * k / 2; // 加上第k塊內(nèi)前offset個數(shù)的和 res offset * (offset 1) / 2; return res; } int main() { int T; cin T; while (T--) { ll L, R; cin L R; cout sumToPos(R) - sumToPos(L - 1) endl; } return 0; }注意事項與踩坑點二分查找的邊界塊號k的上界需要合理估計。因為k*(k1)/2 ≈ pos所以k ≈ sqrt(2*pos)。對于pos最大為10^12sqrt(2e12) ≈ 1.4e6所以上界設(shè)為2e6是安全的。數(shù)據(jù)溢出計算過程中涉及多個大數(shù)相乘如k*(k1)*(k2)即使k2e6結(jié)果也遠超32位int范圍。必須全程使用long long。公式推導(dǎo)的正確性sumOfBlocks的公式m*(m1)*(m2)/6需要自己動手推導(dǎo)驗證死記硬背容易出錯。可以寫個小程序驗證前幾項。位置與偏移量的計算(k-1)*k/2是前k-1塊的總長度也是第k塊開始的位置。offset的計算要小心確保是從1開始計數(shù)。4. 常見問題與調(diào)試技巧實錄在競賽或練習(xí)中除了算法思路調(diào)試能力同樣決定成敗。以下是我在解決這類題目時積累的一些常見問題排查技巧。4.1 答案錯誤Wrong Answer的排查流程重讀題目確保完全理解題意特別是輸入輸出格式、數(shù)據(jù)范圍、邊界條件如LRN0。這是最常見的問題源。測試樣例自己構(gòu)造一些小的、邊界性的測試用例。對于日期題測試閏年2月29日、跨年、同一天等。對于DP題測試N0,1,2,3。中間輸出調(diào)試在代碼關(guān)鍵位置如循環(huán)內(nèi)、狀態(tài)轉(zhuǎn)移后打印中間變量與手算結(jié)果對比。例如在動態(tài)規(guī)劃題中打印出dp數(shù)組的前幾項。對拍寫一個暴力但正確的程序通常只適用于小數(shù)據(jù)范圍用隨機生成的數(shù)據(jù)同時運行你的優(yōu)化程序和暴力程序比較輸出。這是找出邏輯錯誤的大殺器。關(guān)注溢出對于涉及大量加法、乘法的題目如“123”int溢出是隱形殺手。養(yǎng)成習(xí)慣看到10^5以上的數(shù)據(jù)范圍直接使用long long。4.2 時間超限Time Limit Exceeded的優(yōu)化思路復(fù)雜度分析首先分析你的算法理論時間復(fù)雜度。O(N^2)對于N10^5肯定超時。國賽B組O(NlogN)或O(N)通常是安全的。減少常數(shù)檢查循環(huán)內(nèi)部是否有不必要的函數(shù)調(diào)用如pow,sqrt、是否能用前綴和/差分避免重復(fù)計算、是否能用數(shù)組代替vector以提升訪問速度在C中差異不大但在極端情況下有影響。I/O優(yōu)化當(dāng)輸入數(shù)據(jù)量巨大時如10^6個數(shù)使用cin/cout可能成為瓶頸。可以ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);或者使用scanf/printf。避免遞歸過深DFS等遞歸算法在數(shù)據(jù)量大時可能棧溢出或超時考慮迭代寫法或顯式棧。4.3 內(nèi)存超限Memory Limit Exceeded的檢查點檢查數(shù)據(jù)結(jié)構(gòu)大小你申請的數(shù)組大小是否與題目要求匹配int dp[1000000]大約占用4MBlong long則翻倍。估算一下總內(nèi)存消耗。不必要的緩存是否存儲了所有中間結(jié)果有時可以滾動數(shù)組只保留最近幾層狀態(tài)。遞歸開銷深度遞歸不僅慢而且每個函數(shù)調(diào)用都會占用棧空間。4.4 藍橋杯國賽特有的注意事項結(jié)果填空題有些題目是填空題只要求提交最終結(jié)果。對于這類題可以寫程序暴力計算但一定要確保答案唯一且正確。計算出來后最好用不同的思路或程序驗證。編程題仔細閱讀輸入輸出描述。藍橋杯有時要求輸出特定格式比如“Case #1: ”前綴或者結(jié)果對某個數(shù)取模。環(huán)境差異本地環(huán)境如Mac的Clang和比賽環(huán)境通常Windows的GCC可能有細微差別比如rand()函數(shù)、to_string的支持度。避免使用非標準特性。長整型使用國賽題目經(jīng)常涉及大數(shù)long long是你的好朋友。定義別名using ll long long;是個好習(xí)慣。5. 備賽策略與資源推薦國賽的備戰(zhàn)是一個系統(tǒng)工程不能只靠刷題。5.1 系統(tǒng)性知識梳理你需要一個清晰的知識圖譜基礎(chǔ)語法與STL熟練使用C11/14掌握vector,map,set,queue,stack,string等容器及其方法。基礎(chǔ)算法排序、二分查找、前綴和、差分、雙指針。搜索DFS、BFS、回溯、剪枝。動態(tài)規(guī)劃線性DP、背包DP、區(qū)間DP、樹形DP、狀態(tài)壓縮DP。掌握經(jīng)典模型和狀態(tài)設(shè)計方法。圖論最短路Dijkstra, Floyd, SPFA、最小生成樹Kruskal, Prim、拓撲排序、并查集。數(shù)學(xué)質(zhì)數(shù)篩法、快速冪、最大公約數(shù)/最小公倍數(shù)、簡單組合數(shù)學(xué)。數(shù)據(jù)結(jié)構(gòu)單調(diào)棧、單調(diào)隊列、并查集、樹狀數(shù)組、線段樹提高組。5.2 有效的練習(xí)方法專題突破針對自己的弱點進行集中訓(xùn)練。例如花一周時間專門練習(xí)動態(tài)規(guī)劃從簡單題到難題。模擬賽定期進行4小時的全程模擬使用歷年真題或高質(zhì)量模擬題。嚴格計時模擬真實比賽環(huán)境包括不能上網(wǎng)查資料。復(fù)盤總結(jié)每做完一套題或一次模擬賽無論結(jié)果如何必須復(fù)盤。寫出詳細的題解記錄自己的思考過程、錯誤原因、優(yōu)化方法。本篇“未完待續(xù)”的題解就是極好的復(fù)盤形式。構(gòu)建代碼模板將常用的、易錯的算法如快速冪、Dijkstra、并查集寫成簡潔、正確的模板并熟記于心。5.3 資源推薦官方題庫藍橋杯官網(wǎng)的練習(xí)系統(tǒng)是最直接的資源。在線判題平臺洛谷、AcWing、Codeforces、LeetCode側(cè)重算法思維都有豐富的題庫和社區(qū)討論。書籍《算法競賽入門經(jīng)典》劉汝佳、《算法競賽進階指南》李煜東是經(jīng)典教材。社區(qū)與博客多看看其他優(yōu)秀選手的博客和題解學(xué)習(xí)不同的思路和編碼技巧。國賽的挑戰(zhàn)性正在于它綜合考察了你的知識廣度、思維深度、編碼速度和心理素質(zhì)。這份針對2021年國賽B組的“未完待續(xù)”式深度解析希望能幫你捋清一類題目的解題脈絡(luò)更重要的是傳遞一種“復(fù)盤”和“深究”的態(tài)度。每一道錯題、每一個卡住的點都是進步的階梯。當(dāng)你能夠獨立完成這樣一篇詳盡的題解時你的實力必然已經(jīng)更上一層樓了。 藍橋杯國賽C/C++ B組真題深度解析：從質(zhì)數(shù)篩法到動態(tài)規(guī)劃優(yōu)化
1. 項目概述一次國賽真題的深度復(fù)盤之旅看到這個標題相信很多正在備戰(zhàn)藍橋杯尤其是目標國賽的C/C選手都會心頭一緊。“國賽C/CB組”、“未完待續(xù)”這幾個關(guān)鍵詞組合在一起立刻勾勒出一幅充滿挑戰(zhàn)與求知欲的圖景。這不僅僅是一份普通的題解更像是一位同行在激烈競賽后帶著尚未平復(fù)的心緒迫不及待地開始對頂級賽事真題進行的一次系統(tǒng)性拆解與復(fù)盤。對于所有志在攀登算法競賽高峰的開發(fā)者而言國賽真題是檢驗實力、洞察趨勢最寶貴的試金石。然而真題資源往往稀缺官方通常只提供題目而詳細的思路、踩坑記錄和優(yōu)化心法才是真正幫助后來者實現(xiàn)突破的關(guān)鍵。今天我們就以這個“未完待續(xù)”的題解為契機假設(shè)自己就是那位參賽歸來的選手對2021年第十二屆藍橋杯國賽C/C B組的真題進行一次全面的、深度的、帶有強烈個人實戰(zhàn)色彩的解析。我們的目標不是簡單地給出答案而是還原解題時的完整思考鏈條從第一眼看到題目時的直覺到多種思路的碰撞與取舍再到編碼實現(xiàn)中那些魔鬼般的細節(jié)最后是對于更高維度優(yōu)化的探討。我會分享我在模擬解題過程中“踩過的坑”、“靈光一現(xiàn)的優(yōu)化”以及“事后看來可以做得更好的地方”希望這份超過5000字的詳實記錄能成為你備賽路上的一塊堅實墊腳石。2. 整體賽題分析與解題策略總覽第十二屆國賽的題目整體上延續(xù)了藍橋杯“重思維、考基礎(chǔ)、有區(qū)分度”的特點。B組的題目相較于A組在數(shù)學(xué)模型和算法深度上要求稍低但對編程技巧、代碼效率和邊界情況的考察依然嚴苛。拿到一套題首先得有全局觀。通常前幾題是簽到或簡單題用于穩(wěn)定心態(tài)和爭取時間中間部分考察經(jīng)典算法如動態(tài)規(guī)劃、搜索、圖論的應(yīng)用與變形最后的壓軸題則往往需要比較深刻的洞察力或復(fù)雜的數(shù)據(jù)結(jié)構(gòu)/算法組合。我的策略通常是“三輪遞進法”第一輪快速通讀用10-15分鐘瀏覽所有題目對每道題的題意、數(shù)據(jù)范圍和可能考點做出初步判斷。標記出一眼就有思路的“簽到題”和需要仔細琢磨的“硬骨頭”。第二輪穩(wěn)扎穩(wěn)打從最簡單的題目開始入手確保這些分數(shù)穩(wěn)穩(wěn)拿到。在實現(xiàn)簡單題的同時大腦后臺會持續(xù)思考難題的關(guān)鍵點。第三輪攻堅克難集中精力解決剩下的中等和難題。此時要合理分配時間對于有思路但實現(xiàn)復(fù)雜的題先寫出基礎(chǔ)版本保證部分分再嘗試優(yōu)化對于完全沒思路的果斷跳過檢查前面題目的正確性。對于“未完待續(xù)”的題解我們不妨假設(shè)作者就是按照比賽節(jié)奏先解決了部分題目并進行分享。我們接下來的解析也將遵循一種合理的解題順序兼顧難度和思維連貫性。2.1 環(huán)境準備與心態(tài)調(diào)整在深入每一道題之前有兩個非技術(shù)因素至關(guān)重要環(huán)境和心態(tài)。環(huán)境國賽通常使用指定的IDE如Dev-C但日常練習(xí)我強烈建議使用自己最熟悉的工具例如Visual Studio Code GCC/Clang配合簡單的輸入輸出重定向進行測試。準備好一個本地測試腳本能快速編譯、運行并對比樣例輸出可以節(jié)省大量時間。# 一個簡單的測試腳本示例 (test.sh) g -stdc11 -O2 -o sol solution.cpp ./sol input.txt my_output.txt diff -w my_output.txt expected_output.txt心態(tài)國賽時長4小時壓力巨大。遇到卡頓比如調(diào)試半小時找不到bug時最容易慌亂。我的經(jīng)驗是設(shè)置時間盒。比如給一道題分配最多1小時包括思考、編碼和調(diào)試。如果超時仍未解決保存當(dāng)前代碼切換到另一道題或回頭檢查。往往在思考其他問題后回頭再看會有新的靈感。此外一定要仔細閱讀數(shù)據(jù)范圍這直接決定了算法的時間復(fù)雜度上限是選擇暴力還是優(yōu)化算法的根本依據(jù)。3. 真題逐題深度解析與實現(xiàn)由于是“未完待續(xù)”我們假設(shè)從部分已解題開始并補充完整后續(xù)題目的解析。以下解析包含題目大意、核心思路、代碼實現(xiàn)以及至關(guān)重要的注意事項。3.1 試題A純質(zhì)數(shù)假設(shè)題題目大意計算1到N之間其本身是質(zhì)數(shù)并且其每一位十進制數(shù)也都是質(zhì)數(shù)即每位只能是2,3,5,7的數(shù)字個數(shù)。N可能很大例如10^7。核心思路雙重判斷首先這個數(shù)必須是質(zhì)數(shù)。其次分解其每一位數(shù)字檢查是否都在集合{2,3,5,7}中。算法選擇判斷單個質(zhì)數(shù)可以用試除法時間復(fù)雜度O(√n)。判斷每一位通過不斷取模和整除10來分解數(shù)字。優(yōu)化點對于大范圍N對每個數(shù)都進行O(√n)的質(zhì)數(shù)判斷會超時。需要使用埃拉托斯特尼篩法預(yù)先篩選出所有范圍內(nèi)的質(zhì)數(shù)然后在這些質(zhì)數(shù)中檢查數(shù)位條件。數(shù)位檢查可以在篩法過程中或篩完后進行。一個關(guān)鍵的剪枝如果一個數(shù)的任何一位包含0,1,4,6,8,9它肯定不是純質(zhì)數(shù)無需進行質(zhì)數(shù)判斷。這個判斷成本極低O(位數(shù))可以提前過濾掉大量數(shù)字。代碼實現(xiàn)與注釋#include iostream #include vector #include cmath using namespace std; bool isDigitPrime(int x) { // 檢查每一位是否為2,3,5,7 while (x) { int d x % 10; if (d ! 2 d ! 3 d ! 5 d ! 7) { return false; } x / 10; } return true; } int main() { int N; cin N; vectorbool isPrime(N 1, true); isPrime[0] isPrime[1] false; // 埃氏篩法 for (int i 2; i * i N; i) { if (isPrime[i]) { for (int j i * i; j N; j i) { isPrime[j] false; } } } int ans 0; // 遍歷所有數(shù)先檢查數(shù)位再判斷質(zhì)數(shù)對于非質(zhì)數(shù)數(shù)位檢查也很快 for (int i 2; i N; i) { if (isDigitPrime(i) isPrime[i]) { ans; } } cout ans endl; return 0; }注意事項與踩坑點注意埃氏篩法的內(nèi)層循環(huán)起始點應(yīng)該是j i * i而不是j i i。從i*i開始標記是因為更小的i的倍數(shù)已經(jīng)被之前的質(zhì)數(shù)標記過了。這是寫篩法時非常容易出錯的地方。 另一個坑點1不是質(zhì)數(shù)在初始化篩法數(shù)組和遍歷計數(shù)時一定要從2開始。數(shù)位檢查函數(shù)中如果輸入是0循環(huán)會直接跳過返回true但0不在我們考慮范圍內(nèi)且篩法中isPrime[0]已被設(shè)為false所以不會影響結(jié)果但邏輯上要清晰。3.2 試題B完全日期假設(shè)題題目大意定義日期“完全”為將年月日連成一個8位數(shù)如20210101這個數(shù)的所有位數(shù)之和是一個完全平方數(shù)。給定起止日期統(tǒng)計期間有多少個“完全日期”。核心思路日期處理這是核心。需要能正確遍歷給定范圍內(nèi)的每一天并處理閏年、月份天數(shù)變化。自己實現(xiàn)日期遞增函數(shù)或使用C的chrono庫但競賽環(huán)境可能有限制。數(shù)位和計算將8位整數(shù)分解求和。完全平方數(shù)判斷計算出的數(shù)位和sum判斷是否存在整數(shù)t使得t*t sum。可以預(yù)處理一個布爾數(shù)組標記1到100因為8位數(shù)最大和是8*972以內(nèi)的完全平方數(shù)。代碼實現(xiàn)與注釋#include iostream using namespace std; // 預(yù)處理完全平方數(shù)表 bool isPerfectSquare[100] {false}; // 下標即數(shù)字值為是否為完全平方數(shù) // 判斷閏年 bool isLeapYear(int y) { return (y % 4 0 y % 100 ! 0) || (y % 400 0); } // 獲取某年某月的天數(shù) int daysOfMonth(int y, int m) { if (m 2) { return isLeapYear(y) ? 29 : 28; } if (m 4 || m 6 || m 9 || m 11) { return 30; } return 31; } // 計算數(shù)位和 int digitSum(int num) { int sum 0; while (num) { sum num % 10; num / 10; } return sum; } int main() { // 初始化平方數(shù)表 for (int i 1; i * i 100; i) { isPerfectSquare[i * i] true; } int y1, m1, d1, y2, m2, d2; // 假設(shè)輸入格式為 y1 m1 d1 y2 m2 d2 // 這里為了演示直接賦值一個范圍 y1 2001, m1 1, d1 1; y2 2021, m2 12, d2 31; int ans 0; int y y1, m m1, d d1; // 循環(huán)遍歷每一天直到超過結(jié)束日期 while (!(y y2 || (y y2 m m2) || (y y2 m m2 d d2))) { int dateNum y * 10000 m * 100 d; // 組成8位數(shù) int sum digitSum(dateNum); if (isPerfectSquare[sum]) { ans; } // 日期遞增 d; if (d daysOfMonth(y, m)) { d 1; m; if (m 12) { m 1; y; } } } cout ans endl; return 0; }注意事項與踩坑點日期遍歷的邊界條件是極易出錯的地方。循環(huán)條件while (!(y y2 ...))確保了在日期嚴格大于終止日期時停止。也可以寫成while (y y2 || (y y2 m m2) || (y y2 m m2 d d2))但要注意d d2。閏年判斷規(guī)則必須記牢能被4整除但不能被100整除或者能被400整除。2月的天數(shù)處理依賴于這個函數(shù)。性能直接遍歷每一天在日期跨度大時比如百年也是可行的因為總天數(shù)大約在3萬左右計算量很小。重點在于日期遞增邏輯的正確性。3.3 試題C最小權(quán)值動態(tài)規(guī)劃典型題題目大意對一棵有N個節(jié)點的二叉樹定義其權(quán)值為所有節(jié)點的“權(quán)值”之和。每個節(jié)點的“權(quán)值”定義為以其為根的子樹中所有節(jié)點到它的距離之和。現(xiàn)在給定N求所有可能結(jié)構(gòu)的二叉樹的最小權(quán)值。核心思路解析 這道題是動態(tài)規(guī)劃的經(jīng)典應(yīng)用需要一定的抽象和建模能力。理解題意所謂“所有可能結(jié)構(gòu)的二叉樹”是指所有不同形態(tài)的二叉樹考慮左右子樹形態(tài)。我們需要找出所有形態(tài)中權(quán)值最小的那個。問題轉(zhuǎn)化假設(shè)我們定義dp[i]為有i個節(jié)點時所能得到的最小權(quán)值。考慮如何從子問題推導(dǎo)。狀態(tài)轉(zhuǎn)移對于一棵有i個節(jié)點的樹我們可以將根節(jié)點拿出來剩下的i-1個節(jié)點分配給左子樹和右子樹。設(shè)左子樹有j個節(jié)點則右子樹有i-1-j個節(jié)點j從0到i-1。根節(jié)點本身的貢獻左子樹所有j個節(jié)點到根的距離為1右子樹所有i-1-j個節(jié)點到根的距離也為1。所以根節(jié)點帶來的權(quán)值增加為j (i-1-j) i-1。左右子樹的貢獻左子樹本身的權(quán)值是dp[j]但注意左子樹中每個節(jié)點到根的距離等于它到左子樹根的距離再加1。因此左子樹的所有節(jié)點對總權(quán)值的貢獻除了自身的dp[j]還要加上j * 1因為每個節(jié)點到新根的距離都增加了1。右子樹同理。轉(zhuǎn)移方程dp[i] min_{j0}^{i-1} { (i-1) dp[j] j dp[i-1-j] (i-1-j) }簡化后dp[i] min_{j0}^{i-1} { dp[j] dp[i-1-j] i - 1 }這里i-1是根節(jié)點的直接貢獻dp[j] j是左子樹的總貢獻自身權(quán)值距離增量dp[i-1-j] (i-1-j)是右子樹的總貢獻。 進一步觀察dp[j] j可以看作是一個新的狀態(tài)f[j]。但直接按上式計算即可。初始化dp[0] 0空樹權(quán)值為0。dp[1] 0只有一個節(jié)點距離和為0。代碼實現(xiàn)與注釋#include iostream #include vector #include climits using namespace std; int main() { int N; cin N; vectorlong long dp(N 1, LLONG_MAX); // 權(quán)值可能很大用long long dp[0] 0; dp[1] 0; // 初始化 for (int i 2; i N; i) { for (int j 0; j i; j) { // j為左子樹節(jié)點數(shù) int left j; int right i - 1 - j; // 計算當(dāng)前分配方案下的權(quán)值 long long cur dp[left] dp[right] i - 1; // 注意dp[left]已經(jīng)包含了左子樹內(nèi)部的距離和 // 加上 (i-1) 是根節(jié)點帶來的貢獻所有子節(jié)點到根距離為1。 // 為什么不是加上 left right因為 left right i-1。 // 更嚴謹?shù)耐茖?dǎo)總權(quán)值 根貢獻(i-1) 左子樹貢獻(dp[left] left) 右子樹貢獻(dp[right] right) // dp[left] dp[right] (i-1) left right dp[left] dp[right] 2*(i-1)這里需要仔細核對。 // 讓我們重新推導(dǎo)這是最容易出錯的地方 } } cout dp[N] endl; return 0; }停下來這里發(fā)現(xiàn)了問題。上面的推導(dǎo)和注釋出現(xiàn)了矛盾。這說明在壓力下動態(tài)規(guī)劃的狀態(tài)定義和轉(zhuǎn)移方程極易搞混。我們必須靜下心來重新嚴謹推導(dǎo)。重新推導(dǎo)動態(tài)規(guī)劃狀態(tài) 定義dp[i]為有 i 個節(jié)點的二叉樹其最小權(quán)值是多少。注意這個權(quán)值定義是樹中所有節(jié)點到其子樹根節(jié)點的距離之和。但題目定義是每個節(jié)點的權(quán)值是其子樹中所有節(jié)點到它的距離之和然后對所有節(jié)點求和。對于整棵樹而言如果我們選定了樹根那么總權(quán)值就是根節(jié)點的權(quán)值 左子樹的總權(quán)值 右子樹的總權(quán)值。然而左子樹的總權(quán)值在左子樹自己的坐標系下是dp[left]但放在整棵樹下左子樹每個節(jié)點到整棵樹根的距離等于它到左子樹根的距離再加1。所以左子樹對總權(quán)值的貢獻是dp[left] left因為 left 個節(jié)點每個距離1。右子樹同理。因此正確的轉(zhuǎn)移方程應(yīng)該是dp[i] min_{j0}^{i-1} { (i-1) (dp[j] j) (dp[i-1-j] (i-1-j)) }化簡dp[i] min_{j0}^{i-1} { dp[j] dp[i-1-j] i - 1 j (i-1-j) } min_{j0}^{i-1} { dp[j] dp[i-1-j] 2*(i-1) } min_{j0}^{i-1} { dp[j] dp[i-1-j] } 2*(i-1)修正后的代碼#include iostream #include vector #include climits using namespace std; int main() { int N; cin N; vectorlong long dp(N 1, LLONG_MAX); dp[0] 0; // 空樹 dp[1] 0; // 只有一個節(jié)點 for (int i 2; i N; i) { long long minVal LLONG_MAX; for (int j 0; j i; j) { // j 左子樹節(jié)點數(shù) int left j; int right i - 1 - j; // 左右子樹節(jié)點數(shù)必須合法非負 if (left 0 right 0) { long long cur dp[left] dp[right]; if (cur minVal) { minVal cur; } } } dp[i] minVal 2LL * (i - 1); // 加上根節(jié)點帶來的固定增量 } cout dp[N] endl; return 0; }注意事項與踩坑點這是本題最核心的陷阱。動態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移方程必須經(jīng)過嚴格驗證最好用小的例子如N2,3手動計算看是否符合程序輸出。我第一版的錯誤推導(dǎo)就是一個活生生的教訓(xùn)。 數(shù)據(jù)范圍N可能較大比如2000dp值增長很快必須使用long long。 時間復(fù)雜度O(N^2)對于N2000是可行的400萬次操作。3.4 試題D大寫字符串處理基礎(chǔ)題題目大意給定一個只包含大小寫字母的字符串將其中的小寫字母轉(zhuǎn)換成大寫字母。核心思路這題是絕對的簽到題考察基本的字符處理。兩種方法使用Ctoupper函數(shù)。利用ASCII碼小寫字母a到z對應(yīng)97-122大寫字母A到Z對應(yīng)65-90。小寫轉(zhuǎn)大寫只需c - a A或c - 32。代碼實現(xiàn)與注釋#include iostream #include string #include cctype using namespace std; int main() { string s; cin s; // 或 getline(cin, s) 如果包含空格 for (char c : s) { // 使用引用直接修改原字符串 c toupper(c); // 方法一庫函數(shù) // 方法二if (c a c z) c c - a A; } cout s endl; return 0; }注意事項與踩坑點雖然簡單但要注意輸入字符串是否可能包含空格。如果題目說明是“一行字符串”則可能需要使用getline(cin, s)。仔細看題 使用范圍循環(huán)for (char c : s)時記得加引用否則修改的是副本。3.5 試題E123前綴和與數(shù)學(xué)規(guī)律題題目大意有一個無限長的序列1, 1,2, 1,2,3, 1,2,3,4, ...。即先放1再放1,2再放1,2,3以此類推。多次詢問每次詢問區(qū)間[L, R]內(nèi)所有數(shù)的和。核心思路解析問題規(guī)模L和R可以非常大比如10^12不可能直接模擬生成序列。尋找規(guī)律序列是分塊的。第i塊包含數(shù)字1到i。第1塊長度1數(shù)字和1。第2塊長度2數(shù)字和123。第3塊長度3數(shù)字和1236。第i塊長度i數(shù)字和i*(i1)/2。定位與求和給定一個位置pos需要知道它在第幾塊以及在該塊內(nèi)的第幾個位置。如何找到pos所在的塊號k滿足條件12... (k-1) pos 12...k。即k*(k-1)/2 pos k*(k1)/2。可以通過解不等式或二分查找得到k。知道塊號k后該塊起始位置的前綴和是S(k-1) sum_{i1}^{k-1} (i*(i1)/2)。這個公式可以簡化sum i*(i1)/2 1/2 * (sum i^2 sum i) 1/2 * (n(n1)(2n1)/6 n(n1)/2) n(n1)(n2)/6。所以前m塊的總數(shù)字和不是位置和是F(m) m*(m1)*(m2)/6。對于位置pos假設(shè)它在第k塊中的偏移量為offset (offset pos - k*(k-1)/2)。那么從第1塊到pos位置的總和可以分兩部分計算前k-1塊的總和F(k-1)。第k塊中前offset個數(shù)的和12...offset offset*(offset1)/2。因此區(qū)間[L,R]的和等于sumToPos(R) - sumToPos(L-1)。代碼實現(xiàn)與注釋#include iostream #include cmath using namespace std; using ll long long; // 計算前x塊的總數(shù)字和 ll sumOfBlocks(ll x) { return x * (x 1) * (x 2) / 6; } // 計算從序列開始到位置pos的總和 ll sumToPos(ll pos) { if (pos 0) return 0; // 二分查找pos所在的塊號k ll l 1, r 2e6; // 估算一個上界因為k*(k1)/2 pos, k約等于sqrt(2*pos) while (l r) { ll mid (l r) / 2; if (mid * (mid 1) / 2 pos) { r mid; } else { l mid 1; } } ll k l; // pos所在的塊號 // 前k-1塊的總和 ll res sumOfBlocks(k - 1); // 在第k塊中的偏移量從1開始 ll offset pos - (k - 1) * k / 2; // 加上第k塊內(nèi)前offset個數(shù)的和 res offset * (offset 1) / 2; return res; } int main() { int T; cin T; while (T--) { ll L, R; cin L R; cout sumToPos(R) - sumToPos(L - 1) endl; } return 0; }注意事項與踩坑點二分查找的邊界塊號k的上界需要合理估計。因為k*(k1)/2 ≈ pos所以k ≈ sqrt(2*pos)。對于pos最大為10^12sqrt(2e12) ≈ 1.4e6所以上界設(shè)為2e6是安全的。數(shù)據(jù)溢出計算過程中涉及多個大數(shù)相乘如k*(k1)*(k2)即使k2e6結(jié)果也遠超32位int范圍。必須全程使用long long。公式推導(dǎo)的正確性sumOfBlocks的公式m*(m1)*(m2)/6需要自己動手推導(dǎo)驗證死記硬背容易出錯。可以寫個小程序驗證前幾項。位置與偏移量的計算(k-1)*k/2是前k-1塊的總長度也是第k塊開始的位置。offset的計算要小心確保是從1開始計數(shù)。4. 常見問題與調(diào)試技巧實錄在競賽或練習(xí)中除了算法思路調(diào)試能力同樣決定成敗。以下是我在解決這類題目時積累的一些常見問題排查技巧。4.1 答案錯誤Wrong Answer的排查流程重讀題目確保完全理解題意特別是輸入輸出格式、數(shù)據(jù)范圍、邊界條件如LRN0。這是最常見的問題源。測試樣例自己構(gòu)造一些小的、邊界性的測試用例。對于日期題測試閏年2月29日、跨年、同一天等。對于DP題測試N0,1,2,3。中間輸出調(diào)試在代碼關(guān)鍵位置如循環(huán)內(nèi)、狀態(tài)轉(zhuǎn)移后打印中間變量與手算結(jié)果對比。例如在動態(tài)規(guī)劃題中打印出dp數(shù)組的前幾項。對拍寫一個暴力但正確的程序通常只適用于小數(shù)據(jù)范圍用隨機生成的數(shù)據(jù)同時運行你的優(yōu)化程序和暴力程序比較輸出。這是找出邏輯錯誤的大殺器。關(guān)注溢出對于涉及大量加法、乘法的題目如“123”int溢出是隱形殺手。養(yǎng)成習(xí)慣看到10^5以上的數(shù)據(jù)范圍直接使用long long。4.2 時間超限Time Limit Exceeded的優(yōu)化思路復(fù)雜度分析首先分析你的算法理論時間復(fù)雜度。O(N^2)對于N10^5肯定超時。國賽B組O(NlogN)或O(N)通常是安全的。減少常數(shù)檢查循環(huán)內(nèi)部是否有不必要的函數(shù)調(diào)用如pow,sqrt、是否能用前綴和/差分避免重復(fù)計算、是否能用數(shù)組代替vector以提升訪問速度在C中差異不大但在極端情況下有影響。I/O優(yōu)化當(dāng)輸入數(shù)據(jù)量巨大時如10^6個數(shù)使用cin/cout可能成為瓶頸。可以ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);或者使用scanf/printf。避免遞歸過深DFS等遞歸算法在數(shù)據(jù)量大時可能棧溢出或超時考慮迭代寫法或顯式棧。4.3 內(nèi)存超限Memory Limit Exceeded的檢查點檢查數(shù)據(jù)結(jié)構(gòu)大小你申請的數(shù)組大小是否與題目要求匹配int dp[1000000]大約占用4MBlong long則翻倍。估算一下總內(nèi)存消耗。不必要的緩存是否存儲了所有中間結(jié)果有時可以滾動數(shù)組只保留最近幾層狀態(tài)。遞歸開銷深度遞歸不僅慢而且每個函數(shù)調(diào)用都會占用棧空間。4.4 藍橋杯國賽特有的注意事項結(jié)果填空題有些題目是填空題只要求提交最終結(jié)果。對于這類題可以寫程序暴力計算但一定要確保答案唯一且正確。計算出來后最好用不同的思路或程序驗證。編程題仔細閱讀輸入輸出描述。藍橋杯有時要求輸出特定格式比如“Case #1: ”前綴或者結(jié)果對某個數(shù)取模。環(huán)境差異本地環(huán)境如Mac的Clang和比賽環(huán)境通常Windows的GCC可能有細微差別比如rand()函數(shù)、to_string的支持度。避免使用非標準特性。長整型使用國賽題目經(jīng)常涉及大數(shù)long long是你的好朋友。定義別名using ll long long;是個好習(xí)慣。5. 備賽策略與資源推薦國賽的備戰(zhàn)是一個系統(tǒng)工程不能只靠刷題。5.1 系統(tǒng)性知識梳理你需要一個清晰的知識圖譜基礎(chǔ)語法與STL熟練使用C11/14掌握vector,map,set,queue,stack,string等容器及其方法。基礎(chǔ)算法排序、二分查找、前綴和、差分、雙指針。搜索DFS、BFS、回溯、剪枝。動態(tài)規(guī)劃線性DP、背包DP、區(qū)間DP、樹形DP、狀態(tài)壓縮DP。掌握經(jīng)典模型和狀態(tài)設(shè)計方法。圖論最短路Dijkstra, Floyd, SPFA、最小生成樹Kruskal, Prim、拓撲排序、并查集。數(shù)學(xué)質(zhì)數(shù)篩法、快速冪、最大公約數(shù)/最小公倍數(shù)、簡單組合數(shù)學(xué)。數(shù)據(jù)結(jié)構(gòu)單調(diào)棧、單調(diào)隊列、并查集、樹狀數(shù)組、線段樹提高組。5.2 有效的練習(xí)方法專題突破針對自己的弱點進行集中訓(xùn)練。例如花一周時間專門練習(xí)動態(tài)規(guī)劃從簡單題到難題。模擬賽定期進行4小時的全程模擬使用歷年真題或高質(zhì)量模擬題。嚴格計時模擬真實比賽環(huán)境包括不能上網(wǎng)查資料。復(fù)盤總結(jié)每做完一套題或一次模擬賽無論結(jié)果如何必須復(fù)盤。寫出詳細的題解記錄自己的思考過程、錯誤原因、優(yōu)化方法。本篇“未完待續(xù)”的題解就是極好的復(fù)盤形式。構(gòu)建代碼模板將常用的、易錯的算法如快速冪、Dijkstra、并查集寫成簡潔、正確的模板并熟記于心。5.3 資源推薦官方題庫藍橋杯官網(wǎng)的練習(xí)系統(tǒng)是最直接的資源。在線判題平臺洛谷、AcWing、Codeforces、LeetCode側(cè)重算法思維都有豐富的題庫和社區(qū)討論。書籍《算法競賽入門經(jīng)典》劉汝佳、《算法競賽進階指南》李煜東是經(jīng)典教材。社區(qū)與博客多看看其他優(yōu)秀選手的博客和題解學(xué)習(xí)不同的思路和編碼技巧。國賽的挑戰(zhàn)性正在于它綜合考察了你的知識廣度、思維深度、編碼速度和心理素質(zhì)。這份針對2021年國賽B組的“未完待續(xù)”式深度解析希望能幫你捋清一類題目的解題脈絡(luò)更重要的是傳遞一種“復(fù)盤”和“深究”的態(tài)度。每一道錯題、每一個卡住的點都是進步的階梯。當(dāng)你能夠獨立完成這樣一篇詳盡的題解時你的實力必然已經(jīng)更上一層樓了。