本文主要是介绍学习进度——附《全国青少年信息学奥林匹克系列竞赛大纲》,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
全国青少年信息学奥林匹克系列竞赛大纲
每日总结
注:知识点总结在每个知识对应的板块那里
1005:
把不是很会的线段树和树状数组搞懂了,另复习了STL容器、二分、三分。
1、树状数组(详见树状数组2.2.3.3)
2、线段树(详见线段树2.2.3.3)
3、STL部分容器(详见STL2.1.2.13),vector、栈、队列
4、三分算法 BZOJ#17 曲线
注意:1.涉及浮点数 l l l 从0开始而不是从1.
5、二分 BZOJ#472 二分法求函数的零点
文章目录
- 全国青少年信息学奥林匹克系列竞赛大纲
- ***每日总结***
- 注:知识点总结在每个知识对应的板块那里
- 2.1 入门级
- 2.1.1 基础知识与编程环境
- 2.1.2 C++ 程序设计 1
- 1.程序基本概念
- 2. 基本数据类型
- 3. 程序基本语句
- 4. 基本运算
- 5. 数学库常用函数
- 6. 结构化程序设计
- 7. 数组
- 8. 字符串的处理
- 9.函数与递归
- 10. 结构体与联合体
- 11. 指针类型
- 12. 文件及基本读写
- 13. STL 模板
- 1. 线性结构
- 2. 简单树
- 3. 特殊树
- 4. 简单图
- 2.1.4 算法
- 1. 算法概念与描述
- 2. 入门算法
- 3. 基础算法
- 4. 数值处理算法
- 5. 排序算法
- 6. 搜索算法
- 7.图论算法
- 8. 动态规划
- 2.1.5 数学与其他
- 1. 数及其运算
- 2. 初等数学
- 3. 初等数论
- 4. 离散与组合数学
- 5. 其他
- 2.2 提高级
- 2.2.1 基础知识与编程环境
- 2.2.2 C++ 程序设计
- 1. 类(class)
- 2. STL 模板
- 2.2.3 数据结构
- 1. 线性结构
- 2. 集合与森林
- 3. 特殊树
- 4. 常见图
- 5. 哈希表
- 2.2.4 算法
- 1. 复杂度分析
- 2. 算法策略
- 3. 基础算法
- 4. 排序算法
- 5. 字符串相关算法
- 6. 搜索算法
- 7. 图论算法
- 8. 动态规划
- 2.2.5 数学与其他
- 1. 初等数学
- 2. 初等数论
- 3. 离散与组合数学
- 4. 线性代数
2.1 入门级
2.1.1 基础知识与编程环境
-
【 1 】计算机的基本构成(CPU、内存、 I/O 设备等)
-
【 1 】Windows、Linux 等操作系统的基本概念及其常见操作
-
【 1 】计算机网络和 Internet 的基本概念
-
【 1 】计算机的历史和常见用途
-
【 1 】NOI 以及相关活动的历史
-
【 1 】NOI 以及相关活动的规则
-
【 1 】位、字节与字
-
【 1 】程序设计语言以及程序编译和运行的基本概念
-
【 1 】使用图形界面新建、复制、删除、移动文件或目录
-
【 1 】使用 Windows 系统下的集成开发环境( 例如 Dev C++ 等 )
-
【 1 】使用 Linux 系统下的集成开发环境 ( 例如 Code::Blocks 等 )
-
【 1 】g++ 、gcc 等常见编译器的基本使用
2.1.2 C++ 程序设计 1
1.程序基本概念
【 1 】标识符、关键字、常量、变量、字符串、表达式的概念
【 1 】常量与变量的命名、定义及作用
【 2 】头文件与名字空间的概念
【 2 】编辑、编译、解释、调试的概念
2. 基本数据类型
【 1 】整数型: int 、 long long
【 1 】实数型: float 、 double
【 1 】字符型: char
【 1 】布尔型: bool
补充:__int128
3. 程序基本语句
【 2 】cin 语句、scanf 语句、cout 语句、printf语句、赋值语句、复合语句
补充:getline getchar write
scanf格式:
格式控制符 | 内容 |
---|---|
%c | 读取一个单一的字符 |
%hd、%d、%ld | 读取一个十进制整数,并分别赋值给 short、int、long 类型 |
%ho、%o、%lo | 读取一个八进制整数(可带前缀也可不带),并分别赋值给 short、int、long 类型 |
%hx、%x、%lx | 读取一个十六进制整数(可带前缀也可不带),并分别赋值给 short、int、long 类型 |
%hu、%u、%lu | 读取一个无符号整数,并分别赋值给 unsigned short、unsigned int、unsigned long 类型 |
%f、%lf | 读取一个十进制形式的小数,并分别赋值给 float、double 类型 |
%e、%le | 读取一个指数形式的小数,并分别赋值给 float、double 类型 |
%g、%lg | 既可以读取一个十进制形式的小数,也可以读取一个指数形式的小数,并分别赋值给 float、double 类型 |
%s | 读取一个字符串(以空白符为结束) |
【 2 】if 语句、switch 语句、多层条件语句
【 2 】for 语句、while 语句、do while 语句
【 3 】多层循环语句
4. 基本运算
【 1 】算术运算:加、减、乘、除、整除、求余
【 1 】关系运算:大于、大于等于、小于、小于等于、等于、不等于
【 1 】逻辑运算:与(&&)、或(||)、非(!)
【 1 】变量自增与自减运算
【 1 】三目运算
【 2 】位运算:与( &)、或(|)、非( ~)、 异或( ^ )、左移( << )、右移( >>)
5. 数学库常用函数
【 3 】绝对值函数、四舍五入函数、下取整函数、 上取整函数、平方根函数、常用三角函数、对数函数、指数函数
6. 结构化程序设计
【 1 】顺序结构、分支结构和循环结构
【 2 】自顶向下、逐步求精的模块化程序设计
【 2 】流程图的概念及流程图描述
7. 数组
【 1 】数组与数组下标
【 1 】数组的读入与输出
【 3 】二维数组与多维数组
8. 字符串的处理
【 2 】字符数组与相关函数
【 2 】string 类与相关函数
9.函数与递归
【 2 】函数定义与调用、形参与实参
【 3 】传值参数与传引用参数
【 2 】常量与变量的作用范围
【 2 】递归函数
10. 结构体与联合体
【 3 】结构体
【 3 】联合体
11. 指针类型
【 4 】指针
【 4 】基于指针的数组访问
【 4 】字符指针
【 4 】指向结构体的指针
12. 文件及基本读写
【 2 】文件的基本概念、文本文件的基本操作
【 2 】文本文件类型与二进制文件类型
【 2 】文件重定向、文件读写等操作
13. STL 模板
【 3 】算法模板库中的函数:min、max、swap、sort
【 4 】栈 (stack)、队列 (queue)、链表 (list)、向量(vector) 等容器
1005:
vector BZOJ#25259 合并区间
c.clear() //移除容器中所有数据
c.empty() //判断容器是否为空
c.erase(pos) //删除pos位置的数据
c.erase(begin,end) //删除[begin,end]区间的数据
c.front() //传回第一个数据
c.insert(pos,elem) //在pos位置插入一个elem拷贝
c.pop_back() //删除最后一个数据
c.push_back(elem) //在尾部加入一个数据
c.resize(num) //重新设置该容器的大小
c.size() //返回容器中实际数据的个数
c.begin() //返回指向容器第一个元素的迭代器
c.end() //返回指向容器最后一个元素的迭代器
1. 线性结构
【 3 】链表:单链表、双向链表、循环链表
【 3 】栈
push //元素入栈
pop //栈顶元素出栈
front //获取栈底元素
size //获取栈长度
empty //栈判空
【 3 】队列
push //元素入队列
pop //队尾元素出栈
front //获取队头元素
size //获取队列长度
empty //队列判空
top //获取队尾元素
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 】插入排序
【 3 】计数排序
6. 搜索算法
【 5 】深度优先搜索
【 5 】广度优先搜索
7.图论算法
【 4 】深度优先遍历
【 4 】广度优先遍历
【 5 】泛洪算法(flood fill)
8. 动态规划
【 4 】动态规划的基本思路
【 4 】简单一维动态规划
【 5 】简单背包类型动态规划
【 5 】简单区间类型动态规划
2.1.5 数学与其他
1. 数及其运算
【 1 】自然数、整数、有理数、实数及其算术运算(加、减、乘、除)
【 1 】进制与进制转换:二进制、八进制、十进制、十六进制
2. 初等数学
【 1 】代数(初中部分)
【 1 】几何(初中部分)
3. 初等数论
【 3 】整除、因数、倍数、指数、质 ( 素 ) 数、合数
【 3 】取整
【 3 】模运算与同余
【 3 】整数唯一分解定理
【 3 】辗转相除法(欧几里得算法)
【 4 】素数筛法:埃氏筛法与线性筛法
4. 离散与组合数学
【 2 】集合
【 2 】加法原理
【 2 】乘法原理
【 4 】排列
【 4 】组合
A M N A^{N}_{M} AMN = N ! / M ! N! / M ! N!/M!
C M N C^{N}_{M} CMN = A M N / A N N A^{N}_{M}/A^{N}_{N} AMN/ANN = N ! / ( N − M ) ! / M ! N!/(N-M)!/M! N!/(N−M)!/M!
【 4 】杨辉三角
5. 其他
【 2 】ASCII 码
【 2 】格雷码
2.2 提高级
2.2.1 基础知识与编程环境
【 5 】Linux 系统终端中常用的文件与目录操作命令
【 5 】Linux 系统下常见文本编辑工具的使用
【 5 】g++、gcc 等编译器与相关编译选项
【 5 】在 Linux 系统终端中运行程序,使用time 命令查看程序用时
【 5 】调试工具 GDB 的使用
2.2.2 C++ 程序设计
1. 类(class)
【 6 】类的概念及简单应用
【 6 】成员函数和运算符重载
2. STL 模板
【 5 】容器(container)和迭代器(iterator)
【 5 】对(pair)、元组(tuple)
【 5 】集合(set)、多重集合(multiset)
【 5 】双端队列(deque)、优先队列(priority_queue)
【 5 】映射(map)、多重映射(multimap)
【 5 】算法模板库中的常用函数
2.2.3 数据结构
1. 线性结构
【 5 】双端栈
【 5 】双端队列
【 5 】单调队列
【 6 】优先队列
【 6 】ST 表(Sparse Table)
2. 集合与森林
【 6 】并查集
【 6 】树的孩子兄弟表示法
3. 特殊树
【 6 】二叉堆
【 6 】树状数组(弱)
用途+知识点:
lowbit√
单修√、区修、单找√、区和找√
前缀和√
逆序对
1004 1005:
前缀和
单点修改、区间查询
BZOJ#130单点修改,区间查询
BZOJ#121清点人数
用法:
lowbit
int lowbit(int i) { return i & -i; }
前缀和、区间和
long long Sum(int i) {long long prev = 0;for (int k = i; k > 0; k -= lowbit(k)) prev += c[k];return prev;
}
单修
void modify(int k, int x) {for (int i = k; i <= n; i += lowbit(i)) c[i] += x;
}
【 6 】线段树(弱)
知识点+用途:
懒惰标记
单修√、区修、单找√、区和找√、区最找√
1005:
单修、区和查、区最查
BZOJ#3192「线段树」模板题1:单点修改,区间和查询
BZOJ#25839「线段树」模板题2:单点修改,区间最值查询
用法:
建树:
void build(long long p, long long l, long long r) {t[p].l = l, t[p].r = r;if (l == r) {t[p].Max = a[l];return;}long long mid = (l + r) / 2;build(p * 2, l, mid);build(p * 2 + 1, mid + 1, r);t[p].Max = max(t[p * 2].Max , t[p * 2 + 1].Max);
}
单修:
void modify(long long p, long long k, long long x) {if (t[p].l == t[p].r) {t[p].Max = x;return;}long long mid = (t[p].l + t[p].r) / 2;if (k > mid)modify(p * 2 + 1, k, x);elsemodify(p * 2, k, x);t[p].Max = max(t[p * 2].Max, t[p * 2 + 1].Max);
}
区找:
long long getsum(long long p, long long l, long long r) {if (l <= t[p].l && r >= t[p].r)return t[p].Max;long long mid = (t[p].l + t[p].r) / 2;long long sum = INT_MIN;if (l <= mid)sum = max(sum, getsum(p * 2, l, r));if (r > mid)sum = max(sum, getsum(p * 2 + 1, l, r));return sum;
}
根据题目要求适当调整。
【 6 】字典树(Trie 树)
【 7 】笛卡尔树
【 8 】平衡树:AVL、treap、splay 等
4. 常见图
【 5 】稀疏图
【 6 】偶图(二分图)
【 6 】欧拉图
【 6 】有向无环图
【 7 】连通图与强连通图
【 7 】双连通图
5. 哈希表
【 5 】数值哈希函数构造
【 6 】字符串哈希函数构造
【 6 】哈希冲突的常用处理方法
2.2.4 算法
1. 复杂度分析
【 6 】时间复杂度分析
【 6 】空间复杂度分析
2. 算法策略
【 6 】离散化
3. 基础算法
【 6 】分治算法
4. 排序算法
【 5 】归并排序
【 5 】快速排序
【 6 】堆排序
【 5 】桶排序
【 6 】基数排序
5. 字符串相关算法
【 5 】字符串匹配:KMP 算法
6. 搜索算法
【 6 】搜索的剪枝优化
【 6 】记忆化搜索
【 7 】启发式搜索
【 7 】双向广度优先搜索
【 7 】迭代加深搜索
7. 图论算法
【 6 】最小生成树:Prim 和 Kruskal 等算法
【 7 】次小生成树
【 6 】单源最短路:Bellman-Ford、Dijkstra、 SPFA 等算法
【 7 】单源次短路
【 6 】Floyd-Warshall 算法
【 6 】有向无环图的拓扑排序
【 6 】欧拉道路和欧拉回路
【 6 】二分图的判定
【 7 】强连通分量
【 7 】割点、割边
【 6 】树的重心、直径、DFS 序与欧拉序
【 6 】树上差分、子树和与倍增
【 6 】最近公共祖先
8. 动态规划
【 6 】树型动态规划
【 7 】状态压缩动态规划
【 8 】动态规划的常用优化
2.2.5 数学与其他
1. 初等数学
【 5 】代数(高中部分)
【 6 】几何(高中部分)
2. 初等数论
【 5 】同余式
【 7 】欧拉定理和欧拉函数
【 7 】费马小定理
【 7 】威尔逊定理
【 7 】裴蜀定理
【 7 】模运算意义下的逆元
【 7 】扩展欧几里得算法
【 7 】中国剩余定理
3. 离散与组合数学
【 6 】多重集合
【 6 】等价类
【 6 】多重集上的排列
【 6 】多重集上的组合
【 6 】错排列、圆排列
【 6 】鸽巢原理
【 6 】二项式定理
【 7 】容斥原理
【 7 】卡特兰(Catalan)数
4. 线性代数
【 5 】向量与矩阵的概念
【 6 】向量的运算
【 6 】矩阵的初等变换
【 6 】矩阵的运算:加法、减法、乘法与转置
【 6 】特殊矩阵的概念:单位阵、三角阵、对称阵和稀疏矩阵
【 7 】高斯消元法
这篇关于学习进度——附《全国青少年信息学奥林匹克系列竞赛大纲》的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!