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