全国青少年信息学奥林匹克系列
竞赛大纲
一、简介
2021 年 4 月,全国青少年信息学奥林匹克竞赛大纲在 NOI 官网发布。为方便大家的查阅和收藏,我们把大纲的入门级、提高级和 NOI 级整理了出来。
二、大纲
2.1 入门级
2.1.1 计算机基础与编程环境
1.【1】计算机的基本构成(CPU、内存、I/O 设 备等)
2.【1】Windows、 Linux 等操作系统的基本概念及其常见操作
3.【1】计算机网络和 Internet 的基本概念
4.【1】计算机的历史及其在现代社会中的常见应用
5.【1】 NOI 以及相关活动的历史
6.【1】进制的基本概念与进制转换、字节与字
7.【1】程序设计语言以及程序编译和运行的基本概念
8.【1】使用图形界面新建、复制、删除、移动文件或目录
9.【1】使用 Windows 系统下的集成开发环境(例如 Dev C++等)
10.【1】使用 Linux 系统下的集成开发环境(例如 Code::Blocks 等)
11.【1】g++、gcc 等常见编译器的基本使用
【X】表示难度系数
2.1.2 C++程序设计 1
1.程序基本概念
•【1】标识符、关键字、常量、变量、字符串、 表达式的概念
•【1】常量与变量的命名、定义及作用
•【2】头文件与名字空间的定义与理解
•【2】编辑、编译、解释、调试等概念理解
2.基本数据类型
•【1】整数型:int, long long
•【1】实数型:float, double
•【1】字符型:char
•【1】布尔型:bool
3.程序基本语句
•【2】cin 语句,scanf 语句,cout 语句,printf 语句,赋值语句,复合语句
•【2】if 语句,switch 语句,多层条件语句
•【2】for 语句,while 语句,do while 语句
•【3】多层循环语句
4.基本运算
•【1】算数运算:加、减、乘、除、整除、求余
•【1】关系运算:大于,大于等于,小于,小于等于,等于,不等于
•【1】逻辑运算:与(&&)、或(||)、非(!)
•【1】变量自增与自减运算
•【1】三目运算
•【3】位运算:与(&)、或(|)、非(~)、 异或(^)、左移、右移
5.数学库常用函数
•【3】绝对值函数,四舍五入函数,取上整函数, 取下整函数,常用三角函数,对数函数,指数 函数,平方根函数
6.结构化程序设计
•【1】顺序结构、分支结构和循环结构
•【2】自顶向下、逐步求精的模块化程序设计
•【2】流程图的概念及流程图描述
7.数组
•【1】数组定义,数组与数组下标的含义
•【1】数组的读入与输出
•【2】纯一维数组的综合运用
•【3】纯二维数组与多维数组的综合应用
8.字符串的处理
•【2】字符数组与字符串的关系
•【2】字符数组的综合应用
•【2】string 类定义、相关函数引用
•【3】string 类的综合应用
9.函数与递归
•【2】函数定义与调用,形参与实参
•【3】传值参数与传引用参数
•【2】常量与变量的作用范围
•【2】递归函数的概念、定义与调用
10.结构体类型
•【3】结构体的定义及应用
11.指针类型
•【4】指针的概念及调用
•【4】指针与数组
•【4】字符指针与 string 类
•【4】指向结构体的指针
12.文件及基本读写
•【2】文件的基本概念,文本文件的基本操作
•【2】文本文件类型与二进制文件类型
•【2】文件重定向、文件读写等操作
13.STL 模板应用
•【3】 中 sort 函数
•【4】 栈(stack)、 队列(queue)、链表(list)、向量(vector)等容器
1C++以外的其他高级程序设计语言可参照本部分内容。
2.1.3 数据结构
1.线性表
•【3】链表:单链表、双向链表、循环链表
•【3】栈
•【3】队列
2.简单树
•【3】树的定义及其相关概念
•【4】树的父亲表示法
•【3】二叉树的定义及其基本性质
•【4】二叉树的孩子表示法
•【4】二叉树的遍历:前序、中序、后序遍历
3.特殊树
•【4】完全二叉树的定义与基本性质
•【4】完全二叉树的数组表示法
•【4】哈夫曼树的定义、构造及其遍历
•【4】二叉树的定义、构造及其遍历
4.简单图
•【3】图的定义及其相关概念
•【4】图的邻接矩阵存储
•【4】图的邻接表存储
2.1.4 算法
1.算法概念与描述
•【1】算法概念
•【2】算法描述:自然语言描述、流程图描述、伪代码描述
2.入门算法
•【1】枚举法
•【1】模拟法
3.基础算法
•【3】贪心法
•【3】递推法
•【4】递归法
•【4】二分法
•【4】倍增法
4.数值处理算法
•【4】高精度的加法
•【4】高精度的减法
•【4】高精度的乘法
•【4】求高精度整数除以单精度整数的商和余数
5.排序算法
•【3】排序的基本概念(稳定性等)
•【3】冒泡排序
•【3】简单选择排序
•【3】简单插入排序
6.图论算法
•【4】图的深度优先遍历算法
•【4】图的宽度优先遍历算法
•【5】洪水填充算法(floodfill)
7.动态规则
•【4】动态规划的基本思路
•【4】简单一维动态规划
•【5】简单背包类型动态规划
•【5】简单区间类型动态规划
2.1.5 数学
1.数及其运算
•【1】数的概念,算术运算(加、减、乘、除、求余)
•【1】数的进制:二进制、八进制、十六进制和十进制及其转换
•【2】编码:ASCII 码,哈夫曼编码,格雷码
2.初中数学
•【1】初中代数
•【1】初中平面几何
3.初等数论
•【3】整除、因数、倍数、指数、质数、合数、同余等概念
•【3】唯一分解定理
•【3】欧几里得算法(辗转相除法)
•【4】埃氏筛法和线性筛法求素数
4.组合数学
•【2】加法原理
•【2】乘法原理
•【4】排列及计算公式
•【4】组合及计算公式
•【4】杨辉三角公式
2.2 提高级
2.2.1 计算机基础与编程环境
1.【5】在 Linux 系统终端中使用 mkdir、cp、rm、mv 等命令新建、复制、删除、移动文件或目录
2.【5】在 Linux 系统终端中使用 cd、pwd、ls 等命令更改、显示目录路径和查看目录中的文件
3.【5】在 Linux 系统下使用 Gedit、Vim 或 Emacs 等文本编辑工具编写代码
4.【5】熟悉 g++、gcc 等编译器以及优化、数学库等常见编译选项
5.【5】在 Linux 系统终端中运行程序,并使用 time 命令查看程序用时(区分 real time、sys time 和 user time)
6.【5】了解调式工具 gdb 及其 break、display、continue、step 等命令
2.2.1 C++程序设计 2
1.类(class)
•【6】类的概念及简单应用
•【6】成员函数和运算符重载
2.STL 模板
•【5】集合(set)
•【5】列表(list),双端队列(deque),优先队列(priority_queue)
•【5】多重集合(multiset)
•【5】映射(map),多重映射(multimap)
•【5】对(pair),元组(tuple)
2C++以外的其他高级程序设计语言可参照本部分内容
2.2.2 数据结构
1.线性结构
•【5】双端栈
•【5】双端队列
•【5】有序队列
•【6】优先队列
•【6】倍增表(ST 表)
2.集合与森林
•【6】等价类
•【6】并查集
•【6】树与二叉树的转化——孩子兄弟表示法
3.特殊树
•【6】线段树与树状数组
•【6】字典树(trie 树)
•【7】笛卡尔树
•【8】二叉平衡树 AVL、treap、splay 等
•【8】基环树
4.常见图
•【5】稀疏图
•【6】偶图(二分图)
•【6】欧拉图
•【6】有向无环图
•【7】连通图与强连通图
•【7】重连通图
5.哈希表
•【5】数值哈希函数构造
•【6】排列哈希函数构造
•【6】字符串哈希函数构造
•【6】哈希函数冲突的常见解决方法
2.2.3 算法
1.复杂度分析
•【6】空间复杂度分析
•【6】时间复杂度分析
2.基础算法
•【6】分治算法
3.排序算法
•【5】归并排序
•【5】快速排序
•【6】堆排序
•【6】树形选择排序(锦标赛排序)
•【5】桶排序
•【6】基数排序
4.字符串相关算法
•【5】字符串匹配算法——KMP
5.搜索算法
•【6】搜索的剪枝优化
•【6】记忆化搜索
•【7】启发式搜索
•【7】双向宽度优先搜索
•【7】迭代加深搜索
•【8】搜索对象的压缩存储
6.图论算法
•【6】Prim 和 Kruskal 等求最小生成树算法
•【7】求次小生成树算法
•【6】Dijkstra、bellman ford、SPFA 等求单源最短路算法
•【7】求单源次短路径算法
•【6】Floyd-Warshall 算法求任意两点间的最短路和传递闭包
•【6】有向无环图的拓扑排序算法
•【6】求欧拉道路和欧拉回路算法
•【6】二分图的构造及其判定算法
•【6】最近公共祖先
•【7】求强联通分量算法
•【7】强连通分量的缩点算法
•【7】求割点、割边算法
7. 动态规则
•【6】树型动态规划
•【7】状态压缩动态规划
•【8】动态规划的常用优化
2.2.4 数学
1.高中数学
•【5】代数
•【6】解析几何
•【6】立体几何
2.初等数论
•【5】同余式
•【7】欧拉定理和欧拉函数
•【7】费马小定理
•【7】威尔逊定理
•【7】裴蜀定理
•【7】逆元
•【7】扩展欧几里得算法
•【7】孙子定理(即中国剩余定理)
3.组合数学
•【6】可重集排列
•【6】可重集组合
•【6】错排列、圆排列
•【6】鸽巢原理
•【6】二项式定理
•【7】容斥原理
•【7】卡特兰数
4.线性代数
•【5】矩阵概念
•【6】特殊矩阵:稀疏矩阵,三角矩阵,对称矩阵
•【6】矩阵的初等变换
•【6】矩阵的加减乘和转置运算
•【7】线性方程组的高斯消元法
2.3 NOI 级
2.3.1 C++程序设计 3
1.【8】STL 模板:容器(containers)、迭代器(iterators)、空间配置器(allocators)、配接器(adapters)、算法(algorithms)、仿函数(functors)
2.【8】面向对象的程序设计思想(OOP)
3C++以外的其他高级程序设计语言可参照本部分内容。
2.3.2 数据结构
1.线性结构
•【8】分块
•【8】块状链表
2.序列
•【8】后缀数组
•【9】跳跃表
•【9】无根树的 Prüfer 序列
3.复杂树
•【8】树链剖分
•【8】主席树
•【8】二位线段树
•【9】后缀树
•【9】树套树
•【9】k-d 树
•【10】最小树形图
•【10】动态树(LCT)
4.可合并堆
•【8】左偏树
•【10】二项堆
5.【9】可持久化数据结构
2.3.3 算法
1.算法策略
•【9】复杂分治思想
•【9】平衡规划思想
•【9】构造思想
2.字符串算法
•【8】求最长回文串的 Manacher 算法
•【8】多模匹配算法——AC 自动机
•【9】求字符串前缀和后缀算法——扩展 KMP
•【9】确定性有穷自动机——DFA 算法
•【10】非确定性有穷自动机——NFA 算法
•【10】后缀自动机
3.图论算法
•【8】网络流算法
•【10】图的支配集、独立集与覆盖集
•【8】二分图的最大匹配——匈牙利算法
•【9】二分图的最佳匹配算法——KM 算法
•【10】一般图的匹配
4.动态规划
•【9】复杂动态规划模型构建
•【9】复杂动态规划模型的优化
2.2.4 数学
1.信息论基础
•【10】熵、互信息、条件熵、相对熵的基本概念
•【10】信息复杂度的基本概念
•【10】描述复杂度的基本概念
•【10】通讯复杂度的基本概念
2.初等数论
•【8】原根和指数
•【8】大步小步(Baby Step Giant Step,BSGS)算法
•【9】完全数
•【9】狄利克雷(Dirichlet)卷积
•【10】平方剩余
•【10】二次同余式
•【10】二次互反律
3.离散数学
•【9】代数系统的基本概念
•【9】群的基本概念
•【9】置换群与循环群
4.组合数学
•【9】母函数
•【9】莫比乌斯变换
•【9】Burnside 引理与 Pólya 原理
•【9】斯特林数
5.高等数学
•【9】多项式函数微分
•【9】多项式函数积分
•【10】泰勒级数
•【10】快速傅里叶变换(Fast Fourier Transform,FFT)
•【10】卷积
6.线性代数
•【9】矩阵的逆运算
•【9】行列式及其运算
•【9】线性相关与矩阵的逆
7.概率论
•【8】概率相关概念
•【9】求概率的乘法公式、全概率公式、贝叶斯公式
8.博弈论
•【9】零和博弈问题——Nim 博弈等
•【9】Sprague-Garundy(SG)函数概念及应用
9.运筹学
•【10】线性规划之单纯形法
10.计算几何
•【7】矢量及其运算
•【8】点、线、面之间的位置判断
•【8】常见图形的面积计算
•【8】二维凸包的求及其应用
•【9】半平面交
冲击2023年CSP-J/S & NOIP
师资介绍
H老师
四川大学硕士
竞赛成绩:
✺ 指导多位同学获得CPS-JS认证、NOIP省奖项
✺ 已培养数百名优秀信息竞赛学生
教学经验:
– 10年以上名校信息竞赛辅导经验;
– 曾经就职于一线互联网大厂,拥有丰富的编程经验;
– 多年iOS、Java、前端、数据库等技术栈开发经验;
– 高中信息技术教师资格证
教学风格:
– 耐心细致,对知识盲区的每个方面力求讲清楚,讲全面;
– 幽默诙谐,注重与同学的互动,提升课堂活跃度;
– 善于用图像具体化抽象的思维,更有利于同学们理解与思维上的提升;
学信息学加康老师微信👇🏻