盤：從字符串處理到狀態(tài)壓縮DP的實戰(zhàn)策略)
1. 從賽場到復(fù)盤一次完整的國賽解題心路剛結(jié)束第十三屆藍橋杯國賽的C/C B組比賽從考場出來腦子還沉浸在那些算法邏輯和邊界條件里。這種級別的競賽題目本身固然是核心但解題過程中的思路拆解、工具運用和心態(tài)調(diào)整其價值往往不亞于最終的答案。我把自己在賽場上的思考、實現(xiàn)以及賽后的一些反思整理出來這不僅僅是一份“題解”更像是一次完整的實戰(zhàn)復(fù)盤。無論你是即將參賽的選手還是對算法競賽感興趣的開發(fā)者希望這份結(jié)合了具體代碼、策略分析和踩坑記錄的經(jīng)驗?zāi)芙o你帶來一些實實在在的參考。我們直接進入正題看看這次國賽B組都考了些什么以及如何一步步拿下它們。2. 賽題整體分析與策略制定國賽的題目通常不會在奇技淫巧上做太多文章更側(cè)重于考察對基礎(chǔ)算法和數(shù)據(jù)結(jié)構(gòu)的深刻理解、縝密的邏輯思維以及將實際問題轉(zhuǎn)化為計算模型的能力。拿到題目后我習(xí)慣先用5-10分鐘快速通讀所有題目對難度和類型有個大致判斷而不是一頭扎進第一題。2.1 題目概覽與難度評估這次B組的題目覆蓋面很廣。通常會有1-2道純簽到題考察基本語法和簡單邏輯2-3道需要用到經(jīng)典算法如DFS/BFS、動態(tài)規(guī)劃、貪心的中等題以及1-2道對思維能力和代碼實現(xiàn)要求都較高的壓軸題?？焖贋g覽后我初步判斷前兩題屬于“必拿分”范疇主要防止粗心中間幾題是得分主力需要穩(wěn)扎穩(wěn)打最后一題則需要仔細分析爭取部分分數(shù)。注意國賽時間寶貴切忌在簡單題上追求“最優(yōu)解”而浪費過多時間。我們的目標是總分最大化而不是某一道題完美。對于一眼就有清晰暴力解法的題先確保AC通過所有測試用例如果后面有時間再回來優(yōu)化。2.2 環(huán)境與工具的準備要點工欲善其事必先利其器。比賽是在指定的OJ在線判題系統(tǒng)上進行但前期的代碼編寫和測試離不開本地環(huán)境。編輯器/IDE選擇我使用的是VS Code搭配C/C插件。它的優(yōu)勢在于輕量、啟動快并且代碼補全和跳轉(zhuǎn)功能足夠用。關(guān)鍵是要提前配置好基本的代碼片段Snippet比如快速生成freopen用于本地文件輸入輸出、生成常見算法框架如Dijkstra、快速冪等。輸入輸出重定向這是調(diào)試的利器。在main函數(shù)開頭加入以下代碼可以在本地測試時從文件讀取數(shù)據(jù)提交時只需注釋掉freopen行即可。#ifdef LOCAL freopen(“input.txt”, “r”, stdin); freopen(“output.txt”, “w”, stdout); #endif編譯時定義LOCAL宏如-DLOCAL就能自動切換。調(diào)試與打印復(fù)雜邏輯的調(diào)試不能只靠腦子想。我通常會定義一個DEBUG宏在需要時輸出關(guān)鍵的中間變量值。#define DEBUG #ifdef DEBUG #define debug(x) cout #x “ “ x endl #else #define debug(x) #endif這樣用debug(a)就能方便地輸出變量a的值提交前關(guān)閉DEBUG宏即可。這些準備工作看似瑣碎但在緊張的比賽環(huán)境中能為你節(jié)省大量時間并減少因低級錯誤導(dǎo)致的失分。3. 核心題目詳解與實現(xiàn)思路下面我將挑選本屆比賽中幾道有代表性、能體現(xiàn)不同解題思維的題目進行詳細拆解。為了還原真實的解題過程我會先描述題目大意非原題照搬避免版權(quán)問題然后逐步展開我的思考路徑和代碼實現(xiàn)。3.1 簽到題字符串處理與邊界陷阱題目大意給定一個字符串和一系列操作指令指令可能是翻轉(zhuǎn)某個子串也可能是查詢某個字符。最終輸出所有查詢結(jié)果。這看起來是一道簡單的模擬題。但國賽的“簡單題”往往藏著邊界條件的陷阱。思路拆解數(shù)據(jù)結(jié)構(gòu)選擇直接使用C的string類型存儲字符串是最方便的它支持下標訪問和修改。操作模擬對于翻轉(zhuǎn)操作題目給定區(qū)間[l, r]通常下標從1開始。我們需要將其轉(zhuǎn)換為C中從0開始的下標然后使用std::reverse(s.begin() l, s.begin() r 1)即可高效完成。對于查詢操作直接輸出s[pos]。關(guān)鍵陷阱與實現(xiàn)下標轉(zhuǎn)換這是最容易出錯的地方。如果題目說“第l個到第r個字符”那么對應(yīng)到string的下標就是l-1和r-1。我習(xí)慣在輸入l, r后立即執(zhí)行l(wèi)--; r--;讓所有后續(xù)操作都基于0-index進行思考。輸入效率操作指令數(shù)量可能很大達到10^5級別。務(wù)必使用scanf或cin關(guān)閉同步流ios::sync_with_stdio(false);來加速輸入輸出。查詢輸出如果查詢很多不要每次查詢都cout一個字符然后換行這樣效率低?？梢韵葘⒉樵兘Y(jié)果存入一個string或vectorchar最后統(tǒng)一輸出。我的實現(xiàn)代碼片段#include iostream #include string #include algorithm using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); string s; cin s; int m; cin m; while (m--) { int op, l, r, pos; cin op; if (op 1) { // 翻轉(zhuǎn)操作 cin l r; l--; r--; // 轉(zhuǎn)換為0-index reverse(s.begin() l, s.begin() r 1); } else { // 查詢操作 cin pos; pos--; // 轉(zhuǎn)換為0-index cout s[pos] ‘\n’; // 使用‘\n’而非endl } } return 0; }實操心得對于所有涉及區(qū)間下標的題目在思維和代碼中統(tǒng)一使用一種索引方式強烈推薦0-index并在輸入后第一時間進行轉(zhuǎn)換能極大降低思維負擔和出錯概率。3.2 中等題圖論建模與BFS求最短路徑題目大意一個網(wǎng)格圖某些格子是障礙某些格子是傳送門成對出現(xiàn)可瞬間移動。求從起點到終點的最少步數(shù)。每次移動可以上下左右走到非障礙格子或者如果當前格是傳送門可以花費0步傳送到其配對格子。思路拆解問題本質(zhì)這是一個帶“0權(quán)邊”的最短路問題。普通格子間移動邊權(quán)為1傳送門之間移動邊權(quán)為0。求單源最短路自然想到BFS0-1 BFS或Dijkstra算法。由于邊權(quán)只有0和1使用0-1 BFS雙端隊列deque實現(xiàn)效率更高時間復(fù)雜度為O(N*M)。數(shù)據(jù)結(jié)構(gòu)建模用二維數(shù)組grid存儲地圖。用pairint, int的數(shù)組teleport記錄傳送門信息。當輸入一對傳送門(A, B)時需要建立雙向的瞬間可達關(guān)系。可以用一個map或二維數(shù)組來快速查詢某個坐標是否為傳送門及其配對坐標。算法實現(xiàn)細節(jié)0-1 BFS使用deque代替普通隊列。dist[x][y]記錄起點到(x,y)的最短距離初始化為無窮大。起點距離為0加入deque前端。當隊列不空時從前端取出節(jié)點(x, y)。遍歷四個方向新坐標(nx, ny)合法且非障礙如果dist[nx][ny] dist[x][y] 1則更新距離并將(nx, ny)推入隊列后端因為邊權(quán)為1。關(guān)鍵步驟如果(x, y)是傳送門設(shè)其配對點為(tx, ty)。如果dist[tx][ty] dist[x][y]則更新距離并將(tx, ty)推入隊列前端因為邊權(quán)為0。一個易錯點傳送門是否可重復(fù)使用題目通常默認可以。但如果傳送門使用后消失則需要用狀態(tài)標記情況會更復(fù)雜本題未做此要求。我的實現(xiàn)代碼框架#include iostream #include vector #include deque #include cstring using namespace std; const int MAXN 1005; const int INF 0x3f3f3f3f; const int dx[4] {1, -1, 0, 0}; const int dy[4] {0, 0, 1, -1}; struct Point { int x, y; }; int n, m; char grid[MAXN][MAXN]; int dist[MAXN][MAXN]; Point teleport[MAXN][MAXN]; // teleport[x][y] 存儲配對點坐標若為(-1,-1)則不是傳送門 bool isTele[MAXN][MAXN]; int bfs(Point start, Point end) { memset(dist, 0x3f, sizeof(dist)); dequePoint dq; dist[start.x][start.y] 0; dq.push_front(start); while (!dq.empty()) { Point cur dq.front(); dq.pop_front(); int x cur.x, y cur.y; // 如果到達終點可以提前結(jié)束BFS首次訪問即是最短 if (x end.x y end.y) { return dist[x][y]; } // 1. 處理傳送門0權(quán)邊 if (isTele[x][y]) { Point nxt teleport[x][y]; if (dist[nxt.x][nxt.y] dist[x][y]) { dist[nxt.x][nxt.y] dist[x][y]; dq.push_front(nxt); // 0權(quán)邊放前端 } } // 2. 處理普通移動1權(quán)邊 for (int i 0; i 4; i) { int nx x dx[i], ny y dy[i]; if (nx 0 nx n ny 0 ny m grid[nx][ny] ! ‘#’) { if (dist[nx][ny] dist[x][y] 1) { dist[nx][ny] dist[x][y] 1; dq.push_back(nxt); // 1權(quán)邊放后端 } } } } return -1; // 無法到達 }注意事項0-1 BFS中為什么0權(quán)邊放隊首1權(quán)邊放隊尾這保證了隊列前端到后端的距離值是“非遞減”的類似于優(yōu)先隊列但用deque實現(xiàn)常數(shù)更小。這是解決邊權(quán)僅為兩種值的最短路問題的經(jīng)典技巧。3.3 壓軸題動態(tài)規(guī)劃與狀態(tài)壓縮題目大意有N個任務(wù)每個任務(wù)有開始時間、結(jié)束時間和價值。同時有M種資源每種資源在同一時間只能用于一個任務(wù)。一個任務(wù)需要占用一種特定的資源才能完成。求能獲得的最大總價值。思路拆解初步分析這是帶資源約束的區(qū)間調(diào)度問題是經(jīng)典“加權(quán)區(qū)間調(diào)度”的擴展。如果沒有資源限制M1我們可以按結(jié)束時間排序后使用動態(tài)規(guī)劃dp[i] max(dp[i-1], value[i] dp[p[i]])其中p[i]是在任務(wù)i開始之前結(jié)束的最后一個任務(wù)下標。引入資源維度現(xiàn)在有M種資源相當于有M條獨立的“時間線”。一個核心的貪心策略是對于同一種資源其上的任務(wù)選擇依然符合無資源沖突時的最優(yōu)子結(jié)構(gòu)。因此我們可以考慮狀態(tài)壓縮DP。狀態(tài)設(shè)計設(shè)dp[i][mask]表示考慮前i個任務(wù)按結(jié)束時間排序后當前M種資源的使用狀態(tài)為mask一個M位的二進制數(shù)第k位為1表示第k種資源正在被占用時能獲得的最大價值。但這樣狀態(tài)數(shù)是N * 2^M如果M較大比如10會超時。優(yōu)化思路注意到任務(wù)數(shù)是N可能很大但資源種類M通常較小本題可能M10。我們換一種狀態(tài)定義dp[mask]表示達到某種資源占用狀態(tài)mask時能獲得的最大價值。我們按時間順序處理事件任務(wù)開始或結(jié)束。將每個任務(wù)拆分為兩個事件開始事件價值需占用資源和結(jié)束事件-價值釋放資源。將所有事件按時間排序時間相同時處理結(jié)束事件優(yōu)先于開始事件釋放資源后才能被再利用。遍歷事件如果是結(jié)束事件dp[mask] max(dp[mask], dp[mask_with_resource_k])其中mask_with_resource_k是包含了該任務(wù)所占資源的那個狀態(tài)。這表示該任務(wù)完成狀態(tài)轉(zhuǎn)移時不增加價值只是釋放了資源。如果是開始事件假設(shè)任務(wù)需要資源r其價值為v。對于所有當前mask中資源r未被占用的狀態(tài)嘗試開始這個任務(wù)new_mask mask | (1r)dp[new_mask] max(dp[new_mask], dp[mask] v)。最終答案所有dp[mask]中的最大值。關(guān)鍵點與實現(xiàn)技巧事件排序確保結(jié)束事件先于開始事件防止一個任務(wù)剛結(jié)束釋放的資源被同一個時間點開始的另一個任務(wù)錯誤占用。狀態(tài)初始化dp[0] 0其他狀態(tài)為負無窮。復(fù)雜度事件數(shù)O(N)狀態(tài)數(shù)O(2^M)總復(fù)雜度O(N * 2^M)在M10時可行。實操心得對于“時間”“資源”的調(diào)度問題事件驅(qū)動掃描線配合狀態(tài)壓縮DP是一個強有力的框架。難點在于正確設(shè)計事件類型和狀態(tài)轉(zhuǎn)移順序。在紙上畫出幾個任務(wù)的時間線模擬事件處理過程對厘清邏輯非常有幫助。4. 常見失誤點與賽場調(diào)試策略即使思路正確實現(xiàn)上的一點點疏忽也可能導(dǎo)致丟分。下面是我總結(jié)的幾條高頻“翻車點”和應(yīng)對策略。4.1 數(shù)據(jù)范圍與溢出問題這是C/C選手永恒的痛。國賽題目一定會卡數(shù)據(jù)范圍。整數(shù)溢出場景兩個int型變量a, b例如a1e9, b1e9相乘結(jié)果可能超過int范圍約2.1e9即使你打算存入long long但在計算a*b時表達式類型仍是int已經(jīng)溢出。解決在表達式前強制轉(zhuǎn)換。long long result (long long)a * b;。檢查清單遇到累加、累乘、計算組合數(shù)C(n,m)、距離平方等操作第一時間思考是否需要long long。數(shù)組越界場景開數(shù)組int arr[N]但訪問了arr[N]?；蛘逥FS/BFS中新坐標未判斷是否在網(wǎng)格內(nèi)就進行訪問。解決養(yǎng)成防御性編程習(xí)慣。定義數(shù)組時稍微開大一點如N5。在訪問數(shù)組前務(wù)必進行下標有效性檢查。無窮大的設(shè)置不要用0x7fffffff因為它加一個正數(shù)會溢出變成負數(shù)。推薦使用0x3f3f3f3f這個數(shù)約等于1e9且其兩倍仍在int范圍內(nèi)用memset(arr, 0x3f, sizeof(arr))可以方便地將int數(shù)組初始化為這個值。4.2 輸入輸出與格式錯誤多組輸入題目說“包含多組測試數(shù)據(jù)”但你的代碼只讀了一組。務(wù)必使用while(cin n n ! 0)或while(scanf(“%d”, n) ! EOF)這類循環(huán)。輸出格式最后一行是否需要換行數(shù)字之間用空格還是換行分隔務(wù)必嚴格按照題目要求輸出。一個常見的技巧是第一個元素正常輸出后續(xù)元素先輸出分隔符再輸出元素如cout ans[0]; for(int i1; in; i) cout “ “ ans[i];。浮點數(shù)精度盡量避免直接比較浮點數(shù)相等a b。應(yīng)使用fabs(a-b) 1e-9這樣的方式。輸出時若要求保留小數(shù)使用printf(“%.2f\n”, value);不要用cout的setprecision容易忘掉fixed。4.3 算法選擇與復(fù)雜度誤判暴力搜索剪枝以為DFS暴力能過結(jié)果數(shù)據(jù)量大導(dǎo)致超時。在實現(xiàn)前務(wù)必估算最壞情況下的時間復(fù)雜度。例如N20子集枚舉是2^20≈1e6可接受N302^30≈1e9基本會超時。容器選擇不當在需要頻繁按值查找如判斷一個數(shù)是否在集合中時使用vector遍歷查找是O(N)而使用unordered_set是平均O(1)。在需要有序數(shù)據(jù)時使用set。4.4 調(diào)試策略當程序WA答案錯誤時先讀題再讀題確保完全理解題意包括輸入輸出格式、數(shù)據(jù)范圍、特殊規(guī)定如多組數(shù)據(jù)、文件尾結(jié)束。WA的一半原因在于誤解題意。構(gòu)造小數(shù)據(jù)不要依賴OJ給的樣例。自己手寫幾個小的、邊界的數(shù)據(jù)測試。比如N0或1的情況數(shù)組全部元素相同的情況負數(shù)的情況。輸出中間變量在懷疑的邏輯段前后輸出關(guān)鍵變量的值。對比你的計算過程和手算結(jié)果是否一致。對拍對于難題如果你有一個保證正確但效率低的暴力算法例如用于小數(shù)據(jù)范圍可以寫一個隨機數(shù)據(jù)生成器讓你的優(yōu)化算法和暴力算法跑同樣的數(shù)據(jù)對比輸出。這是找出深藏BUG的終極手段。5. 從備賽到實戰(zhàn)我的個人經(jīng)驗體會最后拋開具體的題目我想分享幾點關(guān)于備賽和實戰(zhàn)的體會這些可能比解出某一道題更重要。關(guān)于學(xué)習(xí)路徑算法競賽的知識體系龐大但核心是數(shù)據(jù)結(jié)構(gòu)數(shù)組、鏈表、棧、隊列、樹、圖、并查集、堆和基礎(chǔ)算法排序、二分、遞歸、分治、貪心、動態(tài)規(guī)劃、搜索、最短路、最小生成樹。不要一開始就死磕高難度的“模板”把《算法競賽入門經(jīng)典》劉汝佳這類基礎(chǔ)書上的例題和習(xí)題扎扎實實過一遍收獲遠大于漫無目的地刷題。關(guān)于刷題質(zhì)量遠大于數(shù)量。每做一道題尤其是做錯的題一定要徹底弄懂。嘗試用多種方法解同一道題思考時間與空間復(fù)雜度的權(quán)衡。建立自己的“解題本”或博客記錄經(jīng)典題目的思路、易錯點和代碼模板。藍橋杯歷屆真題是非常好的素材它的題目風(fēng)格相對穩(wěn)定。關(guān)于比賽心態(tài)4個小時的比賽是腦力、體力和心態(tài)的綜合較量。開局不順很正常不要糾結(jié)于一題。按照“先易后難”的順序確保簡單題不丟分。如果一道題卡了30分鐘以上還沒有清晰思路果斷標記后跳過去看下一題。很多時候解決后面的題目會給你帶來新的靈感。最后一定要留出至少20分鐘檢查文件名、輸入輸出、數(shù)組大小、long long、多組數(shù)據(jù)等。關(guān)于工具熟練度你平時用什么環(huán)境寫代碼比賽就用什么。不要在比賽當天嘗試新IDE或編輯器。將常用的代碼模板快速冪、并查集、Dijkstra等提前準備好放在一個單獨的文件里比賽時快速復(fù)制粘貼能節(jié)省大量時間并避免手誤。國賽只是一個節(jié)點無論結(jié)果如何在這個過程中對問題分析能力、編碼能力和抗壓能力的鍛煉才是真正寶貴的財富。保持熱愛持續(xù)思考下一次你會做得更好。 藍橋杯國賽C++ B組解題復(fù)盤：從字符串處理到狀態(tài)壓縮DP的實戰(zhàn)策略
1. 從賽場到復(fù)盤一次完整的國賽解題心路剛結(jié)束第十三屆藍橋杯國賽的C/C B組比賽從考場出來腦子還沉浸在那些算法邏輯和邊界條件里。這種級別的競賽題目本身固然是核心但解題過程中的思路拆解、工具運用和心態(tài)調(diào)整其價值往往不亞于最終的答案。我把自己在賽場上的思考、實現(xiàn)以及賽后的一些反思整理出來這不僅僅是一份“題解”更像是一次完整的實戰(zhàn)復(fù)盤。無論你是即將參賽的選手還是對算法競賽感興趣的開發(fā)者希望這份結(jié)合了具體代碼、策略分析和踩坑記錄的經(jīng)驗?zāi)芙o你帶來一些實實在在的參考。我們直接進入正題看看這次國賽B組都考了些什么以及如何一步步拿下它們。2. 賽題整體分析與策略制定國賽的題目通常不會在奇技淫巧上做太多文章更側(cè)重于考察對基礎(chǔ)算法和數(shù)據(jù)結(jié)構(gòu)的深刻理解、縝密的邏輯思維以及將實際問題轉(zhuǎn)化為計算模型的能力。拿到題目后我習(xí)慣先用5-10分鐘快速通讀所有題目對難度和類型有個大致判斷而不是一頭扎進第一題。2.1 題目概覽與難度評估這次B組的題目覆蓋面很廣。通常會有1-2道純簽到題考察基本語法和簡單邏輯2-3道需要用到經(jīng)典算法如DFS/BFS、動態(tài)規(guī)劃、貪心的中等題以及1-2道對思維能力和代碼實現(xiàn)要求都較高的壓軸題?？焖贋g覽后我初步判斷前兩題屬于“必拿分”范疇主要防止粗心中間幾題是得分主力需要穩(wěn)扎穩(wěn)打最后一題則需要仔細分析爭取部分分數(shù)。注意國賽時間寶貴切忌在簡單題上追求“最優(yōu)解”而浪費過多時間。我們的目標是總分最大化而不是某一道題完美。對于一眼就有清晰暴力解法的題先確保AC通過所有測試用例如果后面有時間再回來優(yōu)化。2.2 環(huán)境與工具的準備要點工欲善其事必先利其器。比賽是在指定的OJ在線判題系統(tǒng)上進行但前期的代碼編寫和測試離不開本地環(huán)境。編輯器/IDE選擇我使用的是VS Code搭配C/C插件。它的優(yōu)勢在于輕量、啟動快并且代碼補全和跳轉(zhuǎn)功能足夠用。關(guān)鍵是要提前配置好基本的代碼片段Snippet比如快速生成freopen用于本地文件輸入輸出、生成常見算法框架如Dijkstra、快速冪等。輸入輸出重定向這是調(diào)試的利器。在main函數(shù)開頭加入以下代碼可以在本地測試時從文件讀取數(shù)據(jù)提交時只需注釋掉freopen行即可。#ifdef LOCAL freopen(“input.txt”, “r”, stdin); freopen(“output.txt”, “w”, stdout); #endif編譯時定義LOCAL宏如-DLOCAL就能自動切換。調(diào)試與打印復(fù)雜邏輯的調(diào)試不能只靠腦子想。我通常會定義一個DEBUG宏在需要時輸出關(guān)鍵的中間變量值。#define DEBUG #ifdef DEBUG #define debug(x) cout #x “ “ x endl #else #define debug(x) #endif這樣用debug(a)就能方便地輸出變量a的值提交前關(guān)閉DEBUG宏即可。這些準備工作看似瑣碎但在緊張的比賽環(huán)境中能為你節(jié)省大量時間并減少因低級錯誤導(dǎo)致的失分。3. 核心題目詳解與實現(xiàn)思路下面我將挑選本屆比賽中幾道有代表性、能體現(xiàn)不同解題思維的題目進行詳細拆解。為了還原真實的解題過程我會先描述題目大意非原題照搬避免版權(quán)問題然后逐步展開我的思考路徑和代碼實現(xiàn)。3.1 簽到題字符串處理與邊界陷阱題目大意給定一個字符串和一系列操作指令指令可能是翻轉(zhuǎn)某個子串也可能是查詢某個字符。最終輸出所有查詢結(jié)果。這看起來是一道簡單的模擬題。但國賽的“簡單題”往往藏著邊界條件的陷阱。思路拆解數(shù)據(jù)結(jié)構(gòu)選擇直接使用C的string類型存儲字符串是最方便的它支持下標訪問和修改。操作模擬對于翻轉(zhuǎn)操作題目給定區(qū)間[l, r]通常下標從1開始。我們需要將其轉(zhuǎn)換為C中從0開始的下標然后使用std::reverse(s.begin() l, s.begin() r 1)即可高效完成。對于查詢操作直接輸出s[pos]。關(guān)鍵陷阱與實現(xiàn)下標轉(zhuǎn)換這是最容易出錯的地方。如果題目說“第l個到第r個字符”那么對應(yīng)到string的下標就是l-1和r-1。我習(xí)慣在輸入l, r后立即執(zhí)行l(wèi)--; r--;讓所有后續(xù)操作都基于0-index進行思考。輸入效率操作指令數(shù)量可能很大達到10^5級別。務(wù)必使用scanf或cin關(guān)閉同步流ios::sync_with_stdio(false);來加速輸入輸出。查詢輸出如果查詢很多不要每次查詢都cout一個字符然后換行這樣效率低?？梢韵葘⒉樵兘Y(jié)果存入一個string或vectorchar最后統(tǒng)一輸出。我的實現(xiàn)代碼片段#include iostream #include string #include algorithm using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); string s; cin s; int m; cin m; while (m--) { int op, l, r, pos; cin op; if (op 1) { // 翻轉(zhuǎn)操作 cin l r; l--; r--; // 轉(zhuǎn)換為0-index reverse(s.begin() l, s.begin() r 1); } else { // 查詢操作 cin pos; pos--; // 轉(zhuǎn)換為0-index cout s[pos] ‘\n’; // 使用‘\n’而非endl } } return 0; }實操心得對于所有涉及區(qū)間下標的題目在思維和代碼中統(tǒng)一使用一種索引方式強烈推薦0-index并在輸入后第一時間進行轉(zhuǎn)換能極大降低思維負擔和出錯概率。3.2 中等題圖論建模與BFS求最短路徑題目大意一個網(wǎng)格圖某些格子是障礙某些格子是傳送門成對出現(xiàn)可瞬間移動。求從起點到終點的最少步數(shù)。每次移動可以上下左右走到非障礙格子或者如果當前格是傳送門可以花費0步傳送到其配對格子。思路拆解問題本質(zhì)這是一個帶“0權(quán)邊”的最短路問題。普通格子間移動邊權(quán)為1傳送門之間移動邊權(quán)為0。求單源最短路自然想到BFS0-1 BFS或Dijkstra算法。由于邊權(quán)只有0和1使用0-1 BFS雙端隊列deque實現(xiàn)效率更高時間復(fù)雜度為O(N*M)。數(shù)據(jù)結(jié)構(gòu)建模用二維數(shù)組grid存儲地圖。用pairint, int的數(shù)組teleport記錄傳送門信息。當輸入一對傳送門(A, B)時需要建立雙向的瞬間可達關(guān)系。可以用一個map或二維數(shù)組來快速查詢某個坐標是否為傳送門及其配對坐標。算法實現(xiàn)細節(jié)0-1 BFS使用deque代替普通隊列。dist[x][y]記錄起點到(x,y)的最短距離初始化為無窮大。起點距離為0加入deque前端。當隊列不空時從前端取出節(jié)點(x, y)。遍歷四個方向新坐標(nx, ny)合法且非障礙如果dist[nx][ny] dist[x][y] 1則更新距離并將(nx, ny)推入隊列后端因為邊權(quán)為1。關(guān)鍵步驟如果(x, y)是傳送門設(shè)其配對點為(tx, ty)。如果dist[tx][ty] dist[x][y]則更新距離并將(tx, ty)推入隊列前端因為邊權(quán)為0。一個易錯點傳送門是否可重復(fù)使用題目通常默認可以。但如果傳送門使用后消失則需要用狀態(tài)標記情況會更復(fù)雜本題未做此要求。我的實現(xiàn)代碼框架#include iostream #include vector #include deque #include cstring using namespace std; const int MAXN 1005; const int INF 0x3f3f3f3f; const int dx[4] {1, -1, 0, 0}; const int dy[4] {0, 0, 1, -1}; struct Point { int x, y; }; int n, m; char grid[MAXN][MAXN]; int dist[MAXN][MAXN]; Point teleport[MAXN][MAXN]; // teleport[x][y] 存儲配對點坐標若為(-1,-1)則不是傳送門 bool isTele[MAXN][MAXN]; int bfs(Point start, Point end) { memset(dist, 0x3f, sizeof(dist)); dequePoint dq; dist[start.x][start.y] 0; dq.push_front(start); while (!dq.empty()) { Point cur dq.front(); dq.pop_front(); int x cur.x, y cur.y; // 如果到達終點可以提前結(jié)束BFS首次訪問即是最短 if (x end.x y end.y) { return dist[x][y]; } // 1. 處理傳送門0權(quán)邊 if (isTele[x][y]) { Point nxt teleport[x][y]; if (dist[nxt.x][nxt.y] dist[x][y]) { dist[nxt.x][nxt.y] dist[x][y]; dq.push_front(nxt); // 0權(quán)邊放前端 } } // 2. 處理普通移動1權(quán)邊 for (int i 0; i 4; i) { int nx x dx[i], ny y dy[i]; if (nx 0 nx n ny 0 ny m grid[nx][ny] ! ‘#’) { if (dist[nx][ny] dist[x][y] 1) { dist[nx][ny] dist[x][y] 1; dq.push_back(nxt); // 1權(quán)邊放后端 } } } } return -1; // 無法到達 }注意事項0-1 BFS中為什么0權(quán)邊放隊首1權(quán)邊放隊尾這保證了隊列前端到后端的距離值是“非遞減”的類似于優(yōu)先隊列但用deque實現(xiàn)常數(shù)更小。這是解決邊權(quán)僅為兩種值的最短路問題的經(jīng)典技巧。3.3 壓軸題動態(tài)規(guī)劃與狀態(tài)壓縮題目大意有N個任務(wù)每個任務(wù)有開始時間、結(jié)束時間和價值。同時有M種資源每種資源在同一時間只能用于一個任務(wù)。一個任務(wù)需要占用一種特定的資源才能完成。求能獲得的最大總價值。思路拆解初步分析這是帶資源約束的區(qū)間調(diào)度問題是經(jīng)典“加權(quán)區(qū)間調(diào)度”的擴展。如果沒有資源限制M1我們可以按結(jié)束時間排序后使用動態(tài)規(guī)劃dp[i] max(dp[i-1], value[i] dp[p[i]])其中p[i]是在任務(wù)i開始之前結(jié)束的最后一個任務(wù)下標。引入資源維度現(xiàn)在有M種資源相當于有M條獨立的“時間線”。一個核心的貪心策略是對于同一種資源其上的任務(wù)選擇依然符合無資源沖突時的最優(yōu)子結(jié)構(gòu)。因此我們可以考慮狀態(tài)壓縮DP。狀態(tài)設(shè)計設(shè)dp[i][mask]表示考慮前i個任務(wù)按結(jié)束時間排序后當前M種資源的使用狀態(tài)為mask一個M位的二進制數(shù)第k位為1表示第k種資源正在被占用時能獲得的最大價值。但這樣狀態(tài)數(shù)是N * 2^M如果M較大比如10會超時。優(yōu)化思路注意到任務(wù)數(shù)是N可能很大但資源種類M通常較小本題可能M10。我們換一種狀態(tài)定義dp[mask]表示達到某種資源占用狀態(tài)mask時能獲得的最大價值。我們按時間順序處理事件任務(wù)開始或結(jié)束。將每個任務(wù)拆分為兩個事件開始事件價值需占用資源和結(jié)束事件-價值釋放資源。將所有事件按時間排序時間相同時處理結(jié)束事件優(yōu)先于開始事件釋放資源后才能被再利用。遍歷事件如果是結(jié)束事件dp[mask] max(dp[mask], dp[mask_with_resource_k])其中mask_with_resource_k是包含了該任務(wù)所占資源的那個狀態(tài)。這表示該任務(wù)完成狀態(tài)轉(zhuǎn)移時不增加價值只是釋放了資源。如果是開始事件假設(shè)任務(wù)需要資源r其價值為v。對于所有當前mask中資源r未被占用的狀態(tài)嘗試開始這個任務(wù)new_mask mask | (1r)dp[new_mask] max(dp[new_mask], dp[mask] v)。最終答案所有dp[mask]中的最大值。關(guān)鍵點與實現(xiàn)技巧事件排序確保結(jié)束事件先于開始事件防止一個任務(wù)剛結(jié)束釋放的資源被同一個時間點開始的另一個任務(wù)錯誤占用。狀態(tài)初始化dp[0] 0其他狀態(tài)為負無窮。復(fù)雜度事件數(shù)O(N)狀態(tài)數(shù)O(2^M)總復(fù)雜度O(N * 2^M)在M10時可行。實操心得對于“時間”“資源”的調(diào)度問題事件驅(qū)動掃描線配合狀態(tài)壓縮DP是一個強有力的框架。難點在于正確設(shè)計事件類型和狀態(tài)轉(zhuǎn)移順序。在紙上畫出幾個任務(wù)的時間線模擬事件處理過程對厘清邏輯非常有幫助。4. 常見失誤點與賽場調(diào)試策略即使思路正確實現(xiàn)上的一點點疏忽也可能導(dǎo)致丟分。下面是我總結(jié)的幾條高頻“翻車點”和應(yīng)對策略。4.1 數(shù)據(jù)范圍與溢出問題這是C/C選手永恒的痛。國賽題目一定會卡數(shù)據(jù)范圍。整數(shù)溢出場景兩個int型變量a, b例如a1e9, b1e9相乘結(jié)果可能超過int范圍約2.1e9即使你打算存入long long但在計算a*b時表達式類型仍是int已經(jīng)溢出。解決在表達式前強制轉(zhuǎn)換。long long result (long long)a * b;。檢查清單遇到累加、累乘、計算組合數(shù)C(n,m)、距離平方等操作第一時間思考是否需要long long。數(shù)組越界場景開數(shù)組int arr[N]但訪問了arr[N]?；蛘逥FS/BFS中新坐標未判斷是否在網(wǎng)格內(nèi)就進行訪問。解決養(yǎng)成防御性編程習(xí)慣。定義數(shù)組時稍微開大一點如N5。在訪問數(shù)組前務(wù)必進行下標有效性檢查。無窮大的設(shè)置不要用0x7fffffff因為它加一個正數(shù)會溢出變成負數(shù)。推薦使用0x3f3f3f3f這個數(shù)約等于1e9且其兩倍仍在int范圍內(nèi)用memset(arr, 0x3f, sizeof(arr))可以方便地將int數(shù)組初始化為這個值。4.2 輸入輸出與格式錯誤多組輸入題目說“包含多組測試數(shù)據(jù)”但你的代碼只讀了一組。務(wù)必使用while(cin n n ! 0)或while(scanf(“%d”, n) ! EOF)這類循環(huán)。輸出格式最后一行是否需要換行數(shù)字之間用空格還是換行分隔務(wù)必嚴格按照題目要求輸出。一個常見的技巧是第一個元素正常輸出后續(xù)元素先輸出分隔符再輸出元素如cout ans[0]; for(int i1; in; i) cout “ “ ans[i];。浮點數(shù)精度盡量避免直接比較浮點數(shù)相等a b。應(yīng)使用fabs(a-b) 1e-9這樣的方式。輸出時若要求保留小數(shù)使用printf(“%.2f\n”, value);不要用cout的setprecision容易忘掉fixed。4.3 算法選擇與復(fù)雜度誤判暴力搜索剪枝以為DFS暴力能過結(jié)果數(shù)據(jù)量大導(dǎo)致超時。在實現(xiàn)前務(wù)必估算最壞情況下的時間復(fù)雜度。例如N20子集枚舉是2^20≈1e6可接受N302^30≈1e9基本會超時。容器選擇不當在需要頻繁按值查找如判斷一個數(shù)是否在集合中時使用vector遍歷查找是O(N)而使用unordered_set是平均O(1)。在需要有序數(shù)據(jù)時使用set。4.4 調(diào)試策略當程序WA答案錯誤時先讀題再讀題確保完全理解題意包括輸入輸出格式、數(shù)據(jù)范圍、特殊規(guī)定如多組數(shù)據(jù)、文件尾結(jié)束。WA的一半原因在于誤解題意。構(gòu)造小數(shù)據(jù)不要依賴OJ給的樣例。自己手寫幾個小的、邊界的數(shù)據(jù)測試。比如N0或1的情況數(shù)組全部元素相同的情況負數(shù)的情況。輸出中間變量在懷疑的邏輯段前后輸出關(guān)鍵變量的值。對比你的計算過程和手算結(jié)果是否一致。對拍對于難題如果你有一個保證正確但效率低的暴力算法例如用于小數(shù)據(jù)范圍可以寫一個隨機數(shù)據(jù)生成器讓你的優(yōu)化算法和暴力算法跑同樣的數(shù)據(jù)對比輸出。這是找出深藏BUG的終極手段。5. 從備賽到實戰(zhàn)我的個人經(jīng)驗體會最后拋開具體的題目我想分享幾點關(guān)于備賽和實戰(zhàn)的體會這些可能比解出某一道題更重要。關(guān)于學(xué)習(xí)路徑算法競賽的知識體系龐大但核心是數(shù)據(jù)結(jié)構(gòu)數(shù)組、鏈表、棧、隊列、樹、圖、并查集、堆和基礎(chǔ)算法排序、二分、遞歸、分治、貪心、動態(tài)規(guī)劃、搜索、最短路、最小生成樹。不要一開始就死磕高難度的“模板”把《算法競賽入門經(jīng)典》劉汝佳這類基礎(chǔ)書上的例題和習(xí)題扎扎實實過一遍收獲遠大于漫無目的地刷題。關(guān)于刷題質(zhì)量遠大于數(shù)量。每做一道題尤其是做錯的題一定要徹底弄懂。嘗試用多種方法解同一道題思考時間與空間復(fù)雜度的權(quán)衡。建立自己的“解題本”或博客記錄經(jīng)典題目的思路、易錯點和代碼模板。藍橋杯歷屆真題是非常好的素材它的題目風(fēng)格相對穩(wěn)定。關(guān)于比賽心態(tài)4個小時的比賽是腦力、體力和心態(tài)的綜合較量。開局不順很正常不要糾結(jié)于一題。按照“先易后難”的順序確保簡單題不丟分。如果一道題卡了30分鐘以上還沒有清晰思路果斷標記后跳過去看下一題。很多時候解決后面的題目會給你帶來新的靈感。最后一定要留出至少20分鐘檢查文件名、輸入輸出、數(shù)組大小、long long、多組數(shù)據(jù)等。關(guān)于工具熟練度你平時用什么環(huán)境寫代碼比賽就用什么。不要在比賽當天嘗試新IDE或編輯器。將常用的代碼模板快速冪、并查集、Dijkstra等提前準備好放在一個單獨的文件里比賽時快速復(fù)制粘貼能節(jié)省大量時間并避免手誤。國賽只是一個節(jié)點無論結(jié)果如何在這個過程中對問題分析能力、編碼能力和抗壓能力的鍛煉才是真正寶貴的財富。保持熱愛持續(xù)思考下一次你會做得更好。