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