简介NOIP1995-2008年普及组复赛试题及解析以25页PDF形式整理成册面向备战信息学奥赛的初中生、中学生和编程初学者用于系统了解历年复赛题型、算法侧重点与常用解题策略。题目涵盖算式求解、方阵填数、二进制数分类、编码问题、灯的排列、乘法竖式、棋盘遍历、字符串编辑等经典内容既练习枚举、模拟、递推等基础算法也涉及数组、字符串等数据结构的应用还包含输入输出格式、边界条件等竞赛常见细节。整个资源包为单份PDF文件体积约352KB页面紧凑便于打印或按年份翻阅。已有306人学习使用说明其在普及组备赛场景中具备一定参考价值。通过学习完整赛题和配套解析读者可逐题理解编程思路与常见解法适合赛前集中刷题、查漏补缺也可作为信息学竞赛入门教学的补充材料。1. 一份 25 页的 NOIP 普及组复赛 PDF老题解析为什么还值得逐题过一遍对很多刚接触信奥的选手来说NOIP 普及组复赛的第一份训练材料往往不是最新的模拟卷而是一份 25 页、收录了 1995 到 2008 年历年复赛真题的 PDF。年份写的是上世纪九十年代题名却一直在刷存在感二进制数分类、方阵填数、字符串编辑、过河卒、麦森数——现在的普及组试卷里依然能找到它们的影子。这份 PDF 适合三种人第一次接触竞赛、想用老题打基础的初中生需要给学生安排限时训练的教练想快速补一遍枚举、递推、搜索、高精度这些基础算法却懒得翻题库的从业者。老题有一个新题很难替代的优势解析里直接写了「问题分析」等于把出题人的提示摆在桌面上。2. 把 1995-1999 拆成三类题枚举、递推与字符串模拟2.1 二进制数分类把题意翻译成循环的经典样例1995 年这道「二进制数分类」是全卷里最适合入门的第一题。题目规定将一个正整数转成二进制后如果 1 的个数多于 0 的个数就是 A 类数否则是 B 类数要求统计 1 到 1000 中两类数各有多少。这里有一个非常容易被忽略的边界题目说的是「多于」也就是 1 的个数等于 0 的个数时归为 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对每个数取二进制字符串统计 1 和 0 的个数后比较。关键参数是limit1000对应题目规定的统计范围bin(x)[2:]这一步决定了统计口径因为二进制表示不包含前导零例如 4 的二进制是1000 的个数算 2 个而不是 3 个。如果谁手滑按 8 位定长去统计答案会整个跑偏。这道题真正的训练价值不在算法而在「把自然语言描述精确翻译成程序逻辑」是典型的普及组第一题风格。2.2 字符串编辑D/I/R 三种命令的实现口径1996 年的字符串编辑题放在今天看依然是好题因为它把字符串处理的三类基本操作揉在一起还故意设置了几处「陷阱」D 命令删除第一次出现的字符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逻辑说明三点实现细节直接决定能否通过。第一find和rfind的差别对应 D 与 I 的不同要求第二replace默认替换全部匹配项所以 R 命令不需要手写循环第三字符串以.结尾时实际操作里一般保留这个结束符不做编辑避免把句号误删。我在复现时习惯把三个命令分别封装成函数再统一走一层 dispatch这样出问题时定位更快。参数注释里提到的target指的是题目里Ia1a2格式中的a1也就是插入位置的参照字符。2.3 Cantor 表与棋盘计数递推公式比模拟填表更稳1997 到 1999 年这三年的题目开始出现「规律题」Cantor 表的 Z 字形编号、棋盘中的正方形与长方形计数、比赛安排的循环赛程。这类题给新手最大的教训是不要一上来就照着题意模拟先花两分钟想公式。以 Cantor 表为例它是一张按斜线排列的有理数表编号沿 Z 字形走输入 N 最大到一千万如果真去逐项填表时间和内存都会爆。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: # 奇数斜线从下往上 return f{k - pos 1}/{pos} else: # 偶数斜线从上往下 return f{pos}/{k - pos 1}逻辑说明k是第几条斜线前k-1条斜线的项数总和是(k-1)*k//2用pos定位第 N 项在当前斜线的位置。斜线序号为奇数时分子递减分母递增偶数时相反。这里的时间复杂度是 O(sqrt(N))一千万的输入也只是毫秒级。同样的思路也用在棋盘计数题上正方形的个数是sum((n-s1)*(m-s1) for s in range(1, min(n,m)1))长方形总数用组合数C(n1,2)*C(m1,2)减去正方形个数直接套公式不需要枚举所有矩形。3. 2000-2004 开始上难度搜索、动态规划与高精度3.1 级数求和与选数精度和判重是第一道坎2002 年有两道题是典型的「看起来简单写起来翻车」级数求和和选数。级数求和本身只是算S_n 1 1/2 1/3 ... 1/n找到第一个大于 K 的 nK 不超过 15。但浮点误差在这里会咬人1/n累加几十万次之后误差可能让判断S_n K的时机偏一位。解析里特意提到 Pascal 时代用 Extended 比 Real 快放到现在我的习惯是直接开 double或者在判断处加一个极小阈值比如if total k 1e-12。选数题才是真正的分水岭。题目给 n 个不超过 500 万的整数选 k 个求和统计和为素数的方案数。n 最大 20意味着组合数上限是 C(20,10)184756DFS 完全可以扛住。但解析里直接点名了一个丢分点统计的是「和为素数的方案数」不是「不同的素数个数」比赛时有人做了判重反而丢了 12 分。另外1 不是素数这个特判必须在素数函数里写死。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逻辑说明递归参数start保证每次选的数在原序列中位置递增这是组合生成的标准写法既不会产生重复方案也不需要额外的 visited 数组。cur_sum在递归过程中维护当前和到深度 k 时统一判断。判断素数时只需要试除到sqrt(x)因为这道题里求和结果最大不超过一亿开根号后到一万循环代价很小。如果追求更快可以按解析的建议用筛选法预先生成 2 到 10000 的素数表再只拿素数去试除速度能提高五到六倍。3.2 过河卒与装箱问题递推和 01 背包的原型过河卒这道题在 NOIP 历史上反复出现1997 年普及组最后一题和 2002 年复赛题几乎一样。题目说卒只能向下或向右走棋盘上有马的控制点不能经过问从 (0,0) 到 (n,m) 有几条路径。解析里那句「要到达棋盘上的一个点只能从左边过来或是从上面下来」直接点破了递推本质到达某点的路径数等于到达其上方点和左方点的路径数之和。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) 是为了把马自己所在的位置也标记为控制点这是很多人第一次写时漏掉的细节。递推时按行优先遍历每个格子只依赖上方和左方所以空间可以优化成一维数组但普及组阶段用二维数组更直观。n 和 m 不超过 20答案最多 14 位Python 的 int 随便装当年 C 选手要开 Comp 类型或 long long这个细节解析里也提了。装箱问题则是 01 背包的裸题容量 v 不超过 20000n 不超过 30每个物品体积给定求最小剩余空间。状态方程就一行dp[j] max(dp[j], dp[j - w] w)最后输出v - dp[v]难度比过河卒还低但它是普及组第一次正面引入「背包」概念值得单独做一遍。3.3 麦森数与乘积最大高精度的两种打开方式2003 年的麦森数题要求计算2^P - 1的位数和最后 500 位数字P 可以到 310 万。这道题的高精度思路分两段位数用对数公式floor(P * log10(2)) 1不涉及大数计算后 500 位用快速幂取模模数取10^500只保留低 500 位。import math def mersenne_tail(P: int) - tuple[int, str]: digits int(P * math.log10(2)) 1 # 位数公式 mod 10 ** 500 last500 str((pow(2, P, mod) - 1) % mod) # 注意减 1 后可能缩位 return digits, last500.zfill(500)逻辑说明pow(2, P, mod)是 Python 内置的快速幂取模效率足够处理 P3100000。减 1 之后如果结果恰好小于 500 位zfill(500)会把高位补成 0对应题目「不足 500 位时高位补 0」的输出要求。位数公式的原理是2^P的十进制位数等于log10(2^P)向下取整加一也就是P * log10(2)的整数部分加一这个公式在原题样例里可以直接验证P1279 时输出 3861279 * 0.30103 ≈ 385.01取整加一就是 386。乘积最大就是另一类高精度长度为 N 的数字串插入 K 个乘号让乘积最大。N 最大 40K 最大 6区间 DP 的转移方程是dp[i][j] max(dp[t][j-1] * num(t1, i))其中dp[i][j]表示前 i 位数字放 j 个乘号的最大值num(l, r)表示原串第 l 到 r 位组成的整数。用 Python 实现时不需要手写高精度乘法内建 int 直接处理上百位的数字没有压力但换成 C/C 就必须自己写大数乘法这是很多人在考场上卡住的地方。4. 解析里藏着做题思路官方「问题分析」怎么读才不浪费4.1 把「问题分析」当提示器选数题的判重教训这份 PDF 最有价值的部分不是题目本身而是每道题下面那段「问题分析」。1995 到 2008 年的题目里官方在不少题解中直接写了算法选择的理由比如选数题的解析说「本题动态规划无从下手也无数学公式可寻看来只能搜索」紧跟着补了一句「1n20 这个约束条件也暗示我们本题搜索是有希望的」。这两句话合在一起就是在教你怎么根据数据范围判断算法看到 n 小于等于 20优先想搜索看到 n 到 40想 DP看到 N 到一千万想数学公式。我的使用习惯是先把题目抄下来自己写一遍写完再打开解析里的「问题分析」对答案。不是比谁的代码短而是看自己有没有漏掉判重、边界、精度这类易错点。选数题那句「比赛时就有很多同学胡乱判重而丢了 12 分还有 1 不是素数」就是典型的提示器——如果我先写完没想到这两点这一题就算白做了。4.2 两条被点破的算法思路产生数闭包与过河卒递推2002 年的产生数题解析给出了一个很干净的建模方式把数字变换规则看成有向图要求的就是每个数字经过任意次变换能变成多少种数字再用乘法原理把整个整数每一位的可变数乘起来。这个思路的关键是传递闭包——如果 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 # 每位数字不变也是一种选择 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]) # 每个数字能变成的数字个数含自身 return [sum(reach[i]) for i in range(10)]逻辑说明这个三重循环的复杂度是常数的因为数字只有 0 到 9 十种规则数最多 15 条所以整体开销极小。拿到每个数字的可变个数后把原整数每一位的可变数相乘就是答案。这个乘法可能产生几百位的数需要用高精度Python 的 int 可以无缝处理C 选手必须手写。过河卒的解析则更直接——「要到达棋盘上的一个点只能从左边过来或是从上面下来」这句话本质上就是在告诉你不要搜索用加法原理递推。我在第 3 章已经给出了递推代码这里想强调的是解析里类似的「一句话点破」非常多刷的时候不要只当答案看要把它当作出题人留下的解题路径。4.3 把解析当评测标准对比自己的实现差距「问题分析」还有一个用处是当基准线。我拿 1997 年的街道路径题做过一次自我对照自己先写的是记忆化搜索版本能出结果但代码长再看解析它直接用递推方程F[i,j]F[i-1,j]F[i,j-1]把问题压成二维表障碍区只是把对应格子置 0。两版对比后能明显感受到差距搜索是顺着题意走递推是顺着关系走。解析里那种「障碍区域用 2 对顶点坐标给出」的读题方式也提醒我一件事——题目描述里的边界条件往往不是摆设。类似的题目还有 1998 年的「1 到 9 分成三组组成 1:2:3 比例的三位数」解析的枚举思路是从最小的三位数开始试而不是从排列 9 个数字开始这两种写法的时间复杂度差了好几个量级。用解析对照自己的实现能清楚地看到差距出在「建模」还是「编码」而不是笼统地说「我太弱」。5. 复现这份资源的避坑清单五条血泪经验5.1 输出格式翻车麦森数补零、乒乓球空行现象代码逻辑全对样例输入也能跑出正确数字但提交评测时格式错误。最典型的是麦森数最后 500 位不足时没补前导零以及 2003 年乒乓球题输出两套比分之间漏了空行。原因麦森数的输出要求「每行输出 50 位共输出 10 行不足 500 位时高位补 0」很多人直接打印last500字符串长度不够就少了前导零。乒乓球题要求两部分结果之间有一个空行但样例输出在两行比分之间看起来只差一个换行肉眼不容易发现。解决我现在的习惯是凡是输出格式里带「补 0」「空行」「对齐」字样的题都先构造一个输出函数把格式全部收敛到函数内部。麦森数直接用zfill(500)再按每 50 位切一行乒乓球题把 11 分制和 21 分制的结果分别收集到列表里用\n\n.join(...)拼装这样空行逻辑只有一处。复现老题时逐字符比对输出样例永远值得多花两分钟。5.2 浮点误差在级数求和与 Cantor 表里冒头现象级数求和这道题K 给 15用float累加1/n到几十万项时total K的判断可能提前或延后触发导致输出的 n 和答案差 1。Cantor 表如果先算浮点数再转整数也可能在取整边界上偏一位。原因1/n在二进制浮点里不能精确表示累加误差会随 n 增大累积。Cantor 表的k*(k1)//2如果用浮点乘法再转 int大数精度会丢。解决级数求和把判断条件写成if total k 1e-12或者干脆用分数Fraction累加K 很小所以性能无所谓。Cantor 表的编号计算全程用整数运算k * (k 1) // 2不要写成int(k * (k 1) / 2)。这题吃过大亏之后我对所有「算位置编号」的题都默认整型运算优先。5.3 题目文本有 OCR 残字先对照题面再动手现象2001 年数的计数题题面写「茬它的左边加上一个自然数」这个「茬」字显然是「在」的扫描识别错误2004 年 FBI 树题面在 PDF 里被截断后半段构造逻辑只剩一半。原因这份 25 页 PDF 是早年纸质试题扫描或 OCR 转出来的个别年份排版和文字有残缺直接照题面写代码容易理解错。解决做这类老题前先花几十秒确认题面完整性。发现明显错字、缺行时用题目编号加关键词去对照在线题库的题面确认输入输出样例一致后再动手。解析里的「问题分析」是 PDF 独有的素材这部分通常没有 OCR 损坏可以放心读。我的经验是老题 PDF 适合用来练思路和刷算法不适合当作唯一题面来源。5.4 过河卒用搜索必超时数据范围暗示算法现象过河卒这道题n 和 m 不超过 20第一反应是 DFS 从起点搜到终点样例能过但 n 到 14、15 时递归分支爆炸稳超时。原因DFS 在无障碍棋盘上的路径数是组合数级别的20×20 的网格路径数已经有 14 位递归搜索会重复计算大量子问题。解析里特意写了「有些同学用了搜索当 n 到 14、15 左右就会超时」。解决看到「路径条数」四个字先想递推而不是搜索。F[i,j]F[i-1,j]F[i,j-1]的时间复杂度是 O(n*m)记忆化搜索虽然也能过但本质是同一个递推不如直接写迭代。这道题给我的教训是题目数据范围本身就是算法提示n20 可以搜索n200 必须 DP这个判断能力比背模板更重要。5.5 老题的评分分值和现代评测环境不对等现象2003 年之前的题目很多标注 30 分、40 分部分题没有给出完整的多组测试数据说明。新手按现代 OJ 的「多组输入直到 EOF」习惯去写样例能过但评测时读入逻辑不对。原因早期 NOIP 复赛是文件输入输出每题单独指定输入文件格式比如unhappy.in、peanuts.out和现在 OJ 的标准输入输出不同。这份 PDF 里没有全部标注文件名只给了问题描述和样例。如果按「键盘输入屏幕输出」写方向就错了。解决复现时先看题面里有没有unhappy.in这种文件名标记。有的话说明是文件读写代码里要用open(unhappy.in, r)的方式读入输出写unhappy.out评测时才不会因为找不到文件而失败。我已经不止一次在「老题新做」时栽在这个文件读写上现在拿到题先看输入输出方式再看数据范围最后才动手写算法。6. 顺手的小技巧按知识标签二次索引这份 PDF老题 PDF 的版面是按年份排的但刷题时很少有人真的按年份从头刷到尾。我会花十几分钟做一张「知识点标签表」把每道题归属到算法类型下之后想练哪块就直奔对应的题号。以这份 25 页 PDF 为例子大致可以这样归类标签年份代表性题目适合阶段枚举 / 模拟1995方阵填数、竖式乘法入门字符串1996字符串编辑入门递推1997 / 2002街道路径、过河卒算法第一步搜索2002选数、单词接龙提高动态规划2000 / 2004乘积最大、装箱问题、数字游戏进阶高精度1998 / 2003阶乘求和、麦森数进阶图论2002产生数、传递闭包提高有了这张表训练计划就好排了第一周只做枚举和模拟把 1995 到 1997 年的题过一遍第二周进入递推街道路径和过河卒一起做第三周再碰搜索和高精度。标签表本身也可以程序化我习惯在复现时顺手维护一个 JSON 清单记录每道题的编号、标签和复现状态import json problems { 1995_binary: {tags: [枚举], done: True, note: 注意等于0个数归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))这个小脚本每次刷完一题就更新状态过段时间回头看哪些标签覆盖得少一目了然。PDF 的价值不在于它有多少页面而在于你能从里面挑出多少道值得反复做的题。我拿到一份新题集的第一件事永远是打标签从那以后几乎没再做过「打开文件不知从哪刷起」的纠结。希望这份 25 页的老题集也能成为你 Debug 路上的固定路标帮到你。本文还有配套的精品资源点击获取