[省选]知识点板块

摘抄自网络,部分自己添加
同样的,加粗是重点,星号是选学

  • 图论
    - 网络流(dinic,ISAP选一个,费用流写EK就行。zkw费用流),二分图
    - 点分治,边分治,
    动态点分治
    - 树链剖分动态树,树分块
    - 虚树,*prufer编码
    - *仙人掌算法
  • 数据结构
    - Splay(作为平衡树和维护区间),Treap,替罪羊树
    - 线段树(权值线段树)树状数组线段树合并
    - 树套树
    - 主席树可持久化trie
    其它可持久化数据结构
    - 二维线段树,KDtree
    - 舞蹈链,二进制分组,
    左偏树,超哥线段树,后缀平衡树,*fhqTreap
  • 分治、分块
    - 分块,块状链表,*双向链表
    - 莫队算法,*树上莫队
    - CDQ分治(整体二分
    - 二分答案、三分法
  • 字符串相关算法及数据结构
    - hash(自然溢出,双hash)
    - kmpAC自动机trie
    - 后缀数组DA/DC3(应用很广)
    - manacher,最小表示法
    - 后缀自动机,回文自动机,*后缀树
  • 数学
    - 线性筛积性函数容斥原理,莫比乌斯反演
    - exgcd费马小定理Lucas定理高中排列组合
    - 高斯消元概率与期望相关
    - 中国剩余定理,BSGS,欧拉定理
    - 矩阵乘法
    - 单纯形法解线性规划
    - FFT
    - 线性代数(行列式)
    - 高中求导与积分
    - *群论
    - 生成函数,多项式类算法
    - 博弈论相关,密码学,阶,原根
  • 计算几何
    - 向量的点积/叉积,计算几何基础
    - 凸包
    - Simpson积分
    - 二维计算几何相关,三维计算几何相关
    - 半平面交,旋转卡壳,*三角剖分
  • 搜索
    - A*记忆化搜索迭代深搜双向广搜
    - 模拟退火,爬山算法,*随机增量法
  • 动态规划
    - 基础DP树形DP数位DP状压DP期望DP,基环树DP,插头DP
    - 斜率优化矩乘优化单调队列优化,倍增优化,
    四边形不等式优化
    - trie图DP,*仙人掌DP
  • 骗分策略
    - 贪心
    - 随机化
    - 打表****

计算几何基本都是全场爆零。

原文地址:https://www.cnblogs.com/patricksu/p/7999877.html