【算法竞赛】已学知识索引与典题收藏
一、数学
1.1 素数筛
1.2 欧几里得算法
1.3 快速幂
普通快速幂、矩阵快速幂
1.4 生成函数
1.5 计算几何
二、动态规划
2.1 经典线性动态规划问题
四种背包、最长（非）上升子序列（LIS）、最长公共子序列（LCS）、最长公共上升子序列（LCIS）……
[NOIP2004 提高组 合唱队形]
[NOIP2010 提高组 乌龟棋]
P1868 饥饿的奶牛
上面3个题算是最基本的DP了
2.2 区间DP
三、数据结构
3.0 离散化
3.1 并查集
[NOIP2017 提高组] 奶酪 算是并查集板子题
[NOIP2010 提高组] 关押罪犯 简单的种类并查集（扩展域并查集）.好题.较为锻炼思维
UVA1316 Supermarket 并查集维护时间段是其一种解法，其思想十分巧妙
3.2 最小生成树
Prim、Kruskra
3.3 树状数组
3.4 ST表
3.5 线段树
3.6 Hash
四、图论
4.1 存图（略）
4.2 最短路
单源最短路、Floyd……
4.3 二分图匹配
4.4 强连通分量
4.5 树
二叉树的遍历、LCA、dfs序、树链剖分
4.5 树链剖分
五、字符串
5.1 KMP
六、博弈论
6.1 SG函数
经典组合博弈问题（取石子、nim游戏……）、SG函数