NOIP 考纲参考

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 页。

每个知识点另有 1∼101\sim10 的学习难度系数。级别与难度系数不是同一件事:提高级新增内容的难度系数主要在 5∼85\sim8,但 NOI 级中也有系数为 88 的内容。不能只按数字判断它是否属于提高级。

例如,树链剖分、分块列在 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 编写顺序

以下是本书的编写安排建议,不是官方规定的教学顺序。

  1. 树形 DP。
  2. 区间 DP。
  3. 补完状态压缩 DP。
  4. 分治与归并排序。
  5. 二分图判定。
  6. 补完扩欧,接着编写乘法逆元。
  7. 矩阵与矩阵快速幂。
  8. 高斯消元。
  9. 搜索剪枝。
  10. 哈夫曼树。

数论可按“质因数分解 → 裴蜀与扩欧 → 同余方程 → 逆元 → 费马与欧拉定理 → 中国剩余定理”整理。线性代数则先补矩阵基础,再进入快速幂和消元。

7 后续拓展

网络流、二分图匹配、2-SAT、后缀数组、概率与期望、SG 函数等,在该版大纲中列于 NOI 级。可以另设进阶路线,安排在基础缺口之后。

数位 DP、差分约束、圆方树也值得编写,但没有在提高级部分单独列名。应将它们标为本书选择的应用模型或扩展,避免写成“大纲逐项明确要求”。

本书已有 树链剖分(HLD)、分块思想、可持久化线段树、AC 自动机:多模式串匹配 等进阶内容。后续编写时,应同时补足它们依赖的基础。

8 维护记录

日期 记录
2026-11-18 核对 2025 年修订版官方大纲,建立范围索引与本书对照。

官方发布新版本后,先更新版本、来源和核对日期,再检查知识点的分级变化。每完成一篇待补文章,将对应记录改为站内链接,并复核是否已经形成完整教学内容。