2. 先把模擬算法說(shuō)清楚它到底在“模擬”什么這幾年在算法社區(qū)里看帖發(fā)現(xiàn)一個(gè)很有意思的現(xiàn)象一提起模擬題很多人的第一反應(yīng)是“這不就是照著題目寫代碼嗎有什么技術(shù)含量”。但真到了比賽或者實(shí)際項(xiàng)目里翻車最多的恰恰是這類題目。我自己帶過(guò)不少剛?cè)腴TC競(jìng)賽的新人也在一些嵌入式項(xiàng)目里用模擬邏輯處理過(guò)狀態(tài)機(jī)可以說(shuō)模擬算法遠(yuǎn)不止“照著做”這么簡(jiǎn)單。先說(shuō)定義。模擬算法通常指的是直接用代碼去復(fù)現(xiàn)某個(gè)過(guò)程、某個(gè)規(guī)則、某套系統(tǒng)的運(yùn)行邏輯以此得到問(wèn)題的結(jié)果。它不需要推導(dǎo)復(fù)雜的數(shù)學(xué)公式不需要套用經(jīng)典的數(shù)據(jù)結(jié)構(gòu)模式核心就是把問(wèn)題描述“翻譯”成可執(zhí)行步驟。聽(tīng)起來(lái)很簡(jiǎn)單但這里頭的關(guān)鍵在于怎么把文字描述轉(zhuǎn)換成無(wú)歧義的程序邏輯怎么讓這個(gè)程序在時(shí)限內(nèi)跑完以及怎么處理那些題目描述里語(yǔ)焉不詳?shù)倪吔缜闆r。從應(yīng)用場(chǎng)合來(lái)看模擬算法大致可以分成三類流程模擬比如約瑟夫環(huán)、報(bào)數(shù)出圈、卡片洗牌、排隊(duì)調(diào)度這類題目描述了一個(gè)過(guò)程你要逐步執(zhí)行。系統(tǒng)模擬比如掃雷展開(kāi)、棋類對(duì)弈規(guī)則判斷、電梯調(diào)度、操作系統(tǒng)里的進(jìn)程調(diào)度這類題目涉及多個(gè)對(duì)象之間的交互。數(shù)值模擬比如物理運(yùn)動(dòng)軌跡推算、細(xì)胞自動(dòng)機(jī)生命游戲、隨機(jī)過(guò)程的蒙特卡洛近似這類往往還牽扯到數(shù)值計(jì)算和時(shí)間步長(zhǎng)。你去看各種C項(xiàng)目里的代碼llama.cpp這類大規(guī)模推理引擎雖然核心是矩陣和張量運(yùn)算但它的內(nèi)存管理、任務(wù)隊(duì)列調(diào)度本質(zhì)上也有大量模擬邏輯在里面——用一個(gè)統(tǒng)一模型去預(yù)判和復(fù)現(xiàn)內(nèi)存分配過(guò)程。甚至更簡(jiǎn)單的單例類設(shè)計(jì)在多線程下做狀態(tài)同步時(shí)也常常先寫一個(gè)模擬程序去驗(yàn)證時(shí)序是否正確。所以模擬算法不是競(jìng)賽專屬的“花架子”它貫穿了從入門到工程實(shí)戰(zhàn)的幾乎所有階段。之所以在C里討論模擬算法特別合適是因?yàn)镃的表現(xiàn)力足夠強(qiáng)STL容器幫你組織數(shù)據(jù)原生數(shù)組幫你精確定位下標(biāo)bitset幫你做狀態(tài)壓縮再加上足夠快的運(yùn)行速度讓那些步驟繁多的模擬不至于因?yàn)檎Z(yǔ)言性能而超時(shí)。后面我會(huì)結(jié)合具體題目來(lái)拆你會(huì)感受到同樣的思路用不同數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)代碼復(fù)雜度和運(yùn)行效率能差出一個(gè)量級(jí)。3. 手寫一個(gè)Cpp模擬程序前務(wù)必想清楚的三個(gè)問(wèn)題很多人拿到模擬題第一反應(yīng)是打開(kāi)編輯器就寫。催著寫代碼這個(gè)問(wèn)題我在別人代碼里和自己身上都見(jiàn)過(guò)多次。其實(shí)模擬算法最忌諱的不是想不到“怎么做”而是沒(méi)有把“按什么規(guī)則做”想清楚就開(kāi)始動(dòng)手。代碼寫了一大半才發(fā)現(xiàn)對(duì)題意的理解和出題人不一樣返工成本極高。3.1 狀態(tài)怎么表示選錯(cuò)數(shù)據(jù)結(jié)構(gòu)后面全是淚模擬程序的核心是“狀態(tài)”。每一輪模擬的執(zhí)行本質(zhì)上就是舊狀態(tài)向新?tīng)顟B(tài)的轉(zhuǎn)移。所以第一步要回答這個(gè)狀態(tài)用什么數(shù)據(jù)結(jié)構(gòu)來(lái)裝。以約瑟夫環(huán)為例N個(gè)人圍成一圈從第1個(gè)人開(kāi)始報(bào)數(shù)報(bào)到M的人出圈問(wèn)最后剩下誰(shuí)。最直觀的做法是用數(shù)組標(biāo)記每個(gè)位置是否還在圈內(nèi)然后循環(huán)遍歷計(jì)數(shù)。但如果你用vector直接erase出圈的人那就涉及到元素的移動(dòng)時(shí)間復(fù)雜度退化。再比如隊(duì)列模擬報(bào)數(shù)報(bào)到的數(shù)字不等于M的人從隊(duì)頭彈出放到隊(duì)尾等于M的人徹底彈出這種方式代碼最短也最貼合“循環(huán)”的語(yǔ)義。選擇依據(jù)很簡(jiǎn)單題目里的實(shí)體是一個(gè)有序序列、一個(gè)集合還是一張網(wǎng)絡(luò)序列用數(shù)組或vector集合用unordered_set或bitset網(wǎng)絡(luò)用鄰接表或鄰接矩陣。另一個(gè)判斷標(biāo)準(zhǔn)是看操作類型——頻繁刪除首尾用queue或deque頻繁按下標(biāo)隨機(jī)訪問(wèn)用vector頻繁在中間插入用list。3.2 時(shí)間成本怎么算先估算再動(dòng)手模擬題最容易讓人掉以輕心的是復(fù)雜度。很多題目的規(guī)則本身就意味著海量步數(shù)如果你不看數(shù)據(jù)范圍悶頭“忠實(shí)”地模擬到了線上立馬超時(shí)。判斷一個(gè)模擬方案是否可行有一個(gè)簡(jiǎn)單的辦法把題目給的數(shù)據(jù)范圍上限代入你算法的時(shí)間復(fù)雜度再結(jié)合C在1秒內(nèi)大約能執(zhí)行10的8次方量級(jí)的基礎(chǔ)操作這個(gè)經(jīng)驗(yàn)值看會(huì)不會(huì)超。如果會(huì)超要么想一個(gè)更高效的數(shù)據(jù)結(jié)構(gòu)來(lái)加速模擬要么這道題實(shí)際上需要你找規(guī)律——這就已經(jīng)脫離純模擬而進(jìn)入優(yōu)化范疇了。舉個(gè)例子一個(gè)模擬鐘表指針轉(zhuǎn)動(dòng)的題目如果給你一個(gè)10的18次方級(jí)別的秒數(shù)讓你算時(shí)針?lè)轴樦睾洗螖?shù)“一秒一秒走”的方案在數(shù)學(xué)上沒(méi)錯(cuò)但10的18次方秒顯然不可行。這就是所謂“模擬會(huì)死規(guī)律才會(huì)活”的典型場(chǎng)景。我見(jiàn)過(guò)太多人卡在這種題上不是不會(huì)做而是沒(méi)意識(shí)到模擬步數(shù)已經(jīng)遠(yuǎn)遠(yuǎn)超出了可執(zhí)行范圍。3.3 邊界條件怎么收斂死循環(huán)和越界都出在這種地方模擬程序最常見(jiàn)的運(yùn)行時(shí)問(wèn)題一個(gè)是死循環(huán)一個(gè)是數(shù)組越界一個(gè)是數(shù)據(jù)結(jié)構(gòu)訪問(wèn)不存在的元素。死循環(huán)的根源通常是狀態(tài)不收斂。循環(huán)條件是“直到滿足某條件”但這條條件在反向或循環(huán)狀態(tài)下可能永遠(yuǎn)不滿足。規(guī)避辦法很簡(jiǎn)單給循環(huán)設(shè)置一個(gè)迭代次數(shù)上限比如超過(guò)N的三次方就強(qiáng)制退出并打印當(dāng)前狀態(tài)以便調(diào)試。這在復(fù)雜系統(tǒng)模擬里幾乎是必備手段。數(shù)組越界往往不是粗心而是邏輯上對(duì)“邊界位置”的判定漏了等號(hào)。處理環(huán)形結(jié)構(gòu)時(shí)把下標(biāo)加一圈長(zhǎng)度再取模是常規(guī)操作但取模前是否要減1、取模后是否會(huì)等于N都得仔細(xì)推敲。更穩(wěn)妥的辦法是把用到的數(shù)組開(kāi)大一點(diǎn)比如N最大是1000就開(kāi)1010甚至1005留出冗余避免一些極端下標(biāo)訪問(wèn)直接把程序干崩。這在C里尤其重要因?yàn)関ector的at方法會(huì)拋異常而原生數(shù)組的下標(biāo)訪問(wèn)是狼性行為——錯(cuò)了也不告訴你直到你在調(diào)試器里看出一堆亂碼。4. 三個(gè)經(jīng)典案例的拆解從題目到代碼的完整推演這里選三個(gè)我實(shí)際在比賽和工程中都碰到的場(chǎng)景分別覆蓋線性結(jié)構(gòu)、二維矩陣和文本解析。不光是給最終代碼關(guān)鍵是把從讀題到寫代碼這條思考鏈路完整攤開(kāi)。4.1 約瑟夫環(huán)隊(duì)列模擬與數(shù)學(xué)解法的分界線題目描述大家都很熟了編號(hào)1到N的人圍成一圈從第1個(gè)人開(kāi)始報(bào)數(shù)報(bào)到M的人出局然后從下一個(gè)人開(kāi)始繼續(xù)報(bào)數(shù)求最后存活者的編號(hào)。最貼合過(guò)程的寫法是用隊(duì)列#include bits/stdc.h using namespace std; int main() { int n, m; cin n m; queueint q; for (int i 1; i n; i) q.push(i); int cnt 1; while (q.size() 1) { int cur q.front(); q.pop(); if (cnt m) { cnt 1; } else { cnt; q.push(cur); } } cout q.front() endl; return 0; }這段代碼的思路特別直觀每次取隊(duì)頭相當(dāng)于當(dāng)前報(bào)數(shù)的人。如果報(bào)到了M就出局不再入隊(duì)否則就放到隊(duì)尾體現(xiàn)環(huán)形的語(yǔ)義。這里有一個(gè)容易寫錯(cuò)的小地方cnt是全局計(jì)數(shù)還是每次重新從1開(kāi)始數(shù)按題意出局的下一個(gè)人從1重新報(bào)數(shù)所以要保留全局計(jì)數(shù)只有報(bào)到M時(shí)才重置為1。我在很多新手代碼里看到他們把cnt放在while循環(huán)里重新初始化導(dǎo)致報(bào)數(shù)永遠(yuǎn)從1開(kāi)始結(jié)果完全不對(duì)。另一種常見(jiàn)實(shí)現(xiàn)是數(shù)組標(biāo)記法維護(hù)一個(gè)bool數(shù)組表示某人是否出局然后不斷往后找到下一個(gè)未出局的人。這個(gè)方法適合M比較小、N比較大的情況因?yàn)殛?duì)列實(shí)現(xiàn)需要把不報(bào)數(shù)的人反復(fù)入隊(duì)出隊(duì)操作次數(shù)是O(N*M)當(dāng)M也很大時(shí)會(huì)有性能問(wèn)題。數(shù)組標(biāo)記法雖然時(shí)間復(fù)雜度同樣不低但常數(shù)會(huì)小一些。不過(guò)模擬的局限也在這里當(dāng)N和M都達(dá)到10的6次方甚至更大時(shí)任何模擬方案都會(huì)超時(shí)。這時(shí)候就輪到數(shù)學(xué)遞推上場(chǎng)了最后的勝者編號(hào)f(N, M)滿足f(1)0f(N)(f(N-1)M)%N的遞推式時(shí)間復(fù)雜度只有O(N)。這個(gè)案例說(shuō)明了一個(gè)重要道理模擬是安全的兜底方案但不是最佳方案?？吹綌?shù)據(jù)范圍的那一刻你就該判斷是老實(shí)模擬還是尋找規(guī)律。4.2 掃雷展開(kāi)DFS/BFS還是純模擬掃雷游戲的“點(diǎn)開(kāi)空白格自動(dòng)展開(kāi)周圍區(qū)域”功能是二維矩陣模擬的經(jīng)典入門題。給你一個(gè)地雷分布圖和一個(gè)點(diǎn)擊位置要求輸出點(diǎn)開(kāi)后的局面。規(guī)則是點(diǎn)擊的位置如果是雷直接爆炸如果不是雷顯示周圍8個(gè)格子中雷的數(shù)量如果周圍沒(méi)有雷則繼續(xù)展開(kāi)周圍8個(gè)格子——這就是遞歸展開(kāi)。這里有一個(gè)很關(guān)鍵的設(shè)計(jì)決策這個(gè)遞歸展開(kāi)到底用深度優(yōu)先還是廣度優(yōu)先還是說(shuō)用一個(gè)循環(huán)隊(duì)列也能模擬先說(shuō)DFS代碼最簡(jiǎn)#include bits/stdc.h using namespace std; int n, m; vectorstring mp; vectorvectorint vis; int dx[8] {-1, -1, -1, 0, 0, 1, 1, 1}; int dy[8] {-1, 0, 1, -1, 1, -1, 0, 1}; int cntMine(int x, int y) { int cnt 0; for (int i 0; i 8; i) { int nx x dx[i], ny y dy[i]; if (nx 0 nx n ny 0 ny m mp[nx][ny] *) cnt; } return cnt; } void dfs(int x, int y) { if (vis[x][y]) return; vis[x][y] 1; int cnt cntMine(x, y); mp[x][y] char(0 cnt); if (cnt 0) { for (int i 0; i 8; i) { int nx x dx[i], ny y dy[i]; if (nx 0 nx n ny 0 ny m) { dfs(nx, ny); } } } } int main() { cin n m; mp.resize(n); for (int i 0; i n; i) cin mp[i]; vis.assign(n, vectorint(m, 0)); int x, y; cin x y; if (mp[x][y] *) { cout Boom! endl; return 0; } dfs(x, y); for (int i 0; i n; i) cout mp[i] endl; return 0; }這里值得展開(kāi)說(shuō)的地方有三個(gè)。第一個(gè)是方向數(shù)組的寫法。dx和dy數(shù)組按行排列把8個(gè)方向的偏移量預(yù)先寫死。這比在每個(gè)判斷里寫8行if要清晰得多而且不容易漏方向。我自己的習(xí)慣是把方向數(shù)組定義在全局區(qū)讓多個(gè)函數(shù)都能直接引用免得在函數(shù)之間反復(fù)傳參。第二個(gè)是邊界判定。每次計(jì)算neighbor坐標(biāo)時(shí)都要檢查nx和ny是否在有效范圍內(nèi)。這個(gè)檢查不能省否則DFS會(huì)越界。稍微懂一點(diǎn)工程經(jīng)驗(yàn)的人會(huì)寫一個(gè)isValidLambda但C競(jìng)賽代碼里直接寫if語(yǔ)句是最快的。第三個(gè)是vis數(shù)組的作用。它不是必須的因?yàn)槿绻褡右呀?jīng)被揭開(kāi)它的值不再等于原來(lái)的?或標(biāo)記字符下次展開(kāi)時(shí)其實(shí)可以靠字符狀態(tài)判斷是否訪問(wèn)過(guò)。但加上vis數(shù)組可以避免一些特殊局面下的重復(fù)遞歸也對(duì)代碼的可讀性有幫助。用上vis數(shù)組就意味著把“訪問(wèn)狀態(tài)”和“面板內(nèi)容”解耦了這在大型模擬中是很重要的設(shè)計(jì)意識(shí)——狀態(tài)本身和展示內(nèi)容經(jīng)常是兩回事。關(guān)于選擇DFS還是BFSDFS實(shí)現(xiàn)簡(jiǎn)潔但由于系統(tǒng)棧深度是有限的默認(rèn)通常在1MB到8MB之間如果棋盤特別大遞歸深度可能撐爆。BFS用queue存儲(chǔ)待擴(kuò)展節(jié)點(diǎn)不會(huì)爆棧但代碼稍微長(zhǎng)一點(diǎn)。我個(gè)人建議在遞歸深度可控的題目里貪圖DFS的簡(jiǎn)潔沒(méi)問(wèn)題一旦矩陣能到達(dá)1000x1000級(jí)別直接上BFS。4.3 文本替換與指令解析最容易被忽視的模擬分水嶺除了數(shù)組和矩陣類模擬還有一大類模擬題是“解析字符串指令”。這類題目在工程里極其常見(jiàn)——你寫一個(gè)配置文件解析器、一個(gè)簡(jiǎn)單的腳本解釋器、一個(gè)命令行工具本質(zhì)上都是逐行讀取、按規(guī)則拆分、根據(jù)指令執(zhí)行。舉個(gè)我處理過(guò)的例子實(shí)現(xiàn)一個(gè)自定義日志格式轉(zhuǎn)換器輸入若干行日志命令一部分是普通文本行一部分是變量賦值語(yǔ)句格式為“變量名變量值”還有一類是輸出指令“print 變量名或文本”。要求按順序執(zhí)行把最終輸出結(jié)果打印出來(lái)。用C實(shí)現(xiàn)第一步是選對(duì)輸入讀取方式。逐行讀取用getline不要用cin因?yàn)閏in遇到空格就會(huì)截?cái)喽鴰Э崭竦奈谋拘刑?。第二步是?duì)每一行做前綴判斷它是賦值行還是print行還是普通文本。第三步是建一個(gè)mapstring, string存儲(chǔ)變量值。#include bits/stdc.h using namespace std; int main() { int n; cin n; cin.ignore(); mapstring, string vars; string line; for (int i 0; i n; i) { getline(cin, line); if (line.rfind(print, 0) 0) { string content line.substr(6); if (!content.empty() content[0] $) { string varName content.substr(1); if (vars.count(varName)) cout vars[varName] endl; else cout undefined endl; } else { cout content endl; } } else if (line.find() ! string::npos) { int pos line.find(); string key line.substr(0, pos); string value line.substr(pos 1); vars[key] value; } } return 0; }這個(gè)例子看起來(lái)簡(jiǎn)單里面其實(shí)有一個(gè)極其經(jīng)典的坑讀取完n之后的那個(gè)換行符必須用cin.ignore()清掉否則第一次getline會(huì)直接讀到一個(gè)空行后續(xù)所有邏輯都錯(cuò)位。這種輸入緩沖區(qū)殘留問(wèn)題是模擬題里最常見(jiàn)的“本地樣例過(guò)、提交WA”的元兇之一。另一個(gè)值得養(yǎng)成習(xí)慣的地方是解析字符串時(shí)優(yōu)先用rfind判斷前綴。C20的starts_with是更優(yōu)雅的寫法但很多舊OJ不支持。rfind(name, 0)0相當(dāng)于判斷字符串是否以name開(kāi)頭這是老代碼中廣泛使用的技巧。麻煩的是如果你用find(name) 0來(lái)判斷雖然大多數(shù)情況下等價(jià)但有些實(shí)現(xiàn)會(huì)有細(xì)微行為差異穩(wěn)妥起見(jiàn)用rfind。從工程角度說(shuō)這類模擬解析器的設(shè)計(jì)模式也可以遷移到更大型的C項(xiàng)目里。比如llama.cpp的推理參數(shù)解析、各種命令行工具的flag解析底層邏輯都脫不開(kāi)“按行讀、按規(guī)則拆、分派處理”。你在刷題時(shí)形成的這種“把模糊需求拆成精確規(guī)則”的能力比記住任何具體API都值錢。5. 模擬題里最容易翻車的四個(gè)坑踩過(guò)才記得住要說(shuō)刷模擬題最大的收獲我覺(jué)得不是會(huì)寫代碼而是知道“哪些地方會(huì)莫名其妙出錯(cuò)”。下面這幾個(gè)坑幾乎每個(gè)都是我親手踩過(guò)、或者在幫別人查錯(cuò)時(shí)親眼見(jiàn)過(guò)的。5.1 輸入格式里的隱藏空格和換行符這是新手翻車率最高的一處。題目說(shuō)“每行兩個(gè)整數(shù)以一個(gè)空格隔開(kāi)”你用cin就能讀得干干凈凈。但一旦題目說(shuō)“第一行一個(gè)整數(shù)n接下來(lái)n行字符串”而字符串可能為空行或包含空格時(shí)cin和getline混用就是災(zāi)難。cin讀完n后換行符還殘留在緩沖區(qū)緊接著的getline會(huì)先把空行讀走。解決這個(gè)問(wèn)題的標(biāo)準(zhǔn)姿勢(shì)是在cin之后、getline之前加cin.ignore()或者干脆統(tǒng)一用getline讀取再用istringstream做詞法拆分。商用的做法是寫一個(gè)readInt和readLine的封裝函數(shù)把所有輸入讀取集中到一個(gè)地方這樣出錯(cuò)了只需要改一處。我在實(shí)際項(xiàng)目里寫配置解析器時(shí)也是這個(gè)思路。5.2 多組測(cè)試數(shù)據(jù)的重置時(shí)機(jī)很多OJ題目會(huì)有多組測(cè)試數(shù)據(jù)每組數(shù)據(jù)之間共享一些全局變量或靜態(tài)數(shù)組。如果你忘了在每輪開(kāi)始前重置上一輪殘留的數(shù)據(jù)就會(huì)污染下一輪。這種錯(cuò)誤最陰險(xiǎn)的地方是——第一組數(shù)據(jù)往往是對(duì)的第二組開(kāi)始出錯(cuò)而且錯(cuò)誤信息還千奇百怪。解決問(wèn)題的方案很樸素所有可變狀態(tài)都定義在循環(huán)內(nèi)部不要定義成全局。如果必須用全局明確寫一個(gè)init函數(shù)在每組數(shù)據(jù)開(kāi)始時(shí)調(diào)用?？梢园堰@個(gè)init函數(shù)寫全把該清零的全部清零包括計(jì)數(shù)器、標(biāo)記數(shù)組、容器尺寸寧可多做不要漏做。我自己還習(xí)慣在init函數(shù)末尾打一條assert確認(rèn)關(guān)鍵狀態(tài)已經(jīng)被重置這在debug階段非常有幫助。5.3 浮點(diǎn)數(shù)比較精度模擬“無(wú)窮小”的時(shí)候別直接用等于有一類模擬題會(huì)涉及浮點(diǎn)數(shù)比如模擬一個(gè)小球在重力作用下的反彈判斷某時(shí)刻是否到達(dá)某個(gè)位置。最自然的寫法是判斷當(dāng)前位置是否等于目標(biāo)位置但浮點(diǎn)數(shù)運(yùn)算的誤差會(huì)讓這個(gè)“等于”永遠(yuǎn)為假。正確做法是設(shè)置一個(gè)很小的epsilon比如1e-9凡是|a - b| eps就認(rèn)為相等。這個(gè)eps的大小也有講究設(shè)得太小誤差會(huì)被當(dāng)成不相等設(shè)得太大可能把本不該相等的兩個(gè)值合并。一個(gè)可用經(jīng)驗(yàn)是根據(jù)題目里給出的精度要求來(lái)判斷——如果保留一位小數(shù)eps取1e-6就夠了如果精確到1e-9那eps再往下取兩三個(gè)數(shù)量級(jí)。當(dāng)然更推薦的方案是盡量避開(kāi)浮點(diǎn)數(shù)。比如把等距位移的問(wèn)題轉(zhuǎn)換成整數(shù)步長(zhǎng)用“走了多少步”代替“走了多少距離”這在物理模擬題里經(jīng)常能把一個(gè)浮點(diǎn)bug變成一個(gè)整數(shù)邏輯問(wèn)題從而完全消除精度困擾。5.4 看似無(wú)關(guān)緊要的順序問(wèn)題先判斷還是先更新模擬的本質(zhì)是“按規(guī)則逐輪推進(jìn)狀態(tài)”那么每輪循環(huán)里先執(zhí)行哪一條規(guī)則、后執(zhí)行哪一條規(guī)則會(huì)對(duì)結(jié)果產(chǎn)生決定性影響。最常見(jiàn)的問(wèn)題是邊界條件應(yīng)該在一輪開(kāi)始判斷還是在一輪結(jié)束后判斷這讓我想起鍛煉里“先熱身還是先拉伸”的爭(zhēng)論。其實(shí)沒(méi)有統(tǒng)一答案完全取決于題目的定義。能做的是讀題時(shí)把“第X步之前”“執(zhí)行完Y之后”這類時(shí)間狀語(yǔ)圈出來(lái)然后嚴(yán)格按照時(shí)間線順序編碼。養(yǎng)成一個(gè)習(xí)慣在代碼注釋里把時(shí)間線寫清楚比如“// 第1步輸入預(yù)定”→“// 第2步判斷是否有人到達(dá)終點(diǎn)”→“// 第3步移動(dòng)”。這個(gè)注釋不光是給讀者看的更重要的是逼你自己把順序理清避免腦子一熱就把兩步并成一步寫了。6. 從模擬到“趕時(shí)間”時(shí)間復(fù)雜度殺手與優(yōu)化思路模擬題做到后面你一定會(huì)遇到一個(gè)瓶頸邏輯完全正確步驟完全忠實(shí)但就是超時(shí)。這時(shí)候你面對(duì)的不是“不會(huì)寫”而是“寫得太慢”。6.1 怎么判斷模擬會(huì)超時(shí)判斷的方法其實(shí)很簡(jiǎn)單前面也已經(jīng)提過(guò)把數(shù)據(jù)范圍上限代入算法復(fù)雜度對(duì)比1秒執(zhí)行10的8次方到10的9次方次基本操作的經(jīng)驗(yàn)值。需要特別提醒的是C的vector和map操作比基本for循環(huán)要慢不少所以同一個(gè)復(fù)雜度下用map的程序可能比用數(shù)組的程序慢3到5倍。這也是為什么競(jìng)賽代碼里能開(kāi)數(shù)組就開(kāi)數(shù)組實(shí)在不行才用哈希表。模擬程序還有一個(gè)特點(diǎn)它的實(shí)際運(yùn)行時(shí)間高度依賴輸入數(shù)據(jù)本身而不是只依賴數(shù)據(jù)規(guī)模。比如模擬一個(gè)隊(duì)列的進(jìn)出隊(duì)操作如果輸入數(shù)據(jù)導(dǎo)致隊(duì)列長(zhǎng)期保持很大規(guī)模那頻繁的push和pop都會(huì)比數(shù)據(jù)規(guī)模本身消耗更多時(shí)間。所以在評(píng)估“會(huì)不會(huì)超”時(shí)不要只看N有多大還要考慮模擬過(guò)程中單個(gè)狀態(tài)上的操作是否可能反復(fù)執(zhí)行很多遍。6.2 從模擬轉(zhuǎn)向規(guī)律輾轉(zhuǎn)相除法的啟示這里我想特別提一下輾轉(zhuǎn)相除法這個(gè)經(jīng)典算法。你單純按“模擬”去看它就是不斷做“大數(shù)除以小數(shù)余數(shù)替換大數(shù)”這個(gè)反復(fù)操作。如果M和N都很大一步一步模擬運(yùn)算次數(shù)其實(shí)也不小。但歐幾里得發(fā)現(xiàn)這個(gè)過(guò)程有嚴(yán)格的對(duì)數(shù)復(fù)雜度——因?yàn)槊看纬ê笥鄶?shù)至少減小一半。這就是“找到了過(guò)程中的規(guī)律從而把模擬優(yōu)化成公式”的極致例子。很多看上去需要模擬的題目當(dāng)你把模擬過(guò)程列出來(lái)盯著每一步的狀態(tài)轉(zhuǎn)移看了半小時(shí)后可能會(huì)發(fā)現(xiàn)某個(gè)量是單調(diào)的、循環(huán)的、或者能用前綴和預(yù)計(jì)算的。這個(gè)時(shí)候你走的已經(jīng)不是模擬的路線而是把模擬當(dāng)作觀察平臺(tái)找到更高級(jí)的優(yōu)化思路。這也是我特別建議模擬題做的原因它逼你先完整理解過(guò)程再動(dòng)手優(yōu)化而不是一上來(lái)就套模板。6.3 常見(jiàn)優(yōu)化技術(shù)清單這里列一個(gè)我在實(shí)際寫代碼時(shí)會(huì)過(guò)的清單按使用頻率從高到低排列下標(biāo)映射把對(duì)象編號(hào)從0開(kāi)始而不是從1開(kāi)始能夠少處理很多邊界也方便取模運(yùn)算。方向數(shù)組處理網(wǎng)格移動(dòng)時(shí)用dx/dy數(shù)組代替一堆if代碼更短bug更少。狀態(tài)壓縮當(dāng)狀態(tài)只有“是/否”兩種可能時(shí)用bitset代替bool數(shù)組或者用整型的位運(yùn)算來(lái)代表多個(gè)開(kāi)關(guān)可以大幅減少內(nèi)存和拷貝時(shí)間。事件驅(qū)動(dòng)模擬系統(tǒng)的推進(jìn)不一定按固定時(shí)間步長(zhǎng)。如果兩次“事件”之間沒(méi)有任何變化可以直接跳躍到下一個(gè)事件發(fā)生點(diǎn)。這在離散事件模擬如進(jìn)程調(diào)度里特別有用。記憶化如果模擬過(guò)程中反復(fù)計(jì)算某個(gè)子狀態(tài)的結(jié)果用一個(gè)表存起來(lái)第二次直接用——本質(zhì)上就是從模擬過(guò)渡到動(dòng)態(tài)規(guī)劃。6.4 工程實(shí)戰(zhàn)里的模擬單例模式和llama.cpp的啟示最后想聯(lián)系熱詞里提到的兩個(gè)方向。一個(gè)是C的單例類很多人覺(jué)得單例只是個(gè)設(shè)計(jì)模式跟模擬無(wú)關(guān)。但你在多線程環(huán)境下測(cè)試單例的線程安全性很難靠“看代碼”得出結(jié)論通常要寫一個(gè)模擬程序創(chuàng)建大量線程同時(shí)獲取實(shí)例觀察是否會(huì)出現(xiàn)重復(fù)構(gòu)造或者異常狀態(tài)。這個(gè)模擬過(guò)程本身就是在驗(yàn)證系統(tǒng)行為和我們前面說(shuō)的系統(tǒng)模擬如出一轍。另一個(gè)是llama.cpp。我最近在看llama.cpp的源碼時(shí)注意到它雖然是一個(gè)推理引擎但在CPU offload到內(nèi)存的時(shí)候做了大量“模擬內(nèi)存布局”的工作——預(yù)估每層張量的大小、排布方式、對(duì)齊要求然后整塊分配。這種操作其實(shí)就是在模擬一個(gè)內(nèi)存分配過(guò)程。如果你能熟練在競(jìng)賽題里做“模擬內(nèi)存池分配”之類的題目理解llama.cpp的這類代碼會(huì)輕松很多。所以說(shuō)模擬算法的適用范圍早已不局限于OJ它可以滲透到任何需要“通過(guò)代碼復(fù)現(xiàn)過(guò)程”的場(chǎng)景。再?gòu)?fù)雜的框架再精妙的設(shè)計(jì)模式抽絲剝繭之后底層往往都有一段樸素的模擬邏輯在支撐。把模擬基本功打好等于給自己裝上了一雙能看清各種復(fù)雜系統(tǒng)的眼睛。我自己這些年在寫模擬類程序時(shí)最深的體會(huì)是寧可多花十分鐘把題目中的每一步規(guī)則、每一個(gè)邊界條件理清楚也不要在代碼寫到一半的時(shí)候返工。模擬算法的代碼量未必大但它對(duì)邏輯嚴(yán)謹(jǐn)性的要求在全算法領(lǐng)域都是數(shù)一數(shù)二的。多數(shù)WA和TLE根源都不在“算法沒(méi)學(xué)夠”而在于“規(guī)則沒(méi)看清、狀態(tài)沒(méi)設(shè)好、復(fù)雜度沒(méi)算準(zhǔn)”。希望這篇梳理能讓你在下一道模擬題面前少走一些我當(dāng)年走過(guò)的彎路。