技能

没错,ACM的技能树,太多了,待补全

一、字符串

查看详细
  1. kmp/扩展kmp
  2. 后缀数组
  3. 串的最小表示
  4. 有限状态自动机
  5. 最长重复子串
  6. 最长公共子串
  7. 最长回文子串
  8. 字符串散列
  9. 第k小数
  10. 区间k大数
  11. 逆序对
  12. 最长公共子序列
  13. 最长上升子序列
  14. 最长公共上升子序列
  15. 序列自动机
  16. 字典树
  17. 01字典树
  18. AC自动机
  19. 回文自动机
  20. 后缀自动机
  21. 最短公共祖先
  22. Karp-Rabin
  23. sunday
  24. 编辑距离
  25. 单词计数
  26. 字符串替换

二、计算几何

查看详细
  1. 点与向量的表示
  2. 内积与外积
  3. 四则运算
  4. 叉积与点积
  5. 两矢量间角度
  6. 两点距离
  7. 最近点对
  8. 对踵点
  9. 向量长度
  10. 费马点
  11. 分治求最近点对
  12. 四点共面
  13. 转角
  14. 单位法向量
  15. 绕点旋转
  16. 直线与线段的表示
  17. 点与直线的关系
  18. 点在直线上
  19. 两直线交点
  20. 点到线段最短距离
  21. 点在直线上的投影点
  22. 点在线段上
  23. 两线段相交
  24. 两线段交点
  25. 直线与线段相交
  26. 点到线段最大距离
  27. 点在射线的正向
  28. 两直线夹角弧度
  29. 点关于直线的对称点
  30. 直线平行
  31. 线段距离
  32. 矢量夹角
  33. 点到直线距离
  34. 三角形面积
  35. 三角形四心
  36. 多边形的表示
  37. 凸多边形直径
  38. Pick定理
  39. 多边形重心
  40. 多边形内格点数
  41. 叉乘法求任意多边形面积
  42. 射向法判断点在多边形内部
  43. 判断封闭图形是凹集还是凸集
  44. 半平面割多边形
  45. 半平面交
  46. 凸多边形交
  47. 多边形核
  48. 凸多边形与直线集交
  49. 多边形切割
  50. 三角剖分
  51. 三角形有向积
  52. 凸多边形并周长
  53. 三角公式
  54. 矩形面积并
  55. 矩形并的周长
  56. 三角形内接圆公式
  57. 三角形外切圆公式
  58. 圆内接四边形面积公式
  59. 圆与直线的交点
  60. 两圆交点
  61. 点到圆切线/内/外
  62. 两圆公切线
  63. 两圆相交面积
  64. 圆与多边形交面积/三角
  65. 最小圆覆盖
  66. 圆与圆求交
  67. 圆的离散化
  68. 圆的面积并
  69. 圆与线段相交
  70. 射线与圆的第一个交点
  71. 三点求圆心坐标
  72. 圆与圆关系
  73. Javis March
  74. Graham Scan
  75. Andrew
  76. Melkman
  77. 最大空凸包
  78. 计算几何误差修正
  79. 判相等
  80. 判大于小于等于0
  81. 排序(比较两点)
  82. 平行/同向/极角序
  83. 矩形面积并(线段树+扫描线|容斥)
  84. 辛普森自适应积分(求积分面积)面积并
  85. PSLG(平面区域)
  86. Liuctic计算几何库
  87. 极角排序
  88. 几何公式
  89. 平面划分
  90. 离散化
  91. 扫描线
  92. 旋转卡壳(求最远点对/点集直径)
  93. 网格
  94. 托勒密定理
  95. 可视图的建立
  96. 三维点线面
  97. 三维向量旋转
  98. 长方体表面两点最短距离
  99. 四面体体积
  100. 最小球覆盖
  101. 三维凸包
  102. 球面两点最短距离
  103. 球面坐标转化
  104. 球面距离模拟退火
  105. 解析几何 抛物线
  106. 双曲线
  107. 椭圆

三、数论

查看详细
  1. 欧几里得算法
  2. 拓展欧几里得
  3. 单变元模线性方程
  4. 中国剩余定理
  5. 费马小定理
  6. 求原根
  7. 平方剩余
  8. 离散对数
  9. N次剩余
  10. 二次剩余
  11. 二次同余方程
  12. 逆元
  13. 唯一分解定理
  14. 线性同余方程
  15. AB的约数和对mod取模
  16. 素数筛法
  17. 素数判定
  18. 质因数分解
  19. 因式分解PR
  20. 欧拉函数计算phi
  21. Mobius函数计算
  22. 素数测试
  23. 反素数
  24. 欧拉降幂公式
  25. 莫比乌斯反演
  26. A^B约束之和
  27. Min_25筛
  28. 积性
  29. 数值积分
  30. 高阶代数方程求根
  31. Ronberg算法计算积分(定积分)
  32. 求模线性方程
  33. 求模线性方程组(中国剩余定量)
  34. 多项式求根(牛顿法)
  35. Gauss求方程组 一类开关模2,01方程组
  36. (追赶法)求周期方程
  37. Gauss求同余方程组
  38. 矩阵的逆
  39. Gauss消元
  40. 常系数线性齐次递推
  41. 最大权子矩形
  42. 行列式的值
  43. 矩阵最大和
  44. 最大1矩阵
  45. 矩阵乘法
  46. 矩阵快速幂
  47. 快速幂
  48. 进制转换
  49. 阶乘
  50. 周期性方程
  51. 整数划分
  52. baby step giant strp
  53. 1/n循环节长度
  54. 斐波那契取模循环节
  55. 集合划分
  56. 阶乘最后非零位
  57. Farey总数
  58. Farey序列构造
  59. NTT
  60. 日期相隔天数
  61. FWT(xor)
  62. 快速傅里叶变换FFT
  63. 分数
  64. 全排列散列
  65. 斐波那契数列
  66. 斐波那契进制转换
  67. 星期计算/求某一天星期几/基姆拉尔森公式
  68. 罗马进制转换
  69. 表达式计算
  70. gcd lcm
  71. x的二进制长度
  72. x每一位相加之和
  73. 偏序关系
  74. Bertrand猜想
  75. 差分序列
  76. 威尔逊定理
  77. 约数个数
  78. 最小二乘法
  79. simpson积分
  80. 大数平方根
  81. 大数取模
  82. 概率

四、组合数学

查看详细
  1. 不可重排列
  2. 可重排列
  3. 圆排列
  4. 不尽相异元素全排列
  5. 多重集的排列
  6. 不可重组合
  7. 可重组合
  8. 不相邻组合
  9. 多重集的组合
  10. 大组合数取模
  11. 二项式定理
  12. 常见恒等式
  13. 鸽巢原理
  14. 容斥定理
  15. 帕斯卡不等式
  16. 卢卡斯定理
  17. 错排问题
  18. 斐波那契数列
  19. 卡特兰数列
  20. 线性递推方程
  21. 非线性递推方程
  22. BM算法
  23. 普通母函数
  24. 指数型母函数
  25. 布尔母函数
  26. Polya计数
  27. FFT
  28. 幻方构造
  29. N皇后问题
  30. 旋转魔方
  31. 骑士周游问题
  32. 杨辉三角
  33. 全排列
  34. 组合序列
  35. 偏序关系
  36. 递推关系
  37. 子集生成
  38. 枚举排列
  39. 汉诺塔
  40. 八数码
  41. 生成gray码
  42. 字典序全排列
  43. 字典序组合
  44. 置换群与Polay定理
  45. 约瑟夫问题Joseph
  46. 递归求排列组合
  47. 莫比乌斯反演
  48. 带约束的轨道计数(Burnside)
  49. Stirling Number(Second Kind)
  50. Bell Number
  51. Stirling’s Approximation
  52. Young Tableau
  53. Sum of Reciprocal Approximation

五、图论

查看详细

NP搜索

  1. 最大团搜索
  2. 极大团计数
    连通性
  3. 无向图割点
  4. 无向图割边
  5. 无向图的块
  6. 无向图连通分支
  7. 有向图连通分支
  8. 有向图最小点基
  9. 双连通分支
  10. 点双连通分支
  11. 边双连通分支
  12. 无向图最小割
  13. 无向图找桥
  14. 无向图连通度(割)
  15. 强连通分量/tarjan/Kosaraju/Gabow
  16. 强连通分支及缩点
    匹配
  17. 二分图最大匹配hungary/hopcroft Karp
  18. 二分图最佳匹配kuhn_munkras(带权二分图最优匹配)
  19. 一般图匹配
  20. 一般图匹配带花树
  21. 一般图最大加权匹配
  22. 二分图多重匹配
  23. 二分图最大权匹配KM
  24. 二分图判断 染色?
    网络流
  25. 最大流
  26. 上下界最大流
  27. 上下界最小流
  28. 最大流无流量
  29. 最小费用最大流zkw spfa
  30. 有界网络流
  31. 二分图网络最大流最小割
  32. 预流和最大流
  33. Dinic
  34. hlpp最大
  35. SAP
  36. ISAP
  37. 网络流规约
  38. 最大流多解
  39. 费用流最小割
  40. 最小费用流
  41. 无源汇上下界网络流
    支撑树
  42. 最小生成树prim/kruscal
  43. 最小树形图
  44. 次小生成树
  45. 最小生成森林(k)
  46. 有向图最小树形图
  47. 生成树计数
  48. 曼哈顿最小生成树
  49. 最优比例生成树
  50. 单度限制最小生成树
    最短路径
  51. 单源最短路
  52. 多源最短路
  53. 第k短路
  54. Bellman-ford
  55. dijkstra
  56. spfa
  57. folyd-warshall
  58. A*
    应用
  59. 欧拉回路 有向图/无向图/混合图
  60. 树的前序表转化
  61. 树的优化算法
  62. 拓扑排序(连通)
  63. 欧拉路径
  64. 最佳边割集
  65. 最佳点割集
  66. 最小边割集
  67. 最小点割集
  68. 最小路径覆盖
  69. 最小点集覆盖
  70. DAG的深度优先搜索标记
  71. 弦图判断
  72. 弦图的perfect elimination点排列
  73. 稳定婚姻问题
  74. 2-SAT 染色法/字典序最小解/强连通缩点(连通)
  75. floyd求最小环
  76. 树分治/点分治/链分治
  77. LCA st+dfs/离线tarjan/LCA倍增
  78. 树的重心
  79. 差分约束系统建立与求解(最短)
  80. 欧拉图 汉密尔顿图 解欧拉图
  81. 完美消除序列
  82. 图的同构
  83. 树的同构
  84. 树的直径
  85. 有特殊条件的汉密尔顿回路
  86. 普吕弗序列
  87. 模2意义下的二分图匹配数

六、数据结构

查看详细

基础

  1. 向量
  2. 队列
  3. 链表
  4. 集合
  5. 映射
  6. 哈希表
  7. 哈夫曼树
    进阶
  8. 单调栈
  9. 单调队列
  10. st表
  11. 带权并查集
  12. 种类并查集
  13. 可持久化并查集
  14. 树状数组/二维树状数组
  15. 线段树/二维线段树
  16. 权值线段树
  17. zkw线段树
  18. 主席树
  19. splay伸展树
  20. treap树堆
  21. 替罪羊树
  22. 珂朵莉树
  23. kd树/动态kd树
  24. 字典树 01/左兄右儿/k叉
  25. 舞蹈链
  26. 树链剖分
  27. LCT动态森林
  28. 树套树
  29. 替罪羊树套splay
  30. 划分树
  31. 左偏树
  32. RMQ 一维/二维
  33. 滚动数组 队列
  34. 两台机器工作调度
  35. 莫队算法
  36. 二叉堆
  37. 块状链表
  38. 01分数规划(k约束)
  39. 取第k元素
  40. 最少找硬币
  41. 棋盘分割
  42. 区间最大频率
  43. 使序列有序的最少交换次数
  44. 最小花费置换
  45. LCSubsequence
  46. Factor Oracle
  47. 子段和
  48. 子阵和
  49. 主席树 区间多少不同数/静态区间第k大/树上路径点权第k大/动态第k大

七、基础

查看详细

排序

  1. 快排
  2. 归并
  3. 堆排
  4. 希尔
  5. 冒泡
  6. 选择
    搜索
  7. dfs
  8. bfs
  9. 双向搜索
  10. 启发式搜索
  11. 记忆化搜索
  12. 二分
  13. 三分
    构造
    贪心
    模拟
    枚举
    分治
    递归
    分块
    莫队
    动态规划
  14. 01背包
  15. 完全背包
  16. 多维背包
  17. 费用背包
  18. 区间dp
  19. 环形dp
  20. 判定型dp
  21. 棋盘切割
  22. 最长上升子序列
  23. 最长公共子序列
  24. 二分判定型
  25. 树型dp(最大独立集)
  26. 状态压缩dp 哈密顿路径问题
  27. 四边形不等式理论(区间dp优化)
  28. 单调队列优化
  29. 数位dp
  30. 插头dp
    cdq分治

八、博弈论

查看详细
  1. SG函数
  2. Nim过程
  3. 极大极小过程
  4. 乘除法博弈
  5. Wythoff博弈

九、库

查看详细
  1. stl
  2. 大数
  3. java
  4. python