信息学竞赛知识大纲
======
|Author|杜博识Dubos|
|---|---|
|E-mail|dubos@foxmail.com|
------
OI (Olympiads in Informatics),国内译作`信息学竞赛`(或`信息学奥林匹克`、`程序设计竞赛`、`算法竞赛`)。本文为知识大纲,点击知识点即可进入对应讲义,但大纲是按照知识点归类排序的,与学习顺序并不完全相同,各个讲义是按照学习顺序编号的。信息学竞赛参赛过程、升学政策与各年级学习安排具体见:《[NOIP 00 信息学竞赛与升学](/NOIP%2000%20信息学竞赛与升学.md)》
## NOIP普及组
* C++入门
1. [入门:基本数据类型,常量与变量,赋值,算术表达式,整除与求余,模运算,数制转化,输入输出][NOIP 01 a],[文件操作][NOIP 01 b]
3. [程序的控制结构,逻辑表达式,逻辑运算,关系表达式,复合语句,条件语句,循环语句,条件嵌套,循环嵌套][NOIP 02]
4. [数组:一维数组][NOIP 03 a],[二维数组][NOIP 03 b],[字符数组][NOIP 03 c],[字符串string][NOIP 03 d],字符串cstring,[高精度计算][NOIP 03 f]
5. [指针,引用][NOIP 04]
5. [函数,常用数学函数(幂函数、指数函数、对数函数、三角函数、随机函数)][NOIP 05 a]
6. [结构体,自定义数据类型][NOIP 06]
* [算法普及组][NOIP 07 a]:
1. 时间复杂度,空间复杂度
2. 位运算
3. 模拟,枚举,回溯
4. 排序:选择,插入,冒泡;堆排序,归并,快排;计数,基数,桶排序
5. 搜索,深度优先搜索DFS,广度优先搜索BFS,剪枝
6. 贪心
7. 递归
8. 分治,二分
9. STL算法
* [数据结构普及组][NOIP 08 a]
1. [线性数据结构][NOIP 08 b]:[顺序表][NOIP 08 b 顺序表],~~数组~~(C++入门讲过了),[向量(或动态数组)][NOIP 08 b 向量],链表,双端队列,栈,队列,优先队列,STL顺序容器和容器适配器]
2. [树:二叉树的存储与遍历,STL关联容器,集合,映射][NOIP 08 c]
3. 图:邻接矩阵,邻接表,图的遍历,用DFS求连通块,用BFS求最短路,Euler回路,Hamiltonian回路
* 数学普及组:
1. 数论:素数与合数,最大公约数,辗转相除法(Euclidean算法),最小公倍数,互质数,整数的质因数分解,筛法
2. 快速幂运算:反复平方法(Russian Peasant算法)
3. 排列组合与集合:加法原理,乘法原理,圆排列,可重集排列,鸽笼原理,容斥原理,二项式定理与杨辉三角形
* 动态规划普及组:数字三角形,记忆化搜索,最长上升子序列LIS,最长公共子序列LCS,背包
## NOIP提高组
* 数学提高组:
1. 数论:拓展欧几里得算法,中国剩余定理,剩余类,费马小定理,欧拉定理,母函数
2. 概率,数学期望
3. 矩阵,线性方程组
4. 解析几何
5. 函数的连续性、单调性和极值,数列与级数
* 动态规划提高组:有向无环图DAG上的动态规划,树形动态规划,环形动态规划,后效性处理,状态压缩,倍增优化
* 数据结构提高组:
1. 二叉堆, 并查集,线段树,主席树,二叉索引树/树状数组BIT,区间最值问题RMQ,ST算法,哈夫曼Huffman树
2. 字典树Trie,哈希表Hash与字符串,KMP算法,AC自动机,后缀数组,后缀树
* 图论提高组:
1. 最小生成树MST,Kruskal算法,Prim算法,最近公共祖先LCA,最小有向生成树/最小树形图
3. 单源最短路SSSP,Dijkstra算法,Bellman-Ford算法及其SPFA优化,Floyd-Warshall算法,负环/负圈,差分约束
3. 连通性:强连通分量SCC,Trajan算法,Kosaraju算法,2-SAT问题
4. 拓扑排序
## 省选与NOI
* 数学决赛:
1. 博弈论SG函数,Nim
2. 群,置换群,Burnside定理,Polya原理
3. 快速傅里叶变换FFT
4. 莫比乌斯反演
5. 模拟退火算法
6. 线性规划
* 动态规划决赛:数据结构优化DP,单调队列优化DP,斜率优化,四边形不等式,计数类DP,数位统计DP,双重动态规划,基于连通性的动态规划
* 计算几何决赛
1. 基本运算,点积,叉积,点和直线,多边形
2. 圆和球
3. 二维几何:点在多边形内的判定,凸包,半平面,平面区域
4. 三维几何
5. 多边形的布尔计算
* 数据结构决赛:
1. 二叉查找树/二叉排序树BST,平衡树Treap,伸展树Splay,平衡二叉树SBT
2. 树套树:线段树套线段树,线段树套平衡树,平衡树套线段树
2. 树链剖分,动态树LCT
3. 分块,块状链表,[莫队算法][莫] [MO’s Algorithm][MO]
4. 可持久化数据结构
* 图论决赛:
1. 二分图:二分图的构造,二分图的匹配,匈牙利算法,KM算法(Kuhn-Munkres算法),Hopcroft-Karp算法,一般图的匹配
2. 网络流:最大流问题,Ford-Fulkerson增广路径算法与Edmonds-Karp算法,Dinic算法,ISAP算法,最大流最小割定理,最小费用最大流问题
3. 启发式搜索:A* 算法,IDA* 算法
信息学竞赛跟数理化生竞赛不同的是,做题可以用在线测评系统(Online Judge)评分:100:。除了公平、高效之外,还有一个好处是让用户看到许多其他用户的水平,这样就可以了解到其他学校、城市、省份乃至国家的选手:raising_hand:。当然OJ平台也有很多,有的主要用于学习阶段刷题,有的是学成之后去与高手切磋的,不同学习阶段用不同的平台。关于Online Judge的更多内容见[《OJ简介》](/NOIP%2000%20OJ简介.md)
###### 相关文件:
> [《关于NOI系列赛编程语言使用限制的规定》](http://www.noi.cn/about/rules/362-noi)
> [《CCF中学生程序设计等级评价体系》](/CCF中学生程序设计等级评价体系.pdf)
[NOIP 01 a]:/NOIP%20Junior/NOIP%2001%20a%20C%2B%2B入门.cpp
[NOIP 01 b]:/NOIP%20Junior/NOIP%2001%20b%20文件.md
[NOIP 02]:/NOIP%20Junior/NOIP%2002%20程序的控制结构.cpp
[NOIP 03 a]:/NOIP%20Junior/NOIP%2003%20a%20一维数组.cpp
[NOIP 03 b]:/NOIP%20Junior/NOIP%2003%20b%20二维数组.cpp
[NOIP 03 c]:/NOIP%20Junior/NOIP%2003%20c%20字符数组.cpp
[NOIP 03 d]:/NOIP%20Junior/NOIP%2003%20d%20string字符串.cpp
[NOIP 03 f]:/NOIP%20Junior/NOIP%2003%20f%20高精度计算.cpp
[NOIP 04]:/NOIP%20Junior/NOIP%2004%20指针与引用.cpp
[NOIP 05 a]:/NOIP%20Junior/NOIP%2005%20a%20函数.cpp
[NOIP 06]:/NOIP%20Junior/NOIP%2006%20结构体.md
[NOIP 07 a]:/NOIP%20Junior/NOIP%2007%20a%20算法普及组.md
[NOIP 08 a]:/NOIP%20Junior/NOIP%2008%20a%20普及组数据结构.md
[NOIP 08 b]:/NOIP%20Junior/NOIP%2008%20b%20线性数据结构.md
[NOIP 08 b 顺序表]:/NOIP%20Junior/NOIP%2008%20b%20线性数据结构.md#顺序表sequence-list
[NOIP 08 b 向量]:/NOIP%20Junior/NOIP%2008%20b%20线性数据结构.md#向量或称动态数组vector
[NOIP 08 c]:/NOIP%20Junior/NOIP%2008%20c%20树.md
[MO]:https://blog.anudeep2011.com/mos-algorithm/
[莫]:https://www.zhihu.com/question/27316467
没有合适的资源?快使用搜索试试~ 我知道了~
信息学竞赛,国内官方网站为:.zip
共35个文件
md:11个
cpp:9个
jpg:9个
需积分: 5 0 下载量 77 浏览量
2024-01-15
16:58:26
上传
评论
收藏 2.77MB ZIP 举报
温馨提示
大学生参加学科竞赛有着诸多好处,不仅有助于个人综合素质的提升,还能为未来职业发展奠定良好基础。以下是一些分析: 首先,学科竞赛是提高专业知识和技能水平的有效途径。通过参与竞赛,学生不仅能够深入学习相关专业知识,还能够接触到最新的科研成果和技术发展趋势。这有助于拓展学生的学科视野,使其对专业领域有更深刻的理解。在竞赛过程中,学生通常需要解决实际问题,这锻炼了他们独立思考和解决问题的能力。 其次,学科竞赛培养了学生的团队合作精神。许多竞赛项目需要团队协作来完成,这促使学生学会有效地与他人合作、协调分工。在团队合作中,学生们能够学到如何有效沟通、共同制定目标和分工合作,这对于日后进入职场具有重要意义。 此外,学科竞赛是提高学生综合能力的一种途径。竞赛项目通常会涉及到理论知识、实际操作和创新思维等多个方面,要求参赛者具备全面的素质。在竞赛过程中,学生不仅需要展现自己的专业知识,还需要具备创新意识和解决问题的能力。这种全面的综合能力培养对于未来从事各类职业都具有积极作用。 此外,学科竞赛可以为学生提供展示自我、树立信心的机会。通过比赛的舞台,学生有机会展现自己在专业领域的优势,得到他人的认可和赞誉。这对于培养学生的自信心和自我价值感非常重要,有助于他们更加积极主动地投入学习和未来的职业生涯。 最后,学科竞赛对于个人职业发展具有积极的助推作用。在竞赛中脱颖而出的学生通常能够引起企业、研究机构等用人单位的关注。获得竞赛奖项不仅可以作为个人履历的亮点,还可以为进入理想的工作岗位提供有力的支持。
资源推荐
资源详情
资源评论
收起资源包目录
信息学竞赛,国内官方网站为:.zip (35个子文件)
ABC-code
CCF中学生程序设计等级评价体系.pdf 1.19MB
NOIP Junior
NOIP 08 c 树.md 857B
NOIP 01 a C++入门.cpp 16KB
NOIP 04 指针与引用.cpp 14KB
NOIP 03 f 高精度计算 除法.md 299B
NOIP 01 b 文件.md 5KB
NOIP 03 c 字符数组.cpp 8KB
NOIP 08 b 线性数据结构.md 24KB
NOIP 03 a 一维数组.cpp 14KB
NOIP 05 a 函数.cpp 14KB
NOIP 07 a 算法普及组.md 4KB
NOIP 03 d string字符串.cpp 20KB
NOIP 03 f 高精度计算.cpp 14KB
README.md 84B
NOIP 03 b 二维数组.cpp 9KB
NOIP 06 结构体.md 1KB
NOIP 08 a 数据结构普及组.md 12KB
NOIP 02 程序的控制结构.cpp 14KB
NOIP 00 信息学竞赛与升学.md 19KB
NOIP 00 OJ简介.md 9KB
diagrams
NOI 04 A Self_Adjusting Search Tree by Jorge Stolfi.jpg 212KB
NOIP 08 b 顺序表2.gif 1KB
NOIP 07 STL Container Types.png 70KB
NOIP 08 b 1956 Dartmouth Conference.jpg 118KB
NOIP 08 b Deletion from a List.JPG 34KB
表情包试验.gif 79KB
NOIP 03 f 高精度计算 除法.png 673KB
NOIP 07 STL Components.JPG 35KB
NOIP 08 b 双向链表.jpg 390KB
NOIP 08 b 顺序表3.gif 897B
NOIP 08 b Simon Newell.jpg 35KB
NOIP 08 b List of elements.JPG 45KB
NOIP 08 b 顺序表1.jpg 62KB
NOIP 08 a KnuthAtOpenContentAlliance.jpg 44KB
README.md 7KB
共 35 条
- 1
资源评论
普通的一个普通猿
- 粉丝: 1460
- 资源: 1761
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功