CCF NOI · 2025年修订版

全国青少年信息学奥林匹克
竞赛大纲

入门级 · 提高级 · NOI级 · 点击切换级别与分类

🖥️ 基础知识与编程环境

入门级 · 难度系数 1~5

💻
2.1.1-A
计算机基础
  • 计算机基本构成1
  • CPU · 内存 · I/O设备
  • 操作系统基本概念及常见操作1
  • Windows · Linux
  • 计算机网络和Internet的基本概念1
  • 计算机的历史和常见用途1
  • NOI以及相关活动的历史与规则1
  • 位、字节与字1
  • 程序设计语言及程序编译运行基本概念1
⚙️
2.1.1-B
开发环境
  • 图形界面文件操作1
  • 新建·复制·删除·移动文件或目录
  • Windows系统集成开发环境1
  • Dev-C++ 等
  • Linux系统集成开发环境1
  • Code::Blocks 等
  • 常用编译命令 g++ 的基本使用1

💻 C++ 程序设计

入门级 · 难度系数 1~5

📝
2.1.2-A
程序基本概念
  • 标识符·关键字·常量·变量·字符串·表达式1
  • 常量与变量的命名·定义及作用1
  • 头文件与名字空间的概念2
  • 编辑·编译·解释·调试的概念2
📦
2.1.2-B
基本数据类型
  • 整数型:int · long long1
  • 实数型:float · double1
  • 字符型:char1
  • 布尔型:bool1
📋
2.1.2-C
程序基本语句
  • cin · scanf · cout · printf2
  • 赋值语句·复合语句2
  • if语句·switch语句·多层条件语句2
  • for · while · do while 语句2
  • 多层循环语句3
🔢
2.1.2-D
基本运算
  • 算术运算:加减乘除整除求余1
  • 关系运算:> · >= · < · <= · == · !=1
  • 逻辑运算:与(&&) · 或(||) · 非(!)1
  • 变量自增与自减运算1
  • 三目运算1
  • 位运算:& · | · ~ · ^ · << · >>2
📐
2.1.2-E
数学库函数
  • 绝对值·四舍五入·下取整·上取整3
  • 平方根函数3
  • 常用三角函数3
  • 对数函数·指数函数3
🏗️
2.1.2-F
结构化程序设计
  • 顺序结构·分支结构·循环结构1
  • 自顶向下·逐步求精的模块化程序设计2
  • 流程图的概念及流程图描述2
📊
2.1.2-G
数组与字符串
  • 数组与数组下标1
  • 数组的读入与输出1
  • 二维数组与多维数组3
  • 字符数组与相关函数2
  • string类与相关函数2
⚙️
2.1.2-H
函数与递归
  • 函数定义与调用·形参与实参2
  • 传值参数与传引用参数3
  • 常量与变量的作用范围2
  • 递归函数2
🏛️
2.1.2-I
结构体·指针·STL
  • 结构体3
  • 联合体3
  • 指针4
  • 基于指针的数组访问·字符指针·结构体指针
  • 引用5
  • 文件基本读写与重定向2
  • STL常用函数:min·max·swap·sort3
  • STL容器:stack·queue·list·vector4

🗂️ 数据结构

入门级 · 难度系数 3~5

📏
2.1.3-A
线性结构
  • 链表:单链表·双向链表·循环链表3
  • 栈3
  • 队列3
🌳
2.1.3-B
简单树
  • 树的定义与相关概念3
  • 树的表示与存储4
  • 二叉树的定义与基本性质3
  • 二叉树的表示与存储4
  • 二叉树的遍历:前序·中序·后序4
⭐
2.1.3-C
特殊树
  • 完全二叉树的定义与基本性质4
  • 完全二叉树的数组表示法4
  • 哈夫曼树的定义·构造·哈夫曼编码4
  • 二叉搜索树的定义和构造4
🕸️
2.1.3-D
简单图
  • 图的定义与相关概念3
  • 图的表示与存储:邻接矩阵4
  • 图的表示与存储:邻接表4

⚡ 算法

入门级 · 难度系数 1~5

📝
2.1.4-A
算法概念与描述
  • 算法概念1
  • 算法描述:自然语言·流程图·伪代码2
🔰
2.1.4-B
入门算法
  • 枚举法1
  • 模拟法1
🔧
2.1.4-C
基础算法
  • 贪心法3
  • 递推法3
  • 递归法4
  • 二分法4
  • 倍增法4
🎯
2.1.4-D
算法策略
  • 前缀和3
  • 差分4
🔢
2.1.4-E
数值处理算法
  • 高精度加法4
  • 高精度减法4
  • 高精度乘法4
  • 高精度整数除以单精度整数的商和余数4
🔃
2.1.4-F
排序算法
  • 排序的基本概念3
  • 冒泡排序3
  • 选择排序3
  • 插入排序3
  • 计数排序3
🔍
2.1.4-G
搜索算法
  • 深度优先搜索 DFS5
  • 广度优先搜索 BFS5
🕸️
2.1.4-H
图论算法
  • 深度优先遍历4
  • 广度优先遍历4
  • 泛洪算法(Flood Fill)5
📈
2.1.4-I
动态规划
  • 动态规划的基本思路4
  • 简单一维动态规划4
  • 简单背包类型动态规划5
  • 简单区间类型动态规划5

📐 数学与其他

入门级 · 难度系数 1~5

🔢
2.1.5-A
数及其运算
  • 自然数·整数·有理数·实数及算术运算1
  • 进制与进制转换1
  • 二进制·八进制·十进制·十六进制
📏
2.1.5-B
初等数学
  • 代数(初中部分)1
  • 几何(初中部分)1
🔬
2.1.5-C
初等数论
  • 整除·因数·倍数·指数·质(素)数·合数3
  • 取整3
  • 模运算与取余3
  • 整数唯一分解定理3
  • 辗转相除法(欧几里得算法)3
  • 素数筛法:埃氏筛法与线性筛法4
🎲
2.1.5-D
离散与组合数学
  • 集合2
  • 加法原理2
  • 乘法原理2
  • 排列4
  • 组合4
  • 杨辉三角4
  • ASCII码2

🖥️ 基础知识与编程环境

提高级 · 难度系数 5~8

🐧
2.2.1
Linux 开发环境
  • Linux系统终端常用文件与目录操作命令5
  • Linux系统常见文本编辑工具的使用5
  • 常用编译命令g++与相关编译选项5
  • 在Linux系统终端中运行程序,使用time命令查看程序用时5
  • 调试工具 GDB 的使用5

💻 C++ 程序设计

提高级 · 难度系数 5~8

🧱
2.2.2-A
类(class)
  • 类的概念及简单应用6
  • 成员函数和运算符重载6
📚
2.2.2-B
STL 模板(进阶)
  • 容器(container)和迭代器(iterator)5
  • 对(pair)· 元组(tuple)5
  • 集合(set)· 多重集合(multiset)5
  • 双端队列(deque)· 优先队列(priority_queue)5
  • 映射(map)· 多重映射(multimap)5
  • 位集合(bitset)5
  • 算法模板库中的常用函数5

🗂️ 数据结构

提高级 · 难度系数 5~8

📏
2.2.3-A
线性结构(进阶)
  • 双端栈5
  • 双端队列5
  • 单调队列5
  • 优先队列6
  • ST表(Sparse Table)6
🌲
2.2.3-B
集合与森林
  • 并查集6
  • 树的孩子兄弟表示法6
⭐
2.2.3-C
特殊树(进阶)
  • 二叉堆6
  • 树状数组6
  • 线段树6
  • 字典树(Trie)6
  • 笛卡尔树7
  • 平衡树:AVL · Treap · Splay 等8
🕸️
2.2.3-D
常见图
  • 稀疏图5
  • 偶图(二分图)6
  • 欧拉图6
  • 有向无环图(DAG)6
  • 连通图与强连通图7
  • 双连通图7
#️⃣
2.2.3-E
哈希表
  • 数值哈希函数构造5
  • 字符串哈希函数构造6
  • 哈希冲突的常用处理方法6

⚡ 算法

提高级 · 难度系数 5~8

⏱️
2.2.4-A
复杂度分析
  • 时间复杂度分析6
  • 空间复杂度分析6
🎯
2.2.4-B
算法策略
  • 离散化6
  • 扫描线7
  • 分治算法6
🔃
2.2.4-C
排序算法(进阶)
  • 归并排序5
  • 快速排序5
  • 堆排序6
  • 桶排序5
  • 基数排序6
🔤
2.2.4-D
字符串算法
  • 字符串匹配:KMP算法6
  • Manacher算法7
🔍
2.2.4-E
搜索算法(进阶)
  • 搜索的剪枝优化6
  • 记忆化搜索6
  • 启发式搜索7
  • 双向广度优先搜索7
  • 迭代加深搜索7
🕸️
2.2.4-F
图论算法(进阶)
  • 最小生成树:Prim · Kruskal6
  • 单源最短路:Bellman-Ford · Dijkstra · SPFA6
  • 单源次短路7
  • Floyd-Warshall算法6
  • 有向无环图的拓扑排序6
  • 欧拉道路和欧拉回路6
  • 二分图的判定6
  • 强连通分量7
  • 割点·割边7
  • 树的重心·直径·DFS序与欧拉序6
  • 树上差分·子树和与倍增6
  • 最近公共祖先(LCA)6
📈
2.2.4-G
动态规划(进阶)
  • 多维动态规划6
  • 树型动态规划6
  • 状态压缩动态规划7
  • 动态规划的常用优化8

📐 数学与其他

提高级 · 难度系数 5~8

📏
2.2.5-A
初等数学
  • 代数(高中部分)5
  • 几何(高中部分)6
🔬
2.2.5-B
初等数论(进阶)
  • 同余式5
  • 欧拉定理和欧拉函数7
  • 费马小定理7
  • 威尔逊定理7
  • 裴蜀定理7
  • 模运算意义下的逆元7
  • 扩展欧几里得算法7
  • 中国剩余定理7
🎲
2.2.5-C
离散与组合数学(进阶)
  • 多重集合6
  • 等价关系与等价类6
  • 多重集上的排列·组合6
  • 错排列·圆排列6
  • 鸽巢原理6
  • 二项式定理6
  • 容斥原理7
  • 卡特兰(Catalan)数7
🔷
2.2.5-D
线性代数
  • 向量与矩阵的概念5
  • 向量的运算6
  • 矩阵的初等变换6
  • 矩阵的运算:加减乘法与转置6
  • 特殊矩阵:单位阵·三角阵·对称阵·稀疏矩阵6
  • 高斯消元法7

💻 C++ 程序设计

NOI级 · 难度系数 7~10

🧱
2.3.1
面向对象程序设计思想(OOP)
  • 面向对象的程序设计思想(OOP)8

🗂️ 数据结构

NOI级 · 难度系数 8~10

📏
2.3.2-A
线性结构(NOI)
  • 块状链表8
🌲
2.3.2-B
复杂树
  • 树链剖分8
  • 动态树(LCT)10
  • 树套树9
  • k-d树9
  • 虚树8
⛰️
2.3.2-C
可合并堆
  • 左偏树8
  • 二项堆10
⏳
2.3.2-D
可持久化数据结构
  • 可持久化线段树8
  • 其他可持久化数据结构9

⚡ 算法

NOI级 · 难度系数 8~10

🎯
2.3.3-A
算法策略(NOI)
  • 分块8
  • 离线处理思想8
  • 复杂分治思想9
  • 平衡规划思想9
  • 构造思想9
🔤
2.3.3-B
字符串算法(NOI)
  • 扩展KMP算法8
  • 有穷自动机的概念8
  • AC自动机8
  • 后缀数组8
  • 后缀树9
  • 后缀自动机10
🕸️
2.3.3-C
图论算法(NOI)
  • 基环树8
  • 最小树形图10
  • 2-SAT8
  • 网络流8
  • 图的支配集·独立集·覆盖集10
  • 匈牙利算法8
  • KM算法10
  • 一般图的匹配10
📈
2.3.3-D
动态规划(NOI)
  • 复杂动态规划模型的构建9
  • 复杂动态规划模型的优化9

📐 数学与其他

NOI级 · 难度系数 8~10

🔬
2.3.4-A
初等数论(NOI)
  • 原根和指数8
  • 大步小步算法(BSGS)8
  • 狄利克雷(Dirichlet)卷积9
  • 二次剩余10
  • 二次同余式10
🎲
2.3.4-B
离散与组合数学(NOI)
  • 群及其基本性质9
  • 置换群与循环群9
  • 母函数9
  • 莫比乌斯反演9
  • Burnside引理与Pólya定理9
  • 斯特林(Stirling)数9
  • 无根树的Prüfer序列9
🔷
2.3.4-C
线性代数(NOI)
  • 逆矩阵9
  • 行列式9
  • 向量空间与线性相关9
  • 基与线性基9
∫
2.3.4-D
高等数学
  • 多项式函数的微分8
  • 多项式函数的积分8
  • 泰勒(Taylor)级数10
  • 快速傅里叶变换(FFT)10
🎰
2.3.4-E
概率论
  • 概率的基本概念8
  • 离散随机变量的期望与方差9
  • 条件概率9
  • 贝叶斯公式9
♟️
2.3.4-F
博弈论
  • 尼姆(Nim)博弈9
  • SG函数9
📐
2.3.4-G
计算几何
  • 点·线·面之间位置关系的判定8
  • 一般图形面积的计算8
  • 二维凸包8
  • 半平面交9
📡
2.3.4-H
信息论与最优化
  • 熵·互信息·条件熵·相对熵10
  • 信息复杂度的概念10
  • 描述复杂度的概念10
  • 通讯复杂度的概念10
  • 单纯形法10