1 版本与来源
本篇依据《全国青少年信息学奥林匹克系列竞赛大纲(2025 年修订版)》,作为本书的阅读索引和编写参考。官方范围与本文的教学安排分别说明;具体条目以官方原文为准。
| 项目 | 记录 |
|---|---|
| 大纲版本 | 2025 年修订版 |
| 官方发布日期 | 2025 年 4 月 18 日 |
| 本次核对日期 | 2026 年 11 月 18 日 |
| NOIP 对应级别 | 提高级,同时包含入门级内容 |
截至本次核对,查到的最新正式版本仍为 2025 年修订版。2026 年的官方通知也继续引用这一版本,不应把它改称“2026 年修订版”。官方发布说明、2026 年官方通知
原文入口:官方大纲 PDF。PDF 为双页排版,阅读器的页序号与页面底部印刷页码不同。
| 查阅内容 | PDF 页序号 | 印刷页码 |
|---|---|---|
| 级别划分与使用原则 | 第 7—8 页 | 第 4—7 页 |
| 入门级 | 第 9—14 页 | 第 9—18 页 |
| 提高级 | 第 14—17 页 | 第 19—25 页 |
| NOI 级 | 第 18—20 页 | 第 26—31 页 |
2 范围与级别
大纲将内容分为入门级、提高级和 NOI 级,高级别包含低级别的内容。CSP-J 对应入门级,NOIP 与 CSP-S 对应提高级,NOI 及以上活动对应 NOI 级。见原文第 4—5 页。
每个知识点另有
例如,树链剖分、分块列在 NOI 级;官方《NOIP 2025 题目综合分析报告》也列出了它们在相关解法中的使用。因此,分级适合安排学习基础,不能据此断言某种技术绝不会出现在 NOIP 的题解中。官方分析报告
下文按主题归纳范围,不逐项转录大纲。矩阵快速幂、换根 DP 等具体教学安排,是本书对相关主题的展开。
3 入门基础
提高级学习以这些内容为前提,不能因为已经开始线段树、Tarjan,就跳过基础。
| 板块 | 学习重点 |
|---|---|
| 程序设计 | 数据类型、运算与控制结构、数组、字符串、函数与递归、结构体、指针与引用、文件读写、常用 STL。 |
| 数据结构 | 链表、栈、队列;树与二叉树、遍历和存储;堆、哈夫曼树、二叉搜索树;图的基本表示。 |
| 基本方法 | 枚举、模拟、贪心、递推、递归、二分、倍增、前缀和与差分。 |
| 排序与搜索 | 基础排序、计数排序、DFS、BFS、连通区域搜索。 |
| 动态规划 | 状态与转移、简单线性 DP、背包、简单区间 DP。 |
| 数学与数值 | 进制、整除与取模、GCD、质因数与筛法、排列组合、杨辉三角、高精度四则运算。 |
4 提高重点
以下板块对应官方大纲第 19—25 页。表中把相近条目合并,便于查阅。
4.1 环境与 C++
需要能够在 Linux 中管理文件、编辑、编译、运行和调试程序。除熟悉常见容器外,还要掌握迭代器、关联容器、双端队列、优先队列和 bitset 等工具。
类的简单使用、成员函数和运算符重载也属于提高级内容。本书以算法为主,语言与环境基础可另设配套文章。
4.2 数据结构
重点包括并查集、单调队列、堆、ST 表、树状数组、线段树、Trie、笛卡尔树与平衡树,以及哈希函数和冲突处理。
哈希表与字符串哈希需要分清:前者还涉及键的存取与冲突解决;后者通常把字符串映射为数值,再用于比较或检索。只有字符串哈希一篇,不能代替完整的哈希表教学。
4.3 分治与搜索
分治需要讲清如何拆分问题、递归求解和合并结果,并分析时间与空间成本。
搜索部分除 DFS、BFS 外,还包括剪枝、记忆化、启发式、双向 BFS 和迭代加深。折半搜索与双向 BFS 的状态组织和使用条件不同,不能互相替代。
排序还应覆盖归并、快速排序、堆排序、桶排序和基数排序。
4.4 图与树
重点包括最小生成树、单源最短路与次短路、Floyd、拓扑排序、欧拉路、二分图判定、强连通分量、割点与割边。
树上基础包括重心、直径、DFS 序与欧拉序、树上差分、子树信息、倍增和 LCA。
二分图判定与二分图最大匹配是不同层次的问题:前者列在提高级,匈牙利算法列在 NOI 级。
4.5 动态规划
提高级明确列出多维 DP、树形 DP、状态压缩 DP 和常用优化。入门级已包含简单区间 DP。
本书宜先建立线性、区间、树形、集合状态等基本模型,再学习如何优化转移。不能用斜率优化、四边形不等式等文章代替基础模型的讲解。
4.6 数学
数论需要从同余关系推进到欧拉函数与欧拉定理、费马小定理、威尔逊定理、裴蜀定理、逆元、扩欧和中国剩余定理。
组合数学需要理解多重集、等价类、错排、圆排列、鸽巢原理、二项式定理、容斥和 Catalan 数。
线性代数包括向量与矩阵的基本运算、矩阵变换和高斯消元。初高中代数与几何也是基础要求,不能把“数学”仅理解为数论。
5 本书对照
以下为 2026 年 11 月 18 日的人工核对记录,以当时目录登记的 198 篇文章及相关正文为依据。新增本篇后,目录数会随之变化。
“已有内容”表示能找到相关讲解,不表示所有文章的完整程度相同;只有题单、提纲、空标题或 TODO,不计为主题已经完成。下表不会随新文章自动更新。
5.1 已有内容
| 板块 | 本书入口 |
|---|---|
| 基础方法 | 前缀和、差分、双指针、二分记账法与二分答案、离散化 |
| 搜索 | 广度优先搜索(BFS):从迷宫到最少步数、0-1 BFS:用双端队列求最小代价、折半搜索 |
| DP | 连续段DP、状态机DP、最长上长子序列、最长公共子序列及背包系列 |
| 常用结构 | 并查集、st表、树状数组基础、线段树基础 |
| 图论 | dijkstra、Floyd 全源最短路、拓扑排序、最小生成树、欧拉路与欧拉回路 |
| 连通性 | 强连通分量(Tarjan)、图的割点、图的割边、点双连通分量、边双连通分量 |
| 树 | 树的直径、树的重心、DFS序、树上差分、爬树法求 LCA(倍增) |
| 字符串 | 字符串哈希:进制哈希法、KMP 字符串匹配:只记一个状态转移、Manacher:线性时间最长回文子串、Trie 字典树 |
| 计数 | 排列与组合、容斥原理、Catalan数 |
记忆化搜索在 数字金字塔 中已有实例;单调队列优化在 多重背包 中已有讲解,不应将它们误记为完全缺失。
5.2 需要完善
| 主题 | 当前情况 | 后续工作 |
|---|---|---|
| 状压DP | 正文基本只有 TODO。 |
补位集合表示、状态含义、枚举与转移、完整例题。 |
| exgcd | 只有标题,缺少推导和实现。 | 补裴蜀定理、递归回代、通解和边界。 |
| 素数 | 欧拉筛未编写。 | 补两种筛法的实现、正确性和复杂度。 |
| 高精度 | 只接入加法,其余运算文件为空。 | 补减法、乘法、除以普通整数及余数处理。 |
| 深度优先搜索 | 以教学提纲为主。 | 补状态设计、恢复现场、完整例题和剪枝。 |
| quickSort | 已有代码和部分讨论,仍有未完成段落。 | 补完整原理、边界和退化分析。 |
| 数论专题 | 欧拉函数、费马小定理、逆元等散在笔记或代码中。 | 整理成独立、连续的学习路线。 |
5.3 需要新建
| 主题 | 当前缺口与编写方向 |
|---|---|
| 树形 DP | 依赖背包、基环树中已有应用,缺少统一入门。先讲子树状态与儿子合并,再接树上背包和换根。 |
| 区间 DP | 已有优化文章,但缺少基础教学。先讲区间状态、最后一次合并、分割点和枚举顺序。石子合并的独立文章也需补正文。 |
| 分治与归并 | 需要从拆分、合并和复杂度讲起,用归并排序及逆序对贯穿。 |
| 复杂度分析 | 各篇分别分析,缺少统一基础。应讲循环、递归、空间和均摊分析。 |
| 二分图判定 | 缺少完整的染色法、奇环解释和非连通图处理。 |
| 搜索优化 | 剪枝、双向 BFS、迭代加深与启发式搜索缺少系统讲解。 |
| 矩阵与高斯消元 | 缺少矩阵运算、快速幂与递推加速、线性方程组求解。 |
| 笛卡尔树 | 缺少与单调栈的联系、线性构造和区间性质。 |
| 哈夫曼树 | 贪心概览中仅作简述,需要补最优合并、证明与编码。 |
| 基础链表 | 缺少单链表、双向链表、循环链表及数组模拟。 |
| 哈希表 | 需补数值哈希、键的存取与冲突解决方法。 |
| 排序 | 除快速排序外,还需补基础排序、归并、堆排序、桶与基数排序。 |
| 组合数学补充 | 错排、鸽巢原理和二项式定理需形成完整讲解;现有文章中的提及不能替代专题。 |
6 编写顺序
以下是本书的编写安排建议,不是官方规定的教学顺序。
- 树形 DP。
- 区间 DP。
- 补完状态压缩 DP。
- 分治与归并排序。
- 二分图判定。
- 补完扩欧,接着编写乘法逆元。
- 矩阵与矩阵快速幂。
- 高斯消元。
- 搜索剪枝。
- 哈夫曼树。
数论可按“质因数分解 → 裴蜀与扩欧 → 同余方程 → 逆元 → 费马与欧拉定理 → 中国剩余定理”整理。线性代数则先补矩阵基础,再进入快速幂和消元。
7 后续拓展
网络流、二分图匹配、2-SAT、后缀数组、概率与期望、SG 函数等,在该版大纲中列于 NOI 级。可以另设进阶路线,安排在基础缺口之后。
数位 DP、差分约束、圆方树也值得编写,但没有在提高级部分单独列名。应将它们标为本书选择的应用模型或扩展,避免写成“大纲逐项明确要求”。
本书已有 树链剖分(HLD)、分块思想、可持久化线段树、AC 自动机:多模式串匹配 等进阶内容。后续编写时,应同时补足它们依赖的基础。
8 维护记录
| 日期 | 记录 |
|---|---|
| 2026-11-18 | 核对 2025 年修订版官方大纲,建立范围索引与本书对照。 |
官方发布新版本后,先更新版本、来源和核对日期,再检查知识点的分级变化。每完成一篇待补文章,将对应记录改为站内链接,并复核是否已经形成完整教学内容。