簡(jiǎn)介NOIP1995-2008年普及組復(fù)賽試題及解析以25頁(yè)P(yáng)DF形式整理成冊(cè)面向備戰(zhàn)信息學(xué)奧賽的初中生、中學(xué)生和編程初學(xué)者用于系統(tǒng)了解歷年復(fù)賽題型、算法側(cè)重點(diǎn)與常用解題策略。題目涵蓋算式求解、方陣填數(shù)、二進(jìn)制數(shù)分類(lèi)、編碼問(wèn)題、燈的排列、乘法豎式、棋盤(pán)遍歷、字符串編輯等經(jīng)典內(nèi)容既練習(xí)枚舉、模擬、遞推等基礎(chǔ)算法也涉及數(shù)組、字符串等數(shù)據(jù)結(jié)構(gòu)的應(yīng)用還包含輸入輸出格式、邊界條件等競(jìng)賽常見(jiàn)細(xì)節(jié)。整個(gè)資源包為單份PDF文件體積約352KB頁(yè)面緊湊便于打印或按年份翻閱。已有306人學(xué)習(xí)使用說(shuō)明其在普及組備賽場(chǎng)景中具備一定參考價(jià)值。通過(guò)學(xué)習(xí)完整賽題和配套解析讀者可逐題理解編程思路與常見(jiàn)解法適合賽前集中刷題、查漏補(bǔ)缺也可作為信息學(xué)競(jìng)賽入門(mén)教學(xué)的補(bǔ)充材料。1. 一份 25 頁(yè)的 NOIP 普及組復(fù)賽 PDF老題解析為什么還值得逐題過(guò)一遍對(duì)很多剛接觸信奧的選手來(lái)說(shuō)NOIP 普及組復(fù)賽的第一份訓(xùn)練材料往往不是最新的模擬卷而是一份 25 頁(yè)、收錄了 1995 到 2008 年歷年復(fù)賽真題的 PDF。年份寫(xiě)的是上世紀(jì)九十年代題名卻一直在刷存在感二進(jìn)制數(shù)分類(lèi)、方陣填數(shù)、字符串編輯、過(guò)河卒、麥森數(shù)——現(xiàn)在的普及組試卷里依然能找到它們的影子。這份 PDF 適合三種人第一次接觸競(jìng)賽、想用老題打基礎(chǔ)的初中生需要給學(xué)生安排限時(shí)訓(xùn)練的教練想快速補(bǔ)一遍枚舉、遞推、搜索、高精度這些基礎(chǔ)算法卻懶得翻題庫(kù)的從業(yè)者。老題有一個(gè)新題很難替代的優(yōu)勢(shì)解析里直接寫(xiě)了「問(wèn)題分析」等于把出題人的提示擺在桌面上。2. 把 1995-1999 拆成三類(lèi)題枚舉、遞推與字符串模擬2.1 二進(jìn)制數(shù)分類(lèi)把題意翻譯成循環(huán)的經(jīng)典樣例1995 年這道「二進(jìn)制數(shù)分類(lèi)」是全卷里最適合入門(mén)的第一題。題目規(guī)定將一個(gè)正整數(shù)轉(zhuǎn)成二進(jìn)制后如果 1 的個(gè)數(shù)多于 0 的個(gè)數(shù)就是 A 類(lèi)數(shù)否則是 B 類(lèi)數(shù)要求統(tǒng)計(jì) 1 到 1000 中兩類(lèi)數(shù)各有多少。這里有一個(gè)非常容易被忽略的邊界題目說(shuō)的是「多于」也就是 1 的個(gè)數(shù)等于 0 的個(gè)數(shù)時(shí)歸為 B 類(lèi)不能寫(xiě)成大于等于。def count_ab(limit: int 1000) - tuple[int, int]: cnt_a 0 cnt_b 0 for x in range(1, limit 1): b bin(x)[2:] # 去掉 0b 前綴得到真正的二進(jìn)制串 ones b.count(1) zeros len(b) - ones if ones zeros: # 注意是“多于”相等時(shí)歸 B cnt_a 1 else: cnt_b 1 return cnt_a, cnt_b邏輯說(shuō)明遍歷 1 到 1000對(duì)每個(gè)數(shù)取二進(jìn)制字符串統(tǒng)計(jì) 1 和 0 的個(gè)數(shù)后比較。關(guān)鍵參數(shù)是limit1000對(duì)應(yīng)題目規(guī)定的統(tǒng)計(jì)范圍bin(x)[2:]這一步?jīng)Q定了統(tǒng)計(jì)口徑因?yàn)槎M(jìn)制表示不包含前導(dǎo)零例如 4 的二進(jìn)制是1000 的個(gè)數(shù)算 2 個(gè)而不是 3 個(gè)。如果誰(shuí)手滑按 8 位定長(zhǎng)去統(tǒng)計(jì)答案會(huì)整個(gè)跑偏。這道題真正的訓(xùn)練價(jià)值不在算法而在「把自然語(yǔ)言描述精確翻譯成程序邏輯」是典型的普及組第一題風(fēng)格。2.2 字符串編輯D/I/R 三種命令的實(shí)現(xiàn)口徑1996 年的字符串編輯題放在今天看依然是好題因?yàn)樗炎址幚淼娜?lèi)基本操作揉在一起還故意設(shè)置了幾處「陷阱」D 命令刪除第一次出現(xiàn)的字符I 命令插入到最后一個(gè)目標(biāo)字符的前面R 命令全部替換目標(biāo)字符不存在時(shí)給出提示。三種命令的操作口徑完全不同這正是模擬題的考法——不是算法難而是題意必須讀細(xì)。def edit_string(s: str, cmds: list[str]) - str: for cmd in cmds: op cmd[0] if op D: ch cmd[1] idx s.find(ch) # 只找第一個(gè) print(no such char if idx -1 else , end) if idx ! -1: s s[:idx] s[idx 1:] elif op I: target, ch cmd[1], cmd[2] idx s.rfind(target) # 最后一個(gè)目標(biāo)字符 if idx -1: print(no such char) else: s s[:idx] ch s[idx:] elif op R: old, new cmd[1], cmd[2] if old not in s: print(no such char) else: s s.replace(old, new) # 全部替換 return s邏輯說(shuō)明三點(diǎn)實(shí)現(xiàn)細(xì)節(jié)直接決定能否通過(guò)。第一find和rfind的差別對(duì)應(yīng) D 與 I 的不同要求第二replace默認(rèn)替換全部匹配項(xiàng)所以 R 命令不需要手寫(xiě)循環(huán)第三字符串以.結(jié)尾時(shí)實(shí)際操作里一般保留這個(gè)結(jié)束符不做編輯避免把句號(hào)誤刪。我在復(fù)現(xiàn)時(shí)習(xí)慣把三個(gè)命令分別封裝成函數(shù)再統(tǒng)一走一層 dispatch這樣出問(wèn)題時(shí)定位更快。參數(shù)注釋里提到的target指的是題目里Ia1a2格式中的a1也就是插入位置的參照字符。2.3 Cantor 表與棋盤(pán)計(jì)數(shù)遞推公式比模擬填表更穩(wěn)1997 到 1999 年這三年的題目開(kāi)始出現(xiàn)「規(guī)律題」Cantor 表的 Z 字形編號(hào)、棋盤(pán)中的正方形與長(zhǎng)方形計(jì)數(shù)、比賽安排的循環(huán)賽程。這類(lèi)題給新手最大的教訓(xùn)是不要一上來(lái)就照著題意模擬先花兩分鐘想公式。以 Cantor 表為例它是一張按斜線排列的有理數(shù)表編號(hào)沿 Z 字形走輸入 N 最大到一千萬(wàn)如果真去逐項(xiàng)填表時(shí)間和內(nèi)存都會(huì)爆。def cantor(n: int) - str: k 1 while k * (k 1) // 2 n: # 前 k 條斜線共有 k(k1)/2 項(xiàng) k 1 pos n - (k - 1) * k // 2 # 當(dāng)前斜線上的第幾項(xiàng) if k % 2 1: # 奇數(shù)斜線從下往上 return f{k - pos 1}/{pos} else: # 偶數(shù)斜線從上往下 return f{pos}/{k - pos 1}邏輯說(shuō)明k是第幾條斜線前k-1條斜線的項(xiàng)數(shù)總和是(k-1)*k//2用pos定位第 N 項(xiàng)在當(dāng)前斜線的位置。斜線序號(hào)為奇數(shù)時(shí)分子遞減分母遞增偶數(shù)時(shí)相反。這里的時(shí)間復(fù)雜度是 O(sqrt(N))一千萬(wàn)的輸入也只是毫秒級(jí)。同樣的思路也用在棋盤(pán)計(jì)數(shù)題上正方形的個(gè)數(shù)是sum((n-s1)*(m-s1) for s in range(1, min(n,m)1))長(zhǎng)方形總數(shù)用組合數(shù)C(n1,2)*C(m1,2)減去正方形個(gè)數(shù)直接套公式不需要枚舉所有矩形。3. 2000-2004 開(kāi)始上難度搜索、動(dòng)態(tài)規(guī)劃與高精度3.1 級(jí)數(shù)求和與選數(shù)精度和判重是第一道坎2002 年有兩道題是典型的「看起來(lái)簡(jiǎn)單寫(xiě)起來(lái)翻車(chē)」級(jí)數(shù)求和和選數(shù)。級(jí)數(shù)求和本身只是算S_n 1 1/2 1/3 ... 1/n找到第一個(gè)大于 K 的 nK 不超過(guò) 15。但浮點(diǎn)誤差在這里會(huì)咬人1/n累加幾十萬(wàn)次之后誤差可能讓判斷S_n K的時(shí)機(jī)偏一位。解析里特意提到 Pascal 時(shí)代用 Extended 比 Real 快放到現(xiàn)在我的習(xí)慣是直接開(kāi) double或者在判斷處加一個(gè)極小閾值比如if total k 1e-12。選數(shù)題才是真正的分水嶺。題目給 n 個(gè)不超過(guò) 500 萬(wàn)的整數(shù)選 k 個(gè)求和統(tǒng)計(jì)和為素?cái)?shù)的方案數(shù)。n 最大 20意味著組合數(shù)上限是 C(20,10)184756DFS 完全可以扛住。但解析里直接點(diǎn)名了一個(gè)丟分點(diǎn)統(tǒng)計(jì)的是「和為素?cái)?shù)的方案數(shù)」不是「不同的素?cái)?shù)個(gè)數(shù)」比賽時(shí)有人做了判重反而丟了 12 分。另外1 不是素?cái)?shù)這個(gè)特判必須在素?cái)?shù)函數(shù)里寫(xiě)死。def is_prime(x: int) - bool: if x 1: return False if x 2: return True if x % 2 0: return False i 3 while i * i x: if x % i 0: return False i 2 return True def count_pick(n: int, k: int, nums: list[int]) - int: ans 0 def dfs(start: int, depth: int, cur_sum: int): nonlocal ans if depth k: if is_prime(cur_sum): ans 1 return for i in range(start, n): dfs(i 1, depth 1, cur_sum nums[i]) dfs(0, 0, 0) return ans邏輯說(shuō)明遞歸參數(shù)start保證每次選的數(shù)在原序列中位置遞增這是組合生成的標(biāo)準(zhǔn)寫(xiě)法既不會(huì)產(chǎn)生重復(fù)方案也不需要額外的 visited 數(shù)組。cur_sum在遞歸過(guò)程中維護(hù)當(dāng)前和到深度 k 時(shí)統(tǒng)一判斷。判斷素?cái)?shù)時(shí)只需要試除到sqrt(x)因?yàn)檫@道題里求和結(jié)果最大不超過(guò)一億開(kāi)根號(hào)后到一萬(wàn)循環(huán)代價(jià)很小。如果追求更快可以按解析的建議用篩選法預(yù)先生成 2 到 10000 的素?cái)?shù)表再只拿素?cái)?shù)去試除速度能提高五到六倍。3.2 過(guò)河卒與裝箱問(wèn)題遞推和 01 背包的原型過(guò)河卒這道題在 NOIP 歷史上反復(fù)出現(xiàn)1997 年普及組最后一題和 2002 年復(fù)賽題幾乎一樣。題目說(shuō)卒只能向下或向右走棋盤(pán)上有馬的控制點(diǎn)不能經(jīng)過(guò)問(wèn)從 (0,0) 到 (n,m) 有幾條路徑。解析里那句「要到達(dá)棋盤(pán)上的一個(gè)點(diǎn)只能從左邊過(guò)來(lái)或是從上面下來(lái)」直接點(diǎn)破了遞推本質(zhì)到達(dá)某點(diǎn)的路徑數(shù)等于到達(dá)其上方點(diǎn)和左方點(diǎn)的路徑數(shù)之和。def horse_paths(n: int, m: int, hx: int, hy: int) - int: dp [[0] * (m 1) for _ in range(n 1)] blocked [[False] * (m 1) for _ in range(n 1)] jumps [(0,0), (1,2), (2,1), (2,-1), (1,-2), (-1,-2), (-2,-1), (-2,1), (-1,2)] for dx, dy in jumps: x, y hx dx, hy dy if 0 x n and 0 y m: blocked[x][y] True dp[0][0] 1 for i in range(n 1): for j in range(m 1): if blocked[i][j]: dp[i][j] 0 continue if i 0: dp[i][j] dp[i - 1][j] if j 0: dp[i][j] dp[i][j - 1] return dp[n][m]邏輯說(shuō)明jumps里包含 (0,0) 是為了把馬自己所在的位置也標(biāo)記為控制點(diǎn)這是很多人第一次寫(xiě)時(shí)漏掉的細(xì)節(jié)。遞推時(shí)按行優(yōu)先遍歷每個(gè)格子只依賴(lài)上方和左方所以空間可以?xún)?yōu)化成一維數(shù)組但普及組階段用二維數(shù)組更直觀。n 和 m 不超過(guò) 20答案最多 14 位Python 的 int 隨便裝當(dāng)年 C 選手要開(kāi) Comp 類(lèi)型或 long long這個(gè)細(xì)節(jié)解析里也提了。裝箱問(wèn)題則是 01 背包的裸題容量 v 不超過(guò) 20000n 不超過(guò) 30每個(gè)物品體積給定求最小剩余空間。狀態(tài)方程就一行dp[j] max(dp[j], dp[j - w] w)最后輸出v - dp[v]難度比過(guò)河卒還低但它是普及組第一次正面引入「背包」概念值得單獨(dú)做一遍。3.3 麥森數(shù)與乘積最大高精度的兩種打開(kāi)方式2003 年的麥森數(shù)題要求計(jì)算2^P - 1的位數(shù)和最后 500 位數(shù)字P 可以到 310 萬(wàn)。這道題的高精度思路分兩段位數(shù)用對(duì)數(shù)公式floor(P * log10(2)) 1不涉及大數(shù)計(jì)算后 500 位用快速冪取模模數(shù)取10^500只保留低 500 位。import math def mersenne_tail(P: int) - tuple[int, str]: digits int(P * math.log10(2)) 1 # 位數(shù)公式 mod 10 ** 500 last500 str((pow(2, P, mod) - 1) % mod) # 注意減 1 后可能縮位 return digits, last500.zfill(500)邏輯說(shuō)明pow(2, P, mod)是 Python 內(nèi)置的快速冪取模效率足夠處理 P3100000。減 1 之后如果結(jié)果恰好小于 500 位zfill(500)會(huì)把高位補(bǔ)成 0對(duì)應(yīng)題目「不足 500 位時(shí)高位補(bǔ) 0」的輸出要求。位數(shù)公式的原理是2^P的十進(jìn)制位數(shù)等于log10(2^P)向下取整加一也就是P * log10(2)的整數(shù)部分加一這個(gè)公式在原題樣例里可以直接驗(yàn)證P1279 時(shí)輸出 3861279 * 0.30103 ≈ 385.01取整加一就是 386。乘積最大就是另一類(lèi)高精度長(zhǎng)度為 N 的數(shù)字串插入 K 個(gè)乘號(hào)讓乘積最大。N 最大 40K 最大 6區(qū)間 DP 的轉(zhuǎn)移方程是dp[i][j] max(dp[t][j-1] * num(t1, i))其中dp[i][j]表示前 i 位數(shù)字放 j 個(gè)乘號(hào)的最大值num(l, r)表示原串第 l 到 r 位組成的整數(shù)。用 Python 實(shí)現(xiàn)時(shí)不需要手寫(xiě)高精度乘法內(nèi)建 int 直接處理上百位的數(shù)字沒(méi)有壓力但換成 C/C 就必須自己寫(xiě)大數(shù)乘法這是很多人在考場(chǎng)上卡住的地方。4. 解析里藏著做題思路官方「問(wèn)題分析」怎么讀才不浪費(fèi)4.1 把「問(wèn)題分析」當(dāng)提示器選數(shù)題的判重教訓(xùn)這份 PDF 最有價(jià)值的部分不是題目本身而是每道題下面那段「問(wèn)題分析」。1995 到 2008 年的題目里官方在不少題解中直接寫(xiě)了算法選擇的理由比如選數(shù)題的解析說(shuō)「本題動(dòng)態(tài)規(guī)劃無(wú)從下手也無(wú)數(shù)學(xué)公式可尋看來(lái)只能搜索」緊跟著補(bǔ)了一句「1n20 這個(gè)約束條件也暗示我們本題搜索是有希望的」。這兩句話合在一起就是在教你怎么根據(jù)數(shù)據(jù)范圍判斷算法看到 n 小于等于 20優(yōu)先想搜索看到 n 到 40想 DP看到 N 到一千萬(wàn)想數(shù)學(xué)公式。我的使用習(xí)慣是先把題目抄下來(lái)自己寫(xiě)一遍寫(xiě)完再打開(kāi)解析里的「問(wèn)題分析」對(duì)答案。不是比誰(shuí)的代碼短而是看自己有沒(méi)有漏掉判重、邊界、精度這類(lèi)易錯(cuò)點(diǎn)。選數(shù)題那句「比賽時(shí)就有很多同學(xué)胡亂判重而丟了 12 分還有 1 不是素?cái)?shù)」就是典型的提示器——如果我先寫(xiě)完沒(méi)想到這兩點(diǎn)這一題就算白做了。4.2 兩條被點(diǎn)破的算法思路產(chǎn)生數(shù)閉包與過(guò)河卒遞推2002 年的產(chǎn)生數(shù)題解析給出了一個(gè)很干凈的建模方式把數(shù)字變換規(guī)則看成有向圖要求的就是每個(gè)數(shù)字經(jīng)過(guò)任意次變換能變成多少種數(shù)字再用乘法原理把整個(gè)整數(shù)每一位的可變數(shù)乘起來(lái)。這個(gè)思路的關(guān)鍵是傳遞閉包——如果 3 能變 55 能變 7那么 3 也必須能變 7。解析里直接給出了把 Floyd 算法中的加法替換成邏輯與、乘法替換成邏輯或的做法def transitive_closure(rules: list[tuple[int, int]]) - list[int]: reach [[False] * 10 for _ in range(10)] for i in range(10): reach[i][i] True # 每位數(shù)字不變也是一種選擇 for u, v in rules: reach[u][v] True for k in range(10): for i in range(10): for j in range(10): reach[i][j] reach[i][j] or (reach[i][k] and reach[k][j]) # 每個(gè)數(shù)字能變成的數(shù)字個(gè)數(shù)含自身 return [sum(reach[i]) for i in range(10)]邏輯說(shuō)明這個(gè)三重循環(huán)的復(fù)雜度是常數(shù)的因?yàn)閿?shù)字只有 0 到 9 十種規(guī)則數(shù)最多 15 條所以整體開(kāi)銷(xiāo)極小。拿到每個(gè)數(shù)字的可變個(gè)數(shù)后把原整數(shù)每一位的可變數(shù)相乘就是答案。這個(gè)乘法可能產(chǎn)生幾百位的數(shù)需要用高精度Python 的 int 可以無(wú)縫處理C 選手必須手寫(xiě)。過(guò)河卒的解析則更直接——「要到達(dá)棋盤(pán)上的一個(gè)點(diǎn)只能從左邊過(guò)來(lái)或是從上面下來(lái)」這句話本質(zhì)上就是在告訴你不要搜索用加法原理遞推。我在第 3 章已經(jīng)給出了遞推代碼這里想強(qiáng)調(diào)的是解析里類(lèi)似的「一句話點(diǎn)破」非常多刷的時(shí)候不要只當(dāng)答案看要把它當(dāng)作出題人留下的解題路徑。4.3 把解析當(dāng)評(píng)測(cè)標(biāo)準(zhǔn)對(duì)比自己的實(shí)現(xiàn)差距「問(wèn)題分析」還有一個(gè)用處是當(dāng)基準(zhǔn)線。我拿 1997 年的街道路徑題做過(guò)一次自我對(duì)照自己先寫(xiě)的是記憶化搜索版本能出結(jié)果但代碼長(zhǎng)再看解析它直接用遞推方程F[i,j]F[i-1,j]F[i,j-1]把問(wèn)題壓成二維表障礙區(qū)只是把對(duì)應(yīng)格子置 0。兩版對(duì)比后能明顯感受到差距搜索是順著題意走遞推是順著關(guān)系走。解析里那種「障礙區(qū)域用 2 對(duì)頂點(diǎn)坐標(biāo)給出」的讀題方式也提醒我一件事——題目描述里的邊界條件往往不是擺設(shè)。類(lèi)似的題目還有 1998 年的「1 到 9 分成三組組成 1:2:3 比例的三位數(shù)」解析的枚舉思路是從最小的三位數(shù)開(kāi)始試而不是從排列 9 個(gè)數(shù)字開(kāi)始這兩種寫(xiě)法的時(shí)間復(fù)雜度差了好幾個(gè)量級(jí)。用解析對(duì)照自己的實(shí)現(xiàn)能清楚地看到差距出在「建?！惯€是「編碼」而不是籠統(tǒng)地說(shuō)「我太弱」。5. 復(fù)現(xiàn)這份資源的避坑清單五條血淚經(jīng)驗(yàn)5.1 輸出格式翻車(chē)麥森數(shù)補(bǔ)零、乒乓球空行現(xiàn)象代碼邏輯全對(duì)樣例輸入也能跑出正確數(shù)字但提交評(píng)測(cè)時(shí)格式錯(cuò)誤。最典型的是麥森數(shù)最后 500 位不足時(shí)沒(méi)補(bǔ)前導(dǎo)零以及 2003 年乒乓球題輸出兩套比分之間漏了空行。原因麥森數(shù)的輸出要求「每行輸出 50 位共輸出 10 行不足 500 位時(shí)高位補(bǔ) 0」很多人直接打印last500字符串長(zhǎng)度不夠就少了前導(dǎo)零。乒乓球題要求兩部分結(jié)果之間有一個(gè)空行但樣例輸出在兩行比分之間看起來(lái)只差一個(gè)換行肉眼不容易發(fā)現(xiàn)。解決我現(xiàn)在的習(xí)慣是凡是輸出格式里帶「補(bǔ) 0」「空行」「對(duì)齊」字樣的題都先構(gòu)造一個(gè)輸出函數(shù)把格式全部收斂到函數(shù)內(nèi)部。麥森數(shù)直接用zfill(500)再按每 50 位切一行乒乓球題把 11 分制和 21 分制的結(jié)果分別收集到列表里用\n\n.join(...)拼裝這樣空行邏輯只有一處。復(fù)現(xiàn)老題時(shí)逐字符比對(duì)輸出樣例永遠(yuǎn)值得多花兩分鐘。5.2 浮點(diǎn)誤差在級(jí)數(shù)求和與 Cantor 表里冒頭現(xiàn)象級(jí)數(shù)求和這道題K 給 15用float累加1/n到幾十萬(wàn)項(xiàng)時(shí)total K的判斷可能提前或延后觸發(fā)導(dǎo)致輸出的 n 和答案差 1。Cantor 表如果先算浮點(diǎn)數(shù)再轉(zhuǎn)整數(shù)也可能在取整邊界上偏一位。原因1/n在二進(jìn)制浮點(diǎn)里不能精確表示累加誤差會(huì)隨 n 增大累積。Cantor 表的k*(k1)//2如果用浮點(diǎn)乘法再轉(zhuǎn) int大數(shù)精度會(huì)丟。解決級(jí)數(shù)求和把判斷條件寫(xiě)成if total k 1e-12或者干脆用分?jǐn)?shù)Fraction累加K 很小所以性能無(wú)所謂。Cantor 表的編號(hào)計(jì)算全程用整數(shù)運(yùn)算k * (k 1) // 2不要寫(xiě)成int(k * (k 1) / 2)。這題吃過(guò)大虧之后我對(duì)所有「算位置編號(hào)」的題都默認(rèn)整型運(yùn)算優(yōu)先。5.3 題目文本有 OCR 殘字先對(duì)照題面再動(dòng)手現(xiàn)象2001 年數(shù)的計(jì)數(shù)題題面寫(xiě)「茬它的左邊加上一個(gè)自然數(shù)」這個(gè)「茬」字顯然是「在」的掃描識(shí)別錯(cuò)誤2004 年 FBI 樹(shù)題面在 PDF 里被截?cái)嗪蟀攵螛?gòu)造邏輯只剩一半。原因這份 25 頁(yè) PDF 是早年紙質(zhì)試題掃描或 OCR 轉(zhuǎn)出來(lái)的個(gè)別年份排版和文字有殘缺直接照題面寫(xiě)代碼容易理解錯(cuò)。解決做這類(lèi)老題前先花幾十秒確認(rèn)題面完整性。發(fā)現(xiàn)明顯錯(cuò)字、缺行時(shí)用題目編號(hào)加關(guān)鍵詞去對(duì)照在線題庫(kù)的題面確認(rèn)輸入輸出樣例一致后再動(dòng)手。解析里的「問(wèn)題分析」是 PDF 獨(dú)有的素材這部分通常沒(méi)有 OCR 損壞可以放心讀。我的經(jīng)驗(yàn)是老題 PDF 適合用來(lái)練思路和刷算法不適合當(dāng)作唯一題面來(lái)源。5.4 過(guò)河卒用搜索必超時(shí)數(shù)據(jù)范圍暗示算法現(xiàn)象過(guò)河卒這道題n 和 m 不超過(guò) 20第一反應(yīng)是 DFS 從起點(diǎn)搜到終點(diǎn)樣例能過(guò)但 n 到 14、15 時(shí)遞歸分支爆炸穩(wěn)超時(shí)。原因DFS 在無(wú)障礙棋盤(pán)上的路徑數(shù)是組合數(shù)級(jí)別的20×20 的網(wǎng)格路徑數(shù)已經(jīng)有 14 位遞歸搜索會(huì)重復(fù)計(jì)算大量子問(wèn)題。解析里特意寫(xiě)了「有些同學(xué)用了搜索當(dāng) n 到 14、15 左右就會(huì)超時(shí)」。解決看到「路徑條數(shù)」四個(gè)字先想遞推而不是搜索。F[i,j]F[i-1,j]F[i,j-1]的時(shí)間復(fù)雜度是 O(n*m)記憶化搜索雖然也能過(guò)但本質(zhì)是同一個(gè)遞推不如直接寫(xiě)迭代。這道題給我的教訓(xùn)是題目數(shù)據(jù)范圍本身就是算法提示n20 可以搜索n200 必須 DP這個(gè)判斷能力比背模板更重要。5.5 老題的評(píng)分分值和現(xiàn)代評(píng)測(cè)環(huán)境不對(duì)等現(xiàn)象2003 年之前的題目很多標(biāo)注 30 分、40 分部分題沒(méi)有給出完整的多組測(cè)試數(shù)據(jù)說(shuō)明。新手按現(xiàn)代 OJ 的「多組輸入直到 EOF」習(xí)慣去寫(xiě)樣例能過(guò)但評(píng)測(cè)時(shí)讀入邏輯不對(duì)。原因早期 NOIP 復(fù)賽是文件輸入輸出每題單獨(dú)指定輸入文件格式比如unhappy.in、peanuts.out和現(xiàn)在 OJ 的標(biāo)準(zhǔn)輸入輸出不同。這份 PDF 里沒(méi)有全部標(biāo)注文件名只給了問(wèn)題描述和樣例。如果按「鍵盤(pán)輸入屏幕輸出」寫(xiě)方向就錯(cuò)了。解決復(fù)現(xiàn)時(shí)先看題面里有沒(méi)有unhappy.in這種文件名標(biāo)記。有的話說(shuō)明是文件讀寫(xiě)代碼里要用open(unhappy.in, r)的方式讀入輸出寫(xiě)unhappy.out評(píng)測(cè)時(shí)才不會(huì)因?yàn)檎也坏轿募?。我已?jīng)不止一次在「老題新做」時(shí)栽在這個(gè)文件讀寫(xiě)上現(xiàn)在拿到題先看輸入輸出方式再看數(shù)據(jù)范圍最后才動(dòng)手寫(xiě)算法。6. 順手的小技巧按知識(shí)標(biāo)簽二次索引這份 PDF老題 PDF 的版面是按年份排的但刷題時(shí)很少有人真的按年份從頭刷到尾。我會(huì)花十幾分鐘做一張「知識(shí)點(diǎn)標(biāo)簽表」把每道題歸屬到算法類(lèi)型下之后想練哪塊就直奔對(duì)應(yīng)的題號(hào)。以這份 25 頁(yè) PDF 為例子大致可以這樣歸類(lèi)標(biāo)簽?zāi)攴荽硇灶}目適合階段枚舉 / 模擬1995方陣填數(shù)、豎式乘法入門(mén)字符串1996字符串編輯入門(mén)遞推1997 / 2002街道路徑、過(guò)河卒算法第一步搜索2002選數(shù)、單詞接龍?zhí)岣邉?dòng)態(tài)規(guī)劃2000 / 2004乘積最大、裝箱問(wèn)題、數(shù)字游戲進(jìn)階高精度1998 / 2003階乘求和、麥森數(shù)進(jìn)階圖論2002產(chǎn)生數(shù)、傳遞閉包提高有了這張表訓(xùn)練計(jì)劃就好排了第一周只做枚舉和模擬把 1995 到 1997 年的題過(guò)一遍第二周進(jìn)入遞推街道路徑和過(guò)河卒一起做第三周再碰搜索和高精度。標(biāo)簽表本身也可以程序化我習(xí)慣在復(fù)現(xiàn)時(shí)順手維護(hù)一個(gè) JSON 清單記錄每道題的編號(hào)、標(biāo)簽和復(fù)現(xiàn)狀態(tài)import json problems { 1995_binary: {tags: [枚舉], done: True, note: 注意等于0個(gè)數(shù)歸B}, 1996_string: {tags: [字符串, 模擬], done: True, note: I命令用rfind}, 2002_guohezu: {tags: [遞推, 高精度], done: False, note: 馬控制點(diǎn)含自身}, 2003_mersenne: {tags: [高精度, 快速冪], done: False, note: zfill(500)}, } print(json.dumps(problems, indent2, ensure_asciiFalse))這個(gè)小腳本每次刷完一題就更新?tīng)顟B(tài)過(guò)段時(shí)間回頭看哪些標(biāo)簽覆蓋得少一目了然。PDF 的價(jià)值不在于它有多少頁(yè)面而在于你能從里面挑出多少道值得反復(fù)做的題。我拿到一份新題集的第一件事永遠(yuǎn)是打標(biāo)簽從那以后幾乎沒(méi)再做過(guò)「打開(kāi)文件不知從哪刷起」的糾結(jié)。希望這份 25 頁(yè)的老題集也能成為你 Debug 路上的固定路標(biāo)幫到你。本文還有配套的精品資源點(diǎn)擊獲取