簡介這份《個人整理ACM模板》PDF是面向ACM國際大學(xué)生程序設(shè)計競賽選手及算法學(xué)習(xí)者的實用模板合集收錄了競賽中高頻使用的數(shù)據(jù)結(jié)構(gòu)、數(shù)學(xué)工具與基礎(chǔ)算法旨在幫助讀者快速調(diào)用現(xiàn)成代碼、縮短編碼時間尤其適合備賽期沖刺或日常刷題時參考。壓縮包內(nèi)僅含1個PDF文件整體約2.14MB便于離線查閱和打印。當(dāng)前已有301人學(xué)習(xí)瀏覽實用性得到了初步驗證。內(nèi)容涵蓋常用頭文件組織方式、埃拉托斯特尼篩法、快速冪、大數(shù)加法與階乘模擬、輾轉(zhuǎn)相除法求最大公約數(shù)和最小公倍數(shù)等經(jīng)典實現(xiàn)每段代碼輔以簡潔注釋與思路說明既可作為比賽時的“代碼字典”也能作為復(fù)習(xí)數(shù)據(jù)結(jié)構(gòu)和數(shù)論模板的提綱。對于希望在有限時間內(nèi)快速定位算法模板、減少重復(fù)造輪子的參賽者來說這份整理周密的PDF能顯著提升解題效率。 如果你已經(jīng)決定要認(rèn)真打幾場算法競賽那整理一份屬于自己的 ACM 模板大概率會在某個晚上突然變成一件很緊急的事。我見過不少同學(xué)賽前兩三天才開始到處搜模板最后打印出一份幾百頁的 PDF翻目錄都翻不到 KMP 在哪一頁也有人把自己的模板整理成了“個人整理ACM模板.pdf”給自己的比賽生涯省下了大量現(xiàn)場寫板子的時間。這篇文章不打算直接丟給你一份現(xiàn)成模板而是把我自己整理 ACM 模板并沉淀成 PDF 的全過程拆開講清楚模塊怎么規(guī)劃、代碼注釋怎么寫、怎么穩(wěn)定地從 Markdown 導(dǎo)出一份排版舒服的中文 PDF以及這一路上踩過的坑。適合準(zhǔn)備區(qū)域賽、校賽或者單純想把算法體系系統(tǒng)化過一遍的同學(xué)參考。1. 為什么我也勸你把手里的算法模板收進(jìn)一個 PDF1.1 紙質(zhì)模板在賽場上依然是最可靠的“外掛”ACM 比賽有個鐵規(guī)矩不能聯(lián)網(wǎng)不能帶自己的代碼文件機(jī)器環(huán)境也是主辦方統(tǒng)一配好的。這意味著你平時順手就能查的 OI Wiki、GitHub、題解博客在賽場上一律歸零。能帶進(jìn)賽場的除了隊友的腦子就是打印出來的紙質(zhì)資料。有人覺得現(xiàn)在不少比賽允許帶電子版這我沒法反駁但你可以先想想這幾個場景機(jī)器上的 IDE 打開一個 5MB 的 PDF 要卡三秒屏幕亮度低 調(diào)代碼調(diào)得眼冒金星比賽后半程裁判提醒電腦快沒電了。紙質(zhì)模板完全沒有這些幺蛾子而且翻頁本身有觸感配合彩色標(biāo)簽紙幾秒鐘就能定位到要找的算法。大部分比賽的規(guī)則里紙質(zhì)資料頁數(shù)會有限制常見的是一支隊伍不超過 25 頁。這就帶來一個殘酷的事實不是所有算法都能塞進(jìn)這份 PDF你得做取舍。25 頁的模板恰恰倒逼你只收藏那些“高頻、短小、能快速上手”的核心代碼。1.2 PDF 在格式層面是各種方案里最省心的我見過有人用 Markdown 存模板有人用 Word也有人直接開個純文本文件。每種方案都有它的適用場景但如果你最終目標(biāo)是打印 電子檔雙份保存PDF 的優(yōu)勢非常明顯。格式寫起來打印效果跨設(shè)備一致性適合場景Markdown舒服依賴導(dǎo)出工具一般日常編輯與維護(hù)Word繁瑣穩(wěn)定但代碼塊和公式排版折騰較好非技術(shù)向排版純文本最快幾乎沒有排版可言好臨時記錄PDF需借助轉(zhuǎn)換工具固定不變極好最終交付、打印、存檔PDF 的核心優(yōu)勢是“所見即所得”的一致性你用這個字體、這個行距生成出來隊友在 Windows 上打開裁判在賽場機(jī)器上打開看到的頁面完全一樣不會因為系統(tǒng)缺字體而錯亂。同時 PDF 天然支持書簽?zāi)夸洝⑽淖謾z索和頁碼電子版在比賽前快速排查某個模板是否存在時CtrlF 一按就出來了。2. 模板內(nèi)容該怎么規(guī)劃模塊化搭建你的算法庫2.1 第一優(yōu)先級數(shù)據(jù)結(jié)構(gòu)和基礎(chǔ)算法模板不是越多越好而是越“順手”越好。我自己的整理順序是嚴(yán)格按照使用頻率來排的第一梯隊一定是數(shù)據(jù)結(jié)構(gòu)因為在任何一場比賽里數(shù)據(jù)結(jié)構(gòu)都是出題人的“寵兒”。我整理的第一層必收清單大致是并查集帶路徑壓縮 按秩合并處理集合合并與查詢問題。樹狀數(shù)組單點修改、區(qū)間查詢代碼量小常數(shù)也小。線段樹區(qū)間加、區(qū)間求和、區(qū)間最值懶標(biāo)記是必會的最基礎(chǔ)寫法。KMP單模式串匹配next 數(shù)組的求法必須背熟。Trie 字典樹處理前綴匹配和異或相關(guān)問題時非常常用。哈希表手寫一個簡單的哈希避免賽后發(fā)現(xiàn) STL 被卡常數(shù)。以并查集為例模板里我會放這樣的代碼// 并查集merge(x, y) 合并find(x) 查詢根 // 復(fù)雜度均攤 O(alpha(n)) // 注意使用前需要初始化 fa[i] i int fa[MAXN], rk[MAXN]; int find(int x) { return fa[x] x ? x : fa[x] find(fa[x]); } void merge(int x, int y) { x find(x); y find(y); if (x y) return; if (rk[x] rk[y]) swap(x, y); fa[y] x; if (rk[x] rk[y]) rk[x]; }這類代碼短、無歧義、幾乎每年都能用到屬于模板里的“壓艙石”。2.2 按“出題概率 × 代碼長度”篩選圖論、數(shù)論、DP、計算幾何第二層是按專題往里塞內(nèi)容我給自己定的篩選公式很簡單一句話題解打成三個字——值不值。一個算法值不值得占模板的一頁就看它在賽場上出現(xiàn)的頻率夠不夠高以及代碼長度是不是在“現(xiàn)場能默寫”和“必須看模板”之間。以圖論為例必收的是堆優(yōu)化 Dijkstra單源最短路、Kruskal最小生成樹、拓?fù)渑判?、Tarjan強(qiáng)連通分量/縮點。SPFA 我建議不要放現(xiàn)在的出題人太會構(gòu)造數(shù)據(jù)卡它了。網(wǎng)絡(luò)流 Dinic 我直到大二才把它放進(jìn)模板因為它雖然長得像模板題專屬但在一些難題里做建模中轉(zhuǎn)時確實能救命。數(shù)論這塊擴(kuò)展歐幾里得、快速冪、線性篩、逆元、組合數(shù)取模是必收項剩下的 Lucas、歐拉函數(shù)、莫比烏斯反演看個人精力。動態(tài)規(guī)劃不是“模板重災(zāi)區(qū)”因為狀態(tài)轉(zhuǎn)移方程幾乎無法模板化我會把 0-1 背包、完全背包、區(qū)間 DP、LIS/LCS、數(shù)位 DP、狀壓 DP 的轉(zhuǎn)移框架各寫一個“最小可運行版本”用來提醒自己初始化邊界和循環(huán)順序。計算幾何是很多人容易忽略的板塊但凸包、最近點對、向量叉積判斷點與線段位置這些在區(qū)域賽里出現(xiàn)的頻率并不低。這類代碼一般不長但細(xì)節(jié)多屬于“明明會寫現(xiàn)場一緊張就寫錯”的類型放進(jìn) PDF 價值極高。另外提醒一句網(wǎng)上確實有大量整理好的 ACM 模板 PDF、Hot 100 題解 PDF 之類你可以參考它們的目錄結(jié)構(gòu)但千萬不要直接拿別人的來打印。整理模板的過程本身就是在梳理你的知識盲區(qū)別人的模板再好到了你手上你也很難在賽場上一眼找到自己需要的那一段。2.3 明確“不收錄”清單控制模板總量25 頁的容量是稀缺資源所以我給自己定了三條“不收錄”原則第一超過一頁才能寫完的算法要么拆要么砍。拆的意思是只保留核心部分把邊界處理寫成注釋砍的意思是直接移除。我見過有人把 Splay 的完整實現(xiàn)塞進(jìn)模板整整兩頁半說實話真到賽場上你根本來不及調(diào)那么長的代碼。第二在 30 秒內(nèi)找不到位置的算法不配進(jìn)模板。如果一個算法在你的目錄里藏在三級標(biāo)題的某個角落里翻了兩頁還沒翻到那它和沒帶沒有區(qū)別。為了提升查找效率我的目錄結(jié)構(gòu)固定為“數(shù)據(jù)結(jié)構(gòu) / 圖論 / 數(shù)論 / DP / 計算幾何 / 雜項”每個分類下最多 6 個模板。第三原理沒吃透的算法不要放。有些選手會把一些自己沒完全理解的高級數(shù)據(jù)結(jié)構(gòu)硬塞進(jìn)模板結(jié)果賽場上抄下來之后一改就崩反而浪費大量時間。模板應(yīng)該是你“腦子已經(jīng)會了手需要提醒一下”的東西而不是你的“自動駕駛儀”。3. 模板代碼的編寫規(guī)范讓打印出來的代碼一樣能看懂3.1 統(tǒng)一風(fēng)格與變量命名模板代碼和普通做題代碼的最大區(qū)別是你是在“學(xué)習(xí)狀態(tài)下”寫它在“緊張狀態(tài)下”用它。所以代碼風(fēng)格必須統(tǒng)一到“閉著眼睛都能改”的程度。我的習(xí)慣是所有模板統(tǒng)一用 4 空格縮進(jìn)大括號換行風(fēng)格全篇保持一致。變量名盡量短但可讀cnt、tot、ans這種都可以但不要用a、b、c到底。數(shù)組大小統(tǒng)一用MAXN代替具體數(shù)字并在注釋中明確標(biāo)注“若 N 范圍超過 1e6請修改”。另外每個模板文件里我都會自己維護(hù)一份“通用頭”——包括快讀函數(shù)。比賽里輸入數(shù)據(jù)可能很大cin就算解綁了同步有時候也不夠穩(wěn)一份帶getchar的快讀模板屬于剛需。3.2 注釋寫“怎么用”不寫“為什么”這一點我特別想強(qiáng)調(diào)。很多人在整理模板時會把算法原理長篇大論地寫在代碼上面什么“本算法基于分治思想每次將區(qū)間一分為二……”這類話在賽場上一點用都沒有。模板注釋的正確寫法是告訴未來的自己這個函數(shù)接收什么參數(shù)、返回什么結(jié)果、復(fù)雜度是多少、有哪些坑。// 樹狀數(shù)組單點 add(pos, val)區(qū)間 query(l, r) // 復(fù)雜度add 和 query 均為 O(log n) // 注意需要先 init(n) 設(shè)置大小下標(biāo)從 1 開始 int tr[MAXN], n; void init(int _n) { n _n; memset(tr, 0, sizeof(tr)); } void add(int pos, int val) { for (; pos n; pos pos -pos) tr[pos] val; } int sum(int pos) { int res 0; for (; pos 0; pos - pos -pos) res tr[pos]; return res; } int query(int l, int r) { return sum(r) - sum(l - 1); }至于這個算法為什么對、數(shù)學(xué)證明是什么那是你平時訓(xùn)練該解決的事不應(yīng)該出現(xiàn)在模板里。模板不是教材是“提詞器”。3.3 每個模板塊拆成三段式結(jié)構(gòu)我自己的每個模板塊都固定成三段式第一段功能標(biāo)題 復(fù)雜度標(biāo)題里直接寫出算法名字比如“線段樹——區(qū)間加 區(qū)間求和懶標(biāo)記”。第二段核心代碼。這段代碼必須是可直接運行、可編譯通過的。我會在每次生成 PDF 前用一個統(tǒng)一的測試文件把所有模板代碼編譯一遍。第三段調(diào)用示例。寫一個極簡的main函數(shù)里面只有幾行輸入和調(diào)用方便我在賽場上快速回憶起“這函數(shù)到底該按什么順序調(diào)”。之所以強(qiáng)調(diào)第三段是因為我吃到過不少苦頭。有一年區(qū)域賽我用了自己模板里的 LIS 變種結(jié)果因為沒寫調(diào)用示例那個參數(shù)順序我看了整整半分鐘才反應(yīng)過來是“先傳數(shù)組名再傳長度”。半分鐘在賽場上屬于相當(dāng)昂貴的代價。4. 從 Markdown 到 PDF一套貼近實戰(zhàn)的生成流程4.1 工具鏈選擇與理由工具鏈我試過好幾套純 Typora 導(dǎo)出 PDF、VS Code 插件 Markdown PDF、在線轉(zhuǎn)換網(wǎng)站最后穩(wěn)定在“Markdown Pandoc XeLaTeX”這套方案。為什么不用 Typora 直接導(dǎo)出因為它走的也是內(nèi)置渲染引擎對長文檔的分頁控制很弱代碼塊跨頁時經(jīng)常出現(xiàn)很丑的斷行。為什么不用在線轉(zhuǎn)換工具因為 ACM 模板涉及大量代碼塊、縮進(jìn)、中英文混排在線工具導(dǎo)出的格式往往不可控而且你的代碼內(nèi)容放在別人服務(wù)器上總歸不太安心。Pandoc 的路線是先用 Markdown 寫內(nèi)容再用 Pandoc 轉(zhuǎn)成 LaTeX 中間文件最后由 XeLaTeX 引擎渲染 PDF。這條路的好處是每個環(huán)節(jié)都在你本地完成可復(fù)現(xiàn)且一旦調(diào)試好參數(shù)以后每次導(dǎo)出都是同一個漂亮結(jié)果。4.2 親測可用的 Pandoc 命令與參數(shù)詳解我目前在 Linux 環(huán)境下用的命令大概是這樣的pandoc ACM_template.md -o ACM_template.pdf \ --pdf-enginexelatex \ -V CJKmainfontNoto Sans CJK SC \ -V mainfontNoto Sans Mono CJK SC \ -V geometry:margin2cm \ --toc \ --highlight-styletango \ -V colorlinkstrue這幾個參數(shù)逐個說--pdf-enginexelatex指定用 XeLaTeX 作為 PDF 引擎它原生支持 Unicode中文字體處理比舊版 pdflatex 省心得多。-V CJKmainfontNoto Sans CJK SC設(shè)置中文字體。如果你的系統(tǒng)沒有這個字體可以用fc-list :langzh查看可用中文字體然后再換名字。-V mainfontNoto Sans Mono CJK SC設(shè)置西文和等寬字體。代碼塊會大量使用等寬字體這一項直接影響代碼顯示效果。-V geometry:margin2cm設(shè)置頁邊距。2cm 是我實測下來比較舒服的寬度既能保證一頁放足夠多內(nèi)容又不會顯得太擠。如果頁數(shù)緊張可以縮到 1.8cm。--toc自動生成目錄。配合 Pandoc 的分頁邏輯會出現(xiàn)在文檔開頭。--highlight-styletango設(shè)置代碼高亮主題。tango 是打印友好的淺色主題避免代碼塊變成黑底白字浪費墨水又傷眼。-V colorlinkstrue讓 PDF 里的超鏈接顯示為彩色。如果你要打印建議后面改成-V colorlinksfalse否則打印出來一片藍(lán)。如果你在 Windows 上建議搭配 TeX Live 或者 MiKTeX同時用-V CJKmainfontMicrosoft YaHei這類系統(tǒng)中文字體名。4.3 目錄、分頁與代碼高亮的細(xì)節(jié)處理Pandoc 默認(rèn)會把一級標(biāo)題當(dāng)成章二級標(biāo)題當(dāng)成節(jié)生成書簽這對 ACM 模板來說其實夠用。但有一個問題需要手動處理分頁。你肯定不希望“并查集”和“樹狀數(shù)組”這兩個毫無關(guān)系的模板擠在同一頁上。解決辦法是在 Markdown 源文件里每個二級標(biāo)題前手動插入一個 LaTeX 換頁指令\newpage ## 2. 圖論Pandoc 默認(rèn)是支持 raw_tex 擴(kuò)展的也就是說這個\newpage會原樣傳給 LaTeX 引擎最終效果就是在“圖論”這一節(jié)之前強(qiáng)制分頁。注意這個指令在 Typora 預(yù)覽里不會變成真正的分頁但你不用管等導(dǎo)出 PDF 時它就會生效。代碼高亮還有一個隱藏問題Pandoc 的默認(rèn)高亮主題在打印時會帶背景色如果整段代碼底色是灰色打印頁數(shù)一多墨水消耗會很夸張。我的做法是除了--highlight-styletango還會在生成的 LaTeX 文件里微調(diào)代碼字號把列表環(huán)境里的字體從默認(rèn)的\small改成\footnotesize這樣同樣的內(nèi)容能壓掉不少行數(shù)。如果你只是想快速導(dǎo)出一版看看效果不追求最終質(zhì)量直接用 Typora 的“導(dǎo)出 PDF”按鈕也可以。但正式比賽前我還是建議走一遍 Pandoc 路線因為它給了你完全可控的分頁和目錄。5. 常見問題與排查技巧實錄5.1 中文亂碼與字體問題這是我最開始折騰最久的一個問題。現(xiàn)象是PDF 生成成功但所有中文都變成了黑色方塊或者直接消失。原因幾乎可以確定是 XeLaTeX 找不到中文字體或者沒有正確設(shè)置CJKmainfont。解決步驟很固定在終端執(zhí)行fc-list :langzh查看系統(tǒng)裝了哪些中文字體?？摧敵隼镉袥]有Noto Sans CJK SC、WenQuanYi Micro Hei、Microsoft YaHei這類字體。把查到的一個字體名字填到-V CJKmainfont字體名注意字體名中間有空格就必須加引號。如果你已經(jīng)設(shè)置了字體還是亂碼大概率是 Pandoc 版本太老。建議把 Pandoc 升級到 2.x 以上XeLaTeX 也要保證是 TeX Live 2019 之后的版本舊版對中文支持的細(xì)節(jié)確實差很多。5.2 代碼跨頁斷行與排版崩壞長代碼塊和分頁機(jī)制的沖突是所有模板里最頭疼的一件事。常見情況是一個線段樹模板長度超過一頁Pandoc 直接把代碼硬生生從中間切斷下一頁從后半截開始看起來非常難受。我的應(yīng)對思路有兩個方向。第一個方向是“人事分離”把過長的代碼拆成“核心邏輯”和“完整實現(xiàn)”兩截。核心邏輯只保留最重要的 update 和 query 函數(shù)完整實現(xiàn)可以作為附錄放在分類末尾。賽場上的需求通常是“回憶一下怎么改”不是“從頭抄一遍”所以核心邏輯那幾行往往比完整代碼更有用。第二個方向是技術(shù)手段在 Pandoc 命令里給 listings 環(huán)境設(shè)置自動換行和斷行。我實測可以這樣加參數(shù)-V listings -V listings-disable-line-numbers然后在 Markdown 里用listing環(huán)境替代普通代碼塊不過這套玩法對 Markdown 的侵入性比較大適合你已經(jīng)很熟悉 LaTeX 的情況。如果你的需求只是“模板打印出來能看”前一個方向足夠。5.3 PDF 體積、打印效果與閱讀體驗PDF 文件動不動幾十 MB通常是嵌入了大量字體子集導(dǎo)致的。模板這種純文字 PDF 其實體積不會太大如果看到異常膨脹檢查一下 Markdown 源文件里有沒有不小心塞進(jìn)去的大圖片。打印層面有幾個實測建議問題建議鏈接顏色在黑白打印下變灰塊導(dǎo)出時設(shè)置-V colorlinksfalse雙面打印后內(nèi)容壓到裝訂線在 geometry 參數(shù)里加bindingoffset0.5cm代碼背景色太深用--highlight-styletango或breezedark這類淺色主題頁碼看不清在 LaTeX 模板或頁腳設(shè)置里加大頁數(shù)字號另外我強(qiáng)烈建議在最終打印前先打印一頁測試頁看看字體、行距、代碼縮進(jìn)到底什么效果。你整理這個 PDF 花的力氣最后都要靠打印效果來兌現(xiàn)。6. 模板的迭代維護(hù)與賽場使用小技巧6.1 訓(xùn)練賽后標(biāo)準(zhǔn)化更新流程模板不是整理一次就完事的東西它應(yīng)該跟著你的水平一起漲。我給自己定了一個標(biāo)準(zhǔn)流程每次訓(xùn)練賽結(jié)束我都會在賽后補(bǔ)題時問自己一個問題這場比賽里有沒有一個算法是我“會但寫得很慢”或者“明明可以做出來卻因為代碼不熟浪費了太多時間”的如果有就在賽后的統(tǒng)一維護(hù)時間里把這個算法的模板優(yōu)化一遍。優(yōu)化包括精簡代碼、補(bǔ)注釋、重新編譯驗證然后同步更新到 Git 倉庫再重新導(dǎo)出 PDF。這套流程一周一次平均每周花 40 分鐘。別小看這一點點更新我有一版線段樹模板就是這樣從最初的 80 行“大頭娃娃”逐步瘦身到 60 行的而賽場上的效率提升是立竿見影的。6.2 打印、收納與現(xiàn)場快速查找的經(jīng)驗關(guān)于紙質(zhì)模板的現(xiàn)場使用有三件事我想按重要性從高到低排一下序。第一件也是最重要的一件給每個大分類貼彩色標(biāo)簽。數(shù)據(jù)結(jié)構(gòu)用紅色標(biāo)簽圖論用藍(lán)色數(shù)論用綠色DP 用黃色計算幾何用橙色。這樣你在賽場上翻模板瞄一眼顏色就能定位到分類再翻幾下就能找到具體算法比看目錄還要快。我見過太多人辛辛苦苦做了 PDF打印出來卻是一沓白紙黑字賽場上翻模板翻了五分鐘心態(tài)直接爆炸。第二件目錄頁打印在封面背面。目錄是檢索的第一入口一定要放在一眼能看到的位置。而且目錄上的頁碼要跟 PDF 導(dǎo)出的頁碼一致所以每次更新后要重新打印不能拿舊目錄去對著新版模板。第三件賽前做一次“20 分鐘手抄模板”測試。具體做法是隨機(jī)抽出模板里的 3 個算法打印在試卷紙上20 分鐘內(nèi)不看任何資料憑記憶手寫出來。如果哪一步卡住了說明那個模板的注釋還不夠清晰或者代碼邏輯你還是沒吃透需要回爐重做。這個測試聽起來有點變態(tài)但實測非常能發(fā)現(xiàn)模板的“偽熟練”問題。說回“個人整理ACM模板.pdf”這件事本身。整理模板真正磨人的不是寫代碼的那一下子而是你發(fā)現(xiàn)同一段 KMP 你已經(jīng)在不同地方抄過第三遍了。我的習(xí)慣是每次看到別人代碼里有更簡潔的寫法、更少 bug 的邊界處理就當(dāng)場替換掉自己模板里的對應(yīng)段落。這個習(xí)慣讓我少打了很多無意義的字也讓我的模板在一次次比賽里變得越來越“聽話”。最后一個小小的建議PDF 生成之后一定要自己打印出來在睡前或者通勤路上多翻幾遍。只有被反復(fù)翻過的模板比賽時才真正長在你手上。本文還有配套的精品資源點擊獲取