CSP-S复赛知识点总结
虚心竹gulu
·
·
个人记录
CSP-S 知识点总结
- 搜索
- bfs
- dfs
- A*
- IDA*
- DLX
- 记忆化搜索
- 剪枝
- 模拟退火
- 遗传算法
- 爬山算法
- 随机化搜索
- 字符串
- kmp
- trie树
- AC自动机
- manacher
- 字符串Hash
- 最小表示法
- 回文自动机
- 后缀数组
- 数据结构
- [x] 栈
- [x] 队列
- [x] 单调队列
- [x] 优先队列(priority_queue)
- [x] 双端队列(deque)
- 堆
- [x] 并查集
- hash表
- 链表
- st表
- 块状树
- [x] 树状数组
- [x] 线段树
- 动态开点
- 线段树的合并
- 权值线段树
- zkw线段树
- 二维线段树(线段树套线段树)
- 可持久化线段树(主席树)
- 扫描线
- 平衡树
- treap
- 无旋treap
- splay
- 替罪羊树
- 红黑树
- AVL树
- SBT
- 朝鲜树
- trie树
- KD树
- 划分树
- 四分树
- 笛卡尔树
- 树套树
- STL
- map
- set
- multiset
- [x] stack
- [x] queue
- [x] priority_queue
- [x] vector
- bitset
- 动态规划
- 简单dp
- [x] 背包
- [x] 0/1背包
- [x] 完全背包
- [x] 多重背包
- 区间dp
- 状态压缩
- 数位dp
- 树形dp
- 环形dp
- DAG上的dp
- 多维dp
- dp套dp
- dp优化
- 斜率优化
- 数据结构优化
- 四边形不等式优化
- 改变状态优化
- 图论
- 最短路
- [x] SPFA
- [x] spfa判负环
- [x] LLL优化
- [x] SLF优化
- [x] dijkstra
- [x] 堆优化dijkstra
- 线段树优化dijkstra
- floyed
- k短路
- 最长路
- 差分约束
- tarjan
- 强连通分量/缩点
- 双连通分量(点、边)
- 割点、割边、桥
- [x] 拓扑排序
- 二分图
- 二分图最大匹配(匈牙利)
- 二分图最大权匹配(KM)
- 生成树
- [x] 最小生成树
- [x] Kruskal
- [x] Prim及其堆优化
- 严格次小生成树
- 最大生成树
- 生成树计数
- 最优比率生成树
- 最小瓶颈生成树
- 网络流
- 最大流/最小割
- 最小费用最大流
- 有上下界的网络流
- 数据结构优化网络流
- 分数规划
- 欧拉图
- 区间图与弦图
- 平面图与对偶图
- 最小树形图(朱刘算法)
- 仙人掌
- 树论
- [x] 树的遍历
- 前序、中序、后序
-[x] LCA
- [x] 倍增
- [x] 树剖
- [x] tarjan
- [x] RMQ求法
- 虚树
- 基环树
- [x] 树链剖分
- prufer序列
- 括号序列
- dfs序
- 树上倍增
- [x] 树的直径
- 树的重心
- 树分治
- Link-Cut-Tree
- 树分块
- 数论/数学
- 基础
- 整除
- 同余
- 素数
- 素数判断
- Miller-Rabbin素数检测
- 筛法求素数
- 分解质因数
- 欧拉函数
- 快速幂
- 最大公约数
- 中国剩余定理
- 矩阵
- 行列式
- 莫比乌斯反演
- 狄利克雷卷积
- 容斥原理
- 费马小定理
- 逆元
- 高斯消元
- 线性基
- 排列组合
- BSGS
- 数列
- polya定理
- 置换群
- 原根
- 快速傅里叶变换(FFT)
- 拉格朗日
- 拉格朗日乘子法
- 拉格朗日插值
- 拉格朗日四平方和定理
- 线性规划
- 单纯性
- 辛普森积分
- 概率和期望
- 计算几何
- 基础
- 向量
- 凸包
- 旋转卡壳
- 半平面交
- 随机增量
- Pick定理
- 梯形剖分&三角形剖分
- 扫描线
- 博弈论
- 基础
- Bash Game
- Wythoff Game
- Nimm Game
- SG函数
- A-Beta剪枝
- 博弈树
- 极大极小搜索
- 树形图博弈
- 其他
- [x] 二分
- 三分
- 整体二分
- [x] 二分答案
- [x] lower_bound
- [x] upper_bound
- 倍增
- [x] 贪心
- [x] 枚举
- [x] 暴力
- 分治
- 离散化
- 模拟
- [x] 排序
- [x] 快速排序(sort)
- [x] 归并排序
- 基数排序
- [x] 计数排序
- [x] 插入排序
- [x] 选择排序
- [x] 冒泡排序
- 分块
- 随机化
- [x] 前缀和
- 高精度
- 递推、递归
- 位运算
- 莫队
- 打表
- 卡常