竞赛知识点清单
竞赛数据结构
一、基本数据结构
a) 线性表
i. 栈
ii. 队列
iii. 链表
b) 树
c) 堆
d) 图
二、Hash表
三、并查集
四、树状数组
五、线段树
六、树套树
七、字典树
八、合并树
九、划分树
十、后缀树
十一、后缀数组
博弈论
1、SG函数
2、SG的拆分
3、Alpha-beta剪枝
搜索
1、DFS
a) 回溯
2、BFS
3、启发式搜索
4、A*算法
5、其它人工智能方面的搜索一般用不上
图论
1.图的搜索
1.1. 图的概念
1.2. 深度优先搜索
1.2.1. 普通的迷宫问题
1.3. 广度优先搜索
1.3.1. 迷宫最少步数
1.4. 隐式图的搜索
1.5. 树的概念
1.6. 图的深度优先搜索能带来的信息
1.6.1. 拓扑排序
1.6.2. 树的遍历
2. 可行遍问题
2.1. 欧拉回路、欧拉通路的判定
2.2. 求欧拉回路、欧拉通路
2.3. 哈密顿回路、哈密顿通路的概念
3. 生成树
3.1. 最小生成树
3.1.1. Kruskal算法
3.1.2. Prim算法
3.2. 最小生成树的性质研究
3.3. 次小生成树
3.4. K限度生成树
3.5. 最优比率生成树
4. 最短路
4.1. 单源最短路径
4.1.1. Dijkstra
4.1.1.1. Dijkstra算法与Prim算法的相似性
4.1.2. Bellman-ford
4.1.2.1. 差分约束系统
4.1.2.2. 单源最长路径
4.2. 多源多点最短路径
4.2.1. Floyd-Warshall
5. LCA问题
5.1. 朴素的LCA
5.2. LCA的Tarjan离线算法
5.3. 与RMQ问题的转化
5.4. +-1RMQ
5.5. 线段树做法*
6. 连通性
6.1. 有向图的强连通分量
6.1.1. Kosaraju算法
6.1.2. Tarjan算法
6.1.3. Gabow算法
6.2. 无向图的割点、桥、双连通分量
6.2.1. Tarjan算法
6.2.2. 图的深度遍历信息总结
6.3. 图的缩点和图的一些相关性质
7. 网络流
7.1. 最大流
7.1.1. 最大流的基本求法
7.1.1.1. Ford-Fulkerson算法
7.1.1.2. Edmonds-Karp算法
7.1.1.3. Dinic算法
7.1.2. 最小割最大流定理
7.2. 最小费用流
7.3. 二分图匹配
一、
计算几何知识点
1． 判断点是否在线段上
2． 判断两线段是否相交
3． 判断矩形是否包涵点
4． 判断矩形是否在矩形中
5． 判断元时候在矩形中
6． 判断点是否在多边形中
7． 判断线段是否在多边形内
8． 判断多边形是否在多边形内
9． 计算点到线段的最近点
10． 计算两个圆的公切线
11． 求两个圆的交点
12． 求矩形并的面积
13． 求多边形的面积
14． 求多边形的重心
15． 求凸包
二、 数论知识点
1. 欧几里得定理
2. 欧几里得定理扩展
3. 同余方程
4. 中国剩余定理
5. 筛法求素数
6. 欧拉定理
7. 费马小定理
8. 威尔逊定理
9. 拉格朗日定理
10. 高次不定方程的解法
11. 二元一次不定方程解法
12. pell方程
动态规划常用方法：
一、普通动态规划
二、记忆化搜索
三、多维动态规划
四、滚动数组
五、状态压缩
六、树形动态规划
其它：
字符串相关算法，如KMP等
自动机相关算法
动态规划与贪心算法必然要经常练习。