python算法竞赛学习记录（总）

1、前提知识

1. 线上学习网站
2. 线上裁判的返回值
3. 输入输出及显示格式
4. 复杂度
5. 基本数据结构
6. 技术

分点学习

2、字符串

1. 易位构词
2. T9
3. 字典树
4. KMP（Knuth-Morris-Pratt）模式匹配算法
5. 最大边的KMP算法
6. 字符串的幂
7. Rabin-Karp模式匹配算法
8. Manacher算法

3、序列

1. 网络中的最短路径
2. 编辑距离
3. 最长公共子序列
4. 升序最长子序列
5. 两位玩家游戏中的必胜策略

4、数组

1. 合并已排序列表
2. 区间的总和
3. 区间的重复内容
4. 区间的最大总和
5. 区间的最小值——线段树
6. 区间的总和——树状数组（fenwick树）
7. k个独立元素的窗口

5、区间

1. 区间树（线段树）
2. 区间的并集
3. 区间的覆盖

6、图

1. python对图编码
2. 隐式图
3. 深度优先遍历——深度优先算法
4. 广度优先遍历——广度优先算法
5. 连通分量
6. 双连通分量
7. 拓扑排序
8. 强连通分量
9. 可满足性

7、图中的环

1. 欧拉路径
2. 中国邮差问题
3. 最小长度上的比率权重环——Krap算法
4. 单位时间上成为最小比率环
5. 旅行推销员问题

8、最短路径

1. 组合的属性
2. 权重为0或1的图
3. 权重为正值或者空值的图——Dijkstra算法
4. 随即权重的图——Bellman—Ford算法
5. 所有源点-目标顶点对——Floyd-Wardshall算法
6. 网格
7. 变种问题

9、耦合性和流

1. 二分图最大匹配
2. 最大权重的完美匹配——Kuhn-Munkres算法
3. 无交叉平面匹配
4. 稳定的婚姻——Gale-Shapley算法
5. Ford-Fulkerson最大流算法
6. Edmonds-karp算法的最大流
7. Dinic算法
8. s-t最小割
9. 片面的s-t最小割
10. 运输问题
11. 在流和匹配之间化简
12. 偏序的宽度——Dilworth算法啊

10、树

1. 哈夫曼编码
2. 最近的共同祖先
3. 树中的最长路径
4. 最小权重生成树——Kruskal算法

11、集合

1. 背包问题
2. 找零问题
3. 给定总和值得子集
4. k个整数之和

12、点和多边形

1. 凸包问题
2. 多边形的测量
3. 最近点对
4. 简单直线多边形

13、长方形

1. 组成长方形
2. 网格中的最大正方形
3. 直方图中的最大长方形
4. 网格中的最大长方形
5. 合并长方形
6. 不相交长方形的合并

14、计算

1. 最大公约数
2. 贝祖等式
3. 二项式系数
4. 快速幂
5. 素数
6. 计算算数表达式
7. 线性方程组
8. 矩阵序列相乘

15、穷举

1. 激光路径
2. 精确覆盖
3. 数独
4. 排列枚举
5. 正确计算