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