很多同學(xué)剛接觸算法競(jìng)賽時(shí)第一反應(yīng)是去啃各種“高大上”的算法——圖論、動(dòng)態(tài)規(guī)劃、網(wǎng)絡(luò)流、字符串匹配。但真正讓我意識(shí)到“地基”重要性的是一次比賽中因?yàn)閿?shù)組開(kāi)小導(dǎo)致半小時(shí)調(diào)不出錯(cuò)誤、最后發(fā)現(xiàn)是邊界問(wèn)題的慘痛教訓(xùn)。數(shù)組這個(gè)最基礎(chǔ)、最不起眼的數(shù)據(jù)結(jié)構(gòu)恰恰是算法競(jìng)賽里幾乎所有解法的落腳點(diǎn)。你寫(xiě)的每一份代碼本質(zhì)上都在操作數(shù)組狀態(tài)轉(zhuǎn)移存數(shù)組、鄰接表存數(shù)組、哈希沖突解決也依賴(lài)數(shù)組。可以說(shuō)搞懂了數(shù)組你就搞懂了算法競(jìng)賽的一大半。這篇文章我想從數(shù)組的內(nèi)存本質(zhì)講起把它在枚舉、雙指針、前綴和、樹(shù)狀數(shù)組、矩陣處理、動(dòng)態(tài)規(guī)劃優(yōu)化這些高頻場(chǎng)景里的用法拆開(kāi)聊一遍順帶把那些比賽中經(jīng)常踩的坑也一并交代清楚。不管你是剛?cè)腴T(mén)的選手還是藍(lán)橋杯、ICPC、CCPC備考中的進(jìn)階黨這篇文章都適合拿來(lái)當(dāng)作一份“數(shù)組使用手冊(cè)”反復(fù)翻。1. 數(shù)組為什么是算法競(jìng)賽的“地基”從內(nèi)存模型說(shuō)起要理解數(shù)組在競(jìng)賽中的分量先得想明白一個(gè)問(wèn)題為什么幾乎所有的算法題解里最終都是“開(kāi)一個(gè)數(shù)組”來(lái)解決問(wèn)題答案不在于數(shù)組本身有多復(fù)雜而在于它背后那段連續(xù)的、固定大小的內(nèi)存。1.1 連續(xù)內(nèi)存帶來(lái)的O(1)隨機(jī)訪問(wèn)數(shù)組最核心的性質(zhì)是下標(biāo)尋址。C/C里a[i]本質(zhì)上就是*(a i * sizeof(T))Java里雖然多了一層對(duì)象包裝但底層依然是一段連續(xù)空間Python的list也是動(dòng)態(tài)數(shù)組訪問(wèn)依然是O(1)。這意味著什么意味著你可以用下標(biāo)在瞬間定位到任意一個(gè)位置不需要像鏈表那樣從頭遍歷。這個(gè)性質(zhì)在算法競(jìng)賽里被用到了極致。比如二分查找、快速排序、堆排序它們?nèi)家蕾?lài)于數(shù)組的隨機(jī)訪問(wèn)能力。你想象一下如果每次查中間元素都要O(n)地走過(guò)去那二分操作一次就是O(n)整個(gè)算法就退化成了笑話。數(shù)組的連續(xù)內(nèi)存還帶來(lái)一個(gè)額外的紅利緩存友好。現(xiàn)代CPU加載數(shù)據(jù)時(shí)按緩存行一次加載64字節(jié)數(shù)組的連續(xù)存儲(chǔ)能把相鄰元素一起拉進(jìn)緩存遍歷時(shí)極少缺頁(yè)。而鏈表節(jié)點(diǎn)散落在內(nèi)存各處每次訪問(wèn)都大概率觸發(fā)緩存未命中。所以同樣是O(n)的遍歷數(shù)組往往比鏈表快好幾倍。競(jìng)賽里數(shù)據(jù)規(guī)模一大這種常數(shù)級(jí)別的差距就足以決定你是AC還是TLE。1.2 空間換時(shí)間的底層邏輯哈希與布爾的“偽哈?！睌?shù)組另一個(gè)被低估的能力是拿空間換時(shí)間。最經(jīng)典的就是“布爾數(shù)組當(dāng)哈希表用”——開(kāi)一個(gè)bool vis[MAXN]如果值x出現(xiàn)過(guò)就標(biāo)記vis[x] true查詢(xún)時(shí)直接O(1)判斷。這比任何哈希表都省常數(shù)因?yàn)檫B哈希函數(shù)都不用算。我當(dāng)年在藍(lán)橋杯做一道題需要判斷兩個(gè)序列是否同構(gòu)第一反應(yīng)是搞個(gè)map后來(lái)發(fā)現(xiàn)數(shù)據(jù)范圍只有10^5直接開(kāi)一個(gè)int idMap[100005]用數(shù)組的下標(biāo)做鍵瞬間O(1)映射代碼短了一半不止。同樣的思路也出現(xiàn)在字符串處理里。比如判斷字母是否出現(xiàn)開(kāi)一個(gè)int count[26]用字符減去a得到下標(biāo)一行代碼搞定統(tǒng)計(jì)。這簡(jiǎn)直是競(jìng)賽里的“萬(wàn)金油”操作從統(tǒng)計(jì)詞頻、判斷字母異位詞到滑動(dòng)窗口的窗口字符計(jì)數(shù)全都在用這個(gè)套路。提示數(shù)組哈希的硬限制是值域必須可控。如果數(shù)據(jù)范圍是10^9甚至更大開(kāi)數(shù)組就不現(xiàn)實(shí)那時(shí)候才輪到std::unordered_map出場(chǎng)。所以比賽中拿到題目先看數(shù)據(jù)范圍這一步往往決定了你要不要開(kāi)大數(shù)組。2. 競(jìng)賽中最常見(jiàn)的數(shù)組應(yīng)用范式從暴力到優(yōu)雅數(shù)組本身不產(chǎn)生算法但它幾乎是每個(gè)基礎(chǔ)算法的“容器”。這里我把競(jìng)賽中出現(xiàn)頻率最高、最實(shí)用的幾類(lèi)數(shù)組用法串一遍你會(huì)發(fā)現(xiàn)很多看起來(lái)“高級(jí)”的算法拆到底層都是數(shù)組操作的組合。2.1 暴力枚舉與剪枝數(shù)組最直接的用法暴力枚舉是競(jìng)賽中最樸素也最不能被忽視的方法。完全枚舉的思想很簡(jiǎn)單把所有的可能都試一遍看哪個(gè)滿(mǎn)足條件。配合數(shù)組枚舉就變得非常直接——用多重循環(huán)遍歷數(shù)組組合再用一個(gè)結(jié)果數(shù)組收集合法答案。但純暴力往往過(guò)不了大數(shù)據(jù)真正厲害的是在枚舉過(guò)程中加入剪枝。剪枝的本質(zhì)是“提前判斷這條路肯定走不通所以不再往下走”。判斷的依據(jù)是什么就是你當(dāng)前狀態(tài)在數(shù)組里反映出來(lái)的信息。舉個(gè)例子有一類(lèi)“N皇后”問(wèn)題你要在N×N棋盤(pán)上放N個(gè)皇后。最暴力的方法是C(N2, N)種組合規(guī)模稍微一大就爆炸。但如果我們用一維數(shù)組col[10]記錄每一列是否已放皇后再配合兩個(gè)對(duì)角線數(shù)組diag1[20]、diag2[20]用行列和行-列做下標(biāo)每放一個(gè)皇后就O(1)檢查位置是否沖突不沖突才繼續(xù)遞歸。這就是用數(shù)組實(shí)現(xiàn)了剪枝條件復(fù)雜度從組合爆炸降到了指數(shù)級(jí)但可接受的范圍。再比如子集枚舉。給定一個(gè)數(shù)組要求所有子集的和。你可以用二進(jìn)制位枚舉把狀態(tài)壓成一個(gè)整數(shù)每一位表示“選/不選”然后對(duì)每個(gè)狀態(tài)用一個(gè)循環(huán)累加對(duì)應(yīng)下標(biāo)的元素。這種寫(xiě)法把數(shù)組下標(biāo)和位運(yùn)算結(jié)合起來(lái)是最樸素的“狀態(tài)壓縮”思想。2.2 雙指針與滑動(dòng)窗口讓數(shù)組遍歷從O(n2)降到O(n)如果說(shuō)暴力枚舉是數(shù)組用法的基礎(chǔ)版那雙指針就是數(shù)組用法的進(jìn)階版。雙指針的核心在于利用數(shù)組下標(biāo)單調(diào)性避免無(wú)效的重復(fù)掃描。最常見(jiàn)的場(chǎng)景是“有序數(shù)組兩數(shù)之和”。給定一個(gè)升序數(shù)組找出兩個(gè)數(shù)使和為target。暴力是兩層循環(huán)O(n2)但用雙指針一個(gè)指頭一個(gè)指尾根據(jù)當(dāng)前和與target的關(guān)系決定哪邊移動(dòng)一趟就能掃完降到O(n)?；瑒?dòng)窗口是雙指針的一種變體常用于子數(shù)組/子串問(wèn)題。比如“最長(zhǎng)無(wú)重復(fù)字符子串”你需要維護(hù)窗口的左右邊界用數(shù)組lastPos[128]記錄每個(gè)字符上一次出現(xiàn)的位置。右指針每擴(kuò)展一格就查數(shù)組更新左指針位置同時(shí)更新答案。整個(gè)過(guò)程每個(gè)元素只進(jìn)出窗口一次復(fù)雜度O(n)。這里有一個(gè)關(guān)鍵心得滑動(dòng)窗口能用的前提是窗口的約束條件具有單調(diào)性——窗口變大時(shí)滿(mǎn)足性可能被破壞窗口變小時(shí)滿(mǎn)足性只會(huì)更容易。如果你發(fā)現(xiàn)題目要求“子數(shù)組滿(mǎn)足某種性質(zhì)”先想想把右指針往右移、左指針往右移時(shí)這個(gè)性質(zhì)的變化是不是單調(diào)的。如果是那大概率就能用滑動(dòng)窗口。2.3 前綴和與差分靜態(tài)區(qū)間查詢(xún)的高效解法前綴和是數(shù)組上最經(jīng)典的空間換時(shí)間操作。一維前綴和數(shù)組pre[i]表示原數(shù)組前i個(gè)元素的和預(yù)處理O(n)查詢(xún)?nèi)我鈪^(qū)間[l, r]的和只需要pre[r] - pre[l-1]O(1)搞定。如果你需要頻繁查詢(xún)區(qū)間和、區(qū)間平均值、區(qū)間乘積取模前綴和幾乎是必選方案。擴(kuò)展到二維二維前綴和sum[i][j]表示以(1,1)為左上角、(i,j)為右下角的矩形區(qū)域總和查詢(xún)?nèi)我饩匦螀^(qū)域的和就用容斥原理四個(gè)格子算一下。這個(gè)在矩陣類(lèi)題目中極其常用比如“求矩陣中所有和為K的子矩陣數(shù)量”先做二維前綴和再枚舉上下邊界配合哈希存中間結(jié)果能把暴力O(n?)優(yōu)化到O(n3)。差分?jǐn)?shù)組則是前綴和的“逆運(yùn)算”。相鄰兩個(gè)原數(shù)組元素相減得到差分?jǐn)?shù)組diff[i] a[i] - a[i-1]區(qū)間[l, r]加上一個(gè)值v時(shí)只需要diff[l] v、diff[r1] - v最后前綴和還原原數(shù)組。這個(gè)技巧在“區(qū)間更新、最后統(tǒng)一查詢(xún)”的題目里堪稱(chēng)神器。比如你有10^5次操作每次給一個(gè)區(qū)間的所有元素加一個(gè)數(shù)最后問(wèn)每個(gè)元素的值。直接模擬是O(nm)用差分?jǐn)?shù)組就是O(nm)。3. 數(shù)組作為高級(jí)數(shù)據(jù)結(jié)構(gòu)的載體樹(shù)狀數(shù)組與單調(diào)結(jié)構(gòu)數(shù)組不僅能直接解決問(wèn)題還能作為更高級(jí)數(shù)據(jù)結(jié)構(gòu)的“肉身”。很多看起來(lái)很玄乎的結(jié)構(gòu)拆開(kāi)一看都是建立在數(shù)組之上。3.1 樹(shù)狀數(shù)組用普通數(shù)組實(shí)現(xiàn)的快速動(dòng)態(tài)前綴和樹(shù)狀數(shù)組Fenwick Tree是我最喜歡的數(shù)據(jù)結(jié)構(gòu)之一因?yàn)樗榷逃謴?qiáng)。你需要維護(hù)一個(gè)數(shù)組支持兩種操作單點(diǎn)修改、前綴和查詢(xún)而且都要求O(log n)。樹(shù)狀數(shù)組的做法是用一個(gè)tree[]數(shù)組存“分塊和”修改和查詢(xún)時(shí)通過(guò)i i (-i)這種位運(yùn)算更新下標(biāo)。為什么它能做到O(log n)因?yàn)閠ree[i]維護(hù)的是原數(shù)組中(i - lowbit(i), i]這段區(qū)間的和查詢(xún)前綴和時(shí)把若干個(gè)二進(jìn)制段拼起來(lái)。樹(shù)狀數(shù)組的代碼不過(guò)十幾行但在競(jìng)賽里用處極廣逆序?qū)τ?jì)數(shù)、動(dòng)態(tài)區(qū)間第K大、二維樹(shù)狀數(shù)組處理矩陣動(dòng)態(tài)修改查詢(xún)……它都能勝任。注意樹(shù)狀數(shù)組下標(biāo)必須從1開(kāi)始。如果你習(xí)慣0基數(shù)組要么在構(gòu)建時(shí)整體1偏移要么使用i (i (-i))時(shí)確保不會(huì)出現(xiàn)0死循環(huán)。這個(gè)0基/1基的坑我在初學(xué)時(shí)吃過(guò)不少虧。3.2 單調(diào)棧與單調(diào)隊(duì)列數(shù)組下標(biāo)即棧/隊(duì)列指針單調(diào)棧和單調(diào)隊(duì)列聽(tīng)起來(lái)像是“數(shù)據(jù)結(jié)構(gòu)”但在競(jìng)賽實(shí)現(xiàn)里它們大部分時(shí)候就是用數(shù)組模擬的。為什么不用std::stack因?yàn)槟阈枰焖侔聪聵?biāo)訪問(wèn)棧內(nèi)元素而且很多題需要把棧內(nèi)元素的下標(biāo)記錄下來(lái)作為答案的一部分手寫(xiě)數(shù)組棧更靈活。單調(diào)棧最典型的應(yīng)用是“尋找下一個(gè)更大元素”——給一個(gè)數(shù)組對(duì)每個(gè)位置找右邊第一個(gè)比它大的元素。做法是從右往左掃維護(hù)一個(gè)單調(diào)遞減的棧棧里存的是數(shù)組下標(biāo)。當(dāng)前元素入棧前把所有比它小的元素彈出彈出的過(guò)程其實(shí)就是在回答“誰(shuí)是這些元素的下一個(gè)更大元素”——就是當(dāng)前元素。答案可以放在一個(gè)ans[]數(shù)組里根據(jù)彈出的下標(biāo)回填。整個(gè)過(guò)程O(píng)(n)比暴力O(n2)快了不止一個(gè)量級(jí)。單調(diào)隊(duì)列則常用于滑動(dòng)窗口最值問(wèn)題。經(jīng)典題“滑動(dòng)窗口最大值”要求每個(gè)窗口內(nèi)快速取最大值。用deque當(dāng)然可以但競(jìng)賽選手更習(xí)慣直接用數(shù)組q[]當(dāng)雙端隊(duì)列頭指針head、尾指針tail維護(hù)一個(gè)窗口內(nèi)元素下標(biāo)的單調(diào)隊(duì)列。每個(gè)元素最多進(jìn)隊(duì)出隊(duì)一次總復(fù)雜度O(n)。這個(gè)能力在處理大量線掃描題時(shí)簡(jiǎn)直好用。3.3 并查集與圖遍歷數(shù)組就是鄰接表的基本形態(tài)并查集本質(zhì)上就是兩個(gè)數(shù)組parent[]記錄每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)rank[]或size[]記錄樹(shù)的高度/大小。路徑壓縮是在查詢(xún)時(shí)把沿途節(jié)點(diǎn)的父節(jié)點(diǎn)直接指向根按秩合并是把小樹(shù)掛到大樹(shù)上。這些操作全部是數(shù)組賦值和比較。并查集看起來(lái)簡(jiǎn)單但處理連通性、最小生成樹(shù)的Kruskal算法、甚至離線查詢(xún)帶權(quán)并查集、可撤銷(xiāo)并查集全都離不開(kāi)它。圖的存儲(chǔ)也大量依賴(lài)數(shù)組。鄰接表在競(jìng)賽里最常見(jiàn)的實(shí)現(xiàn)不是vectorvectorint而是“鏈?zhǔn)角跋蛐恰薄胔ead[]記錄每個(gè)點(diǎn)的首條邊下標(biāo)用edge[]數(shù)組存所有邊每條邊帶to、weight、next三個(gè)字段。這種存儲(chǔ)方式不僅省內(nèi)存而且遍歷一個(gè)點(diǎn)的所有鄰邊時(shí)只需一個(gè)for循環(huán)順著next往下找在深度優(yōu)先遍歷和廣度優(yōu)先遍歷時(shí)性能極佳。4. 多維數(shù)組與矩陣問(wèn)題的實(shí)戰(zhàn)套路競(jìng)賽里有一大類(lèi)題目直接和二維數(shù)組杠上矩陣旋轉(zhuǎn)、迷宮尋路、島嶼數(shù)量、掃雷游戲、生命游戲……這類(lèi)題的特點(diǎn)是邏輯本身不復(fù)雜但邊界處理、方向控制、狀態(tài)記錄非?？简?yàn)對(duì)數(shù)組的掌控力。我把它們單獨(dú)拎出來(lái)講是因?yàn)檫@里的套路非常固定掌握之后可以直接套用。4.1 二維數(shù)組的遍歷與邊界處理二維數(shù)組的遍歷本質(zhì)仍然是下標(biāo)運(yùn)算但坑在于邊界。假設(shè)矩陣是m行n列合法的下標(biāo)范圍是0 i m、0 j n。幾乎所有矩陣題都會(huì)用到“四方向”或“八方向”遍歷這時(shí)候預(yù)先定義方向數(shù)組是省事又安全的方法int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1}; for (int d 0; d 4; d) { int nx x dx[d]; int ny y dy[d]; if (nx 0 || nx m || ny 0 || ny n) continue; // 越界判斷 // 繼續(xù)處理 }這樣的好處是代碼統(tǒng)一改方向個(gè)數(shù)時(shí)只需改數(shù)組和循環(huán)次數(shù)。我見(jiàn)過(guò)很多新手寫(xiě)四個(gè)if判斷方向又長(zhǎng)又容易漏尤其八方向時(shí)更崩潰。4.2 矩陣旋轉(zhuǎn)、翻轉(zhuǎn)與原地操作的核心技巧矩陣旋轉(zhuǎn)90度這類(lèi)題最直觀的想法是開(kāi)一個(gè)新二維數(shù)組把原[i][j]賦值到新位置。但很多題目要求原地旋轉(zhuǎn)這時(shí)候可以用“兩次翻轉(zhuǎn)代替旋轉(zhuǎn)”的技巧先水平翻轉(zhuǎn)上下對(duì)稱(chēng)交換行再沿主對(duì)角線翻轉(zhuǎn)轉(zhuǎn)置兩步組合就能實(shí)現(xiàn)順時(shí)針旋轉(zhuǎn)90度。這個(gè)技巧避免復(fù)雜的四次循環(huán)坐標(biāo)映射代碼極短、不易出錯(cuò)。如果你真想直接推導(dǎo)坐標(biāo)映射記住順時(shí)針旋轉(zhuǎn)90度后原matrix[i][j]會(huì)到新位置matrix[j][n-1-i]。這組公式在題解里經(jīng)常出現(xiàn)但推導(dǎo)不如“兩次翻轉(zhuǎn)”直觀。我自己傾向于用翻轉(zhuǎn)法尤其是矩陣不是正方形時(shí)翻轉(zhuǎn)法依然通用。4.3 網(wǎng)格類(lèi)搜索問(wèn)題Flood Fill與狀態(tài)記錄“島嶼數(shù)量”這類(lèi)問(wèn)題要求你遍歷網(wǎng)格中相連的陸地。經(jīng)典做法是DFS或BFS但無(wú)論哪種都需要一個(gè)visited數(shù)組標(biāo)記每個(gè)格子是否訪問(wèn)過(guò)。這里有個(gè)空間優(yōu)化技巧如果允許修改原數(shù)組可以直接把訪問(wèn)過(guò)的1改成0省掉visited數(shù)組。但要注意這要求題目不關(guān)心原始數(shù)據(jù)的保留。如果后續(xù)還要用原矩陣就不能這么干。DFS在網(wǎng)格上的實(shí)現(xiàn)要小心遞歸棧深度。一個(gè)1000×1000的網(wǎng)格全是陸地遞歸深度可能達(dá)到10^6級(jí)別直接棧溢出。所以網(wǎng)格規(guī)模較大時(shí)優(yōu)先用顯式隊(duì)列的BFS或者用自己維護(hù)的棧進(jìn)行迭代DFS不要裸遞歸。5. 數(shù)組與字符串、動(dòng)態(tài)規(guī)劃的深度結(jié)合數(shù)組和字符串、動(dòng)態(tài)規(guī)劃的結(jié)合是競(jìng)賽進(jìn)階的必經(jīng)之路。很多看起來(lái)完全不相干的算法內(nèi)里都是數(shù)組在支撐。5.1 KMP的next數(shù)組字符串匹配中的數(shù)組思想KMP算法是字符串匹配的經(jīng)典算法核心是next[]數(shù)組——它記錄了模式串每個(gè)位置的最長(zhǎng)相等前后綴長(zhǎng)度。當(dāng)匹配失敗時(shí)不是從頭開(kāi)始重新匹配而是根據(jù)next[]把模式串向右滑動(dòng)到合適位置。這個(gè)過(guò)程本質(zhì)上是利用數(shù)組預(yù)先計(jì)算的信息避免重復(fù)掃描。初學(xué)KMP時(shí)最容易犯的錯(cuò)是next數(shù)組的求法搞混。直接模式串自己做匹配求next很容易漏掉邊界條件。我的建議是先背下求next的模板理解了“j是當(dāng)前已匹配前綴長(zhǎng)度”這個(gè)含義后再試著推導(dǎo)幾遍。別急著理解所有細(xì)節(jié)先會(huì)用多寫(xiě)幾道匹配題回頭再看原理就順了。5.2 滾動(dòng)數(shù)組將O(n2)空間壓到O(n)的關(guān)鍵技術(shù)動(dòng)態(tài)規(guī)劃里如果狀態(tài)轉(zhuǎn)移只依賴(lài)前一行或前一列完全沒(méi)必要開(kāi)二維數(shù)組。滾動(dòng)數(shù)組的思路是用一維數(shù)組不斷覆蓋舊值或者用兩個(gè)一維數(shù)組交替使用把空間復(fù)雜度從O(n2)降到O(n)。競(jìng)賽里空間限制有時(shí)很緊張滾動(dòng)數(shù)組往往能救你一命。但滾動(dòng)數(shù)組有個(gè)風(fēng)險(xiǎn)覆蓋順序搞錯(cuò)會(huì)污染狀態(tài)。比如0/1背包問(wèn)題內(nèi)層循環(huán)必須從大到小枚舉容量因?yàn)閐p[i][c]依賴(lài)的是dp[i-1][c-w]如果從小到大更新dp[c-w]可能已經(jīng)是“本次物品已放入”的狀態(tài)了。這個(gè)方向問(wèn)題只有親自推過(guò)一遍才會(huì)真正記住我建議你在草稿紙上畫(huà)一個(gè)二維表格標(biāo)出每個(gè)格子依賴(lài)哪些格子再?zèng)Q定循環(huán)方向。5.3 記憶化搜索狀態(tài)數(shù)組的設(shè)計(jì)思路記憶化搜索適合那種狀態(tài)多、轉(zhuǎn)移復(fù)雜的遞歸問(wèn)題。做法是開(kāi)一個(gè)數(shù)組dp[state]記錄某個(gè)狀態(tài)的結(jié)果遞歸時(shí)先查表算完再寫(xiě)表避免重復(fù)子問(wèn)題。這其實(shí)就是“自頂向下的動(dòng)態(tài)規(guī)劃”。狀態(tài)數(shù)組的設(shè)計(jì)是整個(gè)解法的靈魂。比如“走迷宮最短路徑”可以用dist[x][y]記錄從起點(diǎn)到(x,y)的最短距離數(shù)位DP則需要dp[pos][state]配合limit標(biāo)記狀壓DP則用dp[mask]記錄每個(gè)子集狀態(tài)的最優(yōu)值。設(shè)計(jì)狀態(tài)數(shù)組時(shí)問(wèn)自己三個(gè)問(wèn)題這個(gè)狀態(tài)需要哪些維度每個(gè)維度的取值范圍多大狀態(tài)之間怎么轉(zhuǎn)移把這三個(gè)問(wèn)題想清楚了DP題就成功了一大半。6. 競(jìng)賽中數(shù)組使用的高頻坑位與選型建議數(shù)組雖簡(jiǎn)單競(jìng)賽里因數(shù)組出問(wèn)題的案例卻數(shù)不勝數(shù)。我把高頻坑位總結(jié)成清單每條都是我用WA和RE換來(lái)的教訓(xùn)。6.1 數(shù)組越界和初始化80%的RE與WA來(lái)源越界訪問(wèn)是最隱蔽的錯(cuò)誤之一。C/C不檢查數(shù)組邊界越界讀可能返回垃圾值越界寫(xiě)則可能破壞其他變量甚至直接段錯(cuò)誤。比賽中遇到“本地正常、提交RE”的情況優(yōu)先懷疑數(shù)組越界。初始化的坑更多。全局變量默認(rèn)零初始化但局部數(shù)組不初始化就是垃圾值。很多選手寫(xiě)int cnt[100005];在函數(shù)內(nèi)部忘了清空后果是數(shù)據(jù)互相污染。我的習(xí)慣是所有數(shù)組能開(kāi)全局就開(kāi)全局一是自動(dòng)清零二是避免棧溢出如果必須在局部用立刻memset(cnt, 0, sizeof(cnt))清一次。還有兩個(gè)常見(jiàn)邊界錯(cuò)誤循環(huán)里用還是直接決定是否越界差分?jǐn)?shù)組在r1處做減法時(shí)如果r1等于數(shù)組長(zhǎng)度要保證數(shù)組多開(kāi)一位。6.2 時(shí)間與空間復(fù)雜度競(jìng)賽中如何估計(jì)數(shù)組大小在競(jìng)賽里開(kāi)數(shù)組前先算算最壞情況需要多大空間。拿int類(lèi)型舉例1個(gè)int占4字節(jié)數(shù)組大小為10^6 ≈ 4MB。如果題目?jī)?nèi)存限制256MB理論上能開(kāi)約6×10^7個(gè)int。但實(shí)際比賽中除了數(shù)組還要留出調(diào)用棧、臨時(shí)變量、STL容器的空間所以安全系數(shù)建議留一半以上。還有一個(gè)經(jīng)驗(yàn)看到n 10^5二維數(shù)組就要小心了——10^10個(gè)int需要40GB肯定爆內(nèi)存這時(shí)候要么換算法要么用一維數(shù)組手動(dòng)模擬二維索引。6.3 不同語(yǔ)言中數(shù)組的差異與選型思路競(jìng)賽里用得最多的是C數(shù)組性能最好但需要手動(dòng)管理內(nèi)存和邊界。Java的數(shù)組是對(duì)象操作簡(jiǎn)便但內(nèi)存開(kāi)銷(xiāo)大一些并且Arrays.sort對(duì)基本類(lèi)型數(shù)組用快排、對(duì)對(duì)象數(shù)組用歸并排序時(shí)要留意。Python的list是動(dòng)態(tài)數(shù)組配合切片操作非常爽但常數(shù)較大純算法題沖極限數(shù)據(jù)時(shí)比較吃力有時(shí)需要改用array模塊或直接用bytearray。我個(gè)人的選型建議是追求極致性能時(shí)用C并且多用STL提供的vector、array、string本質(zhì)也是動(dòng)態(tài)數(shù)組來(lái)減少手寫(xiě)錯(cuò)誤開(kāi)發(fā)效率優(yōu)先時(shí)用Python刷題但要有心理準(zhǔn)備——同樣的O(n log n)算法Python在10^6這個(gè)量級(jí)就可能逼近時(shí)間上限。盡量不要混用語(yǔ)言競(jìng)賽現(xiàn)場(chǎng)切換語(yǔ)言的成本遠(yuǎn)比你想象的高。數(shù)組這個(gè)結(jié)構(gòu)說(shuō)它簡(jiǎn)單它確實(shí)沒(méi)有復(fù)雜的指針變換和遞歸結(jié)構(gòu)說(shuō)它難它能變化出前綴和、差分、樹(shù)狀數(shù)組、單調(diào)隊(duì)列、滾動(dòng)數(shù)組這樣一大串進(jìn)階玩法。我見(jiàn)過(guò)太多同學(xué)一開(kāi)始就盯著“高級(jí)算法”學(xué)等做題時(shí)才發(fā)現(xiàn)自己連數(shù)組都處理不好——邊界錯(cuò)了、空間爆了、初始化沒(méi)清。與其追求套路多不如先把數(shù)組這一層打扎實(shí)。你越往后學(xué)越會(huì)發(fā)現(xiàn)每一個(gè)精巧的算法背后站著的都是這個(gè)最樸素的“地基”。