CSP-S复赛知识点总结

虚心竹gulu · 2019-10-16 13:13:43 · 个人记录

CSP-S 知识点总结

• 搜索
  • bfs
    • 双向bfs
  • dfs
  • A*
  • IDA*
  • DLX
  • 记忆化搜索
  • 剪枝
    • 可行性剪枝
    • 最优化剪枝
    • 玄学剪枝
  • 模拟退火
  • 遗传算法
  • 爬山算法
  • 随机化搜索
• 字符串
  • kmp
    • 扩展kmp
  • trie树
    • 可持久化trie树
  • AC自动机
  • manacher
  • 字符串Hash
  • 最小表示法
  • 回文自动机
  • 后缀数组
• 数据结构
  • [x] 栈
    • 单调栈
  • [x] 队列
    • [x] 单调队列
    • [x] 优先队列(priority_queue)
    • [x] 双端队列(deque)
  • 堆
    • [x] 二叉堆
    • 可并堆
      • 左偏树
      • 斜堆
      • 配对堆
      • 斐波那契堆
      • 随机堆
  • [x] 并查集
    • 可持久化并查集
    • 带权并查集
  • hash表
  • 链表
    • 双向链表
    • 块状链表
      • 可持久化块状链表
    • 十字链表
  • st表
  • 块状树
  • [x] 树状数组
    • 多维树状数组
    • 树状数组求逆序对
  • [x] 线段树
    • 动态开点
    • 线段树的合并
    • 权值线段树
    • zkw线段树
    • 二维线段树（线段树套线段树）
    • 可持久化线段树（主席树）
    • 扫描线
  • 平衡树
    • treap
    • 无旋treap
      • 可持久化treap
    • splay
      • 可持久化splay
    • 替罪羊树
    • 红黑树
    • AVL树
    • SBT
    • 朝鲜树
  • trie树
    • 可持久化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
  • 环形dp
  • DAG上的dp
  • 多维dp
  • dp套dp
  • dp优化
    • 斜率优化
    • 数据结构优化
    • 四边形不等式优化
    • 改变状态优化
• 图论
  • 最短路
    • [x] SPFA
      • [x] spfa判负环
      • [x] LLL优化
      • [x] SLF优化
    • [x] dijkstra
      • [x] 堆优化dijkstra
      • 线段树优化dijkstra
    • floyed
      • 闭包
      • 倍增floyed
    • k短路
    • 最长路
    • 差分约束
  • tarjan
    • 强连通分量/缩点
    • 双连通分量（点、边）
    • 割点、割边、桥
  • [x] 拓扑排序
  • 二分图
    • 二分图最大匹配（匈牙利）
    • 二分图最大权匹配（KM）
  • 生成树
    • [x] 最小生成树
      • [x] Kruskal
      • [x] Prim及其堆优化
      • 严格次小生成树
      • 最大生成树
    • 生成树计数
      • 暴力统计
      • Matrix-tree定理
    • 最优比率生成树
    • 最小瓶颈生成树
  • 网络流
    • 最大流/最小割
      • Dinic
      • ISAP
    • 最小费用最大流
      • SPFA费用流
      • zkw费用流
    • 有上下界的网络流
    • 数据结构优化网络流
    • 分数规划
    • 欧拉图
    • 区间图与弦图
    • 平面图与对偶图
    • 最小树形图（朱刘算法）
    • 仙人掌
      • 动态仙人掌
• 树论
  • [x] 树的遍历
    • 前序、中序、后序 -[x] LCA
    • [x] 倍增
    • [x] 树剖
    • [x] tarjan
    • [x] RMQ求法
  • 虚树
  • 基环树
  • [x] 树链剖分
  • prufer序列
  • 括号序列
  • dfs序
  • 树上倍增
  • [x] 树的直径
  • 树的重心
  • 树分治
    • 点分治
    • 边分治
    • 动态树分治
  • Link-Cut-Tree
  • 树分块
• 数论/数学
  • 基础
    • 积性函数
    • 高中数学知识
  • 整除
  • 同余
  • 素数
    • 素数判断
    • Miller-Rabbin素数检测
    • 筛法求素数
      • 埃拉托色尼筛
      • 线性筛（欧拉筛）
    • 分解质因数
  • 欧拉函数
    • 线性筛欧拉函数
    • 欧拉定理
  • 快速幂
    • 慢速乘
  • 最大公约数
    • 辗转相除法
    • 更相减损术
    • 扩展欧几里得
      • 同余方程
      • ax+by=c
  • 中国剩余定理
  • 矩阵
    • 矩阵快速幂
    • 矩阵求逆
  • 行列式
  • 莫比乌斯反演
    • 莫比乌斯函数
  • 狄利克雷卷积
  • 容斥原理
    • 抽屉原理
    • Ramsey定理
  • 费马小定理
  • 逆元
    • 线性求逆元
    • exgcd求逆元
    • 费马小定理求逆元
  • 高斯消元
  • 线性基
  • 排列组合
    • 杨辉三角
    • Lucas定理
      • 扩展Lucas定理
  • BSGS
    • 扩展BSGS
  • 数列
    • 斐波那契数列
    • 卡特兰数
    • 斯特林数
    • 贝尔数
  • polya定理
  • 置换群
  • 原根
  • 快速傅里叶变换（FFT）
    • 快速数论变换（NTT）
    • 快速沃尔什变换（FWT）
  • 拉格朗日
    • 拉格朗日乘子法
    • 拉格朗日插值
    • 拉格朗日四平方和定理
  • 线性规划
  • 单纯性
  • 辛普森积分
  • 概率和期望
  • 计算几何
    • 基础
    • 向量
      • 点积
      • 叉积
      • 基础
    • 凸包
    • 旋转卡壳
    • 半平面交
    • 随机增量
    • Pick定理
    • 梯形剖分&三角形剖分
    • 扫描线
  • 博弈论
    • 基础
      • Bash Game
      • Wythoff Game
      • Nimm Game
    • SG函数
    • A-Beta剪枝
    • 博弈树
    • 极大极小搜索
    • 树形图博弈
• 其他
  • [x] 二分
    • 三分
    • 整体二分
    • [x] 二分答案
    • [x] lower_bound
    • [x] upper_bound
  • 倍增
  • [x] 贪心
  • [x] 枚举
  • [x] 暴力
  • 分治
    • CDQ分治
  • 离散化
  • 模拟
  • [x] 排序
    • [x] 快速排序（sort）
    • [x] 归并排序
    • 基数排序
    • [x] 计数排序
    • [x] 插入排序
    • [x] 选择排序
    • [x] 冒泡排序
  • 分块
  • 随机化
  • [x] 前缀和
    • [x] 多维前缀和
  • 高精度
    • 压位
  • 递推、递归
  • 位运算
  • 莫队
    • 树上莫队
    • 带修改的莫队
  • 打表
  • 卡常