ACM_template

常用技巧

• __int128的输入输出模板
• fread读入挂
• 常用STL及其用法
• pb_ds库用法
• 库函数
• 小技巧
• 位运算

动态规划

• 背包类问题
• 编辑距离
• 单调递增子序列LIS
• 区间DP
• 树形dp
• 数位dp
• 状压dp
• 树的最大匹配数

分治

• 点分治

高精度计算

• 大数的加减乘除

计算几何

• 计算几何

数据结构

• 线段树
  • 单点更新-区间求和
  • 单点更新-区间求最值
  • 区间更新
  • 线段树+离散化
  • 扫描线-离散化-矩形面积并
  • 扫描线-离散化-矩形面积交
  • 值域线段树求第k大
• RMQ算法/ST表
• 树状数组
• 树链剖分
• 主席树
• 莫队算法
• 区间不同元素个数
• Trie树
• 线性基
• 使序列有序的最少交换次数
• 单调栈
• 二维数点

数论

• 欧拉函数
• 快速幂/矩阵快速幂
• 康托展开
• 欧几里得/扩展欧几里得算法
• 求逆元
• 自适应辛普森积分
• 素数相关/线性筛法
• 博弈论
  • 巴什博奕
  • 威佐夫博弈
  • 尼姆博弈
  • SG函数

图论

• 欧拉回路
• Havel-Hakimi定理
• 最小生成树
  • Kruakal算法
  • prime算法
• 最短路
  • Dijkstra算法
  • floyd算法
  • Bell-Ford算法以及队列优化SPFA
  • 第k短路
• 二分图匹配
  • 匈牙利算法
  • 二分图染色法
  • 最大完备匹配-KM算法
  • 多重匹配
  • 最小路径覆盖
  • 最小点集覆盖-König定理
• 网络流
  • 最大流-EK算法
  • 最大流-ISAP算法
  • 最大流-Dinic算法
  • 最小费用最大流-最小费用路算法
• 图的连通-tarjan算法
• 树的直径
• 最近公共祖先LCA
  • 离线Tarjan算法
  • 在线倍增算法
  • 树剖求lca
• 拓扑排序
• 最短路树
• 搜索
• 求桥
• 割点

字符串

• KMP算法
• 扩展KMP算法
• AC自动机算法
• 字符串最大最小表示法
• Manacher算法
• 后缀数组
• 后缀自动机SAM

组合数学

• 母函数
• BM线性递推
• 容斥原理
• 组合数
• 卢卡斯定理
• 各种公式

其它

• 表达式求值
• 归并排序
• 模拟退火
• 二分查找
• java和python
• vim配置
• 拉格朗日插值