acm数据结构与算法能力训练（ACM中那些你见都没见过的算法）

小编在大一的时候，参加了学校中的ACM社团，那时候啥都不知道，对一切都充满了好奇，不过待了一年半就没有继续，原因挺多的，在这一年半中，学了许多听都没听过的算法，也不能说彻底了解，只能说“爱过”。

通过这一年半ACM，感觉 智商上的差距光靠努力是弥补不回来的，开个玩笑，努力总比不努力强一万倍。

ACM的确很锻炼思维，今天就在网上找了一下有关ACM的一些算法，来纪念我这一年半的经历。

数据结构

• 栈，队列，链表

• 哈希表，哈希数组

• 堆，优先队列

  双端队列

  可并堆

  左偏堆

• 二叉查找树

  Treap

  伸展树

• 并查集

  集合计数问题

  二分图的识别

• 平衡二叉树

• 二叉排序树

• 线段树

• 基本图算法图

  广度优先遍历

  深度优先遍历

  拓扑排序

  割边割点

  强连通分量

  Tarjan算法

  双连通分量

  强连通分支及其缩点

  图的割边和割点

  最小割模型、网络流规约

  2-SAT问题

  欧拉回路

  哈密顿回路

• 最小生成树

  Prim算法

  Kruskal算法(稀疏图)

  Sollin算法

  次小生成树

  第k小生成树

  最优比例生成树

  最小树形图

  最小度限制生成树

  平面点的欧几里德最小生成树

  平面点的曼哈顿最小生成树

  最小平衡生成树

• 最短路径

  有向无环图的最短路径->拓扑排序

  非负权值加权图的最短路径->Dijkstra算法(可使用二叉堆优化)

  含负权值加权图的最短路径->Bellmanford算法

  含负权值加权图的最短路径->Spfa算法

  (稠密带负权图中SPFA的效率并不如Bellman-Ford高)

  全源最短路弗洛伊德算法Floyd

  全源最短路Johnson算法

  次短路径

  第k短路径

  差分约束系统

  平面点对的最短路径(优化)

  双标准限制最短路径

• 最大流

  增广路->Ford-Fulkerson算法

  预推流

  Dinic算法

  有上下界限制的最大流

  节点有限制的网络流

  无向图最小割->Stoer-Wagner算法

  有向图和无向图的边不交路径

  Ford-Fulkerson迭加算法

  含负费用的最小费用最大流

• 匹配

  Hungary算法

  最小点覆盖

  最小路径覆盖

  最大独立集问题

  二分图最优完备匹配Kuhn-Munkras算法

  不带权二分匹配：匈牙利算法

  带权二分匹配：KM算法

  一般图的最大基数匹配

  一般图的赋权匹配问题

• 拓扑排序

• 弦图

• 稳定婚姻问题

搜索

• 广搜的状态优化

  利用M进制数存储状态

  转化为串用hash表判重

  按位压缩存储状态

  双向广搜

  A*算法

• 深搜的优化

  位运算

  剪枝

  函数参数尽可能少

  层数不易过大

  双向搜索或者是轮换搜索

  IDA*算法

• 记忆化搜索

动态规划

• 四边形不等式理论

• 不完全状态记录

  青蛙过河问题

  利用区间dp

• 背包类问题

  0-1背包，经典问题

  无限背包，经典问题

  判定性背包问题

  带附属关系的背包问题

  -1背包问题

  双背包求最优值

  构造三角形问题

  带上下界限制的背包问题(012背包)

• 线性的动态规划问题

  积木游戏问题

  决斗（判定性问题）

  圆的最大多边形问题

  统计单词个数问题

  棋盘分割

  日程安排问题

  最小逼近问题(求出两数之比最接近某数/两数之和等于某数等等)

  方块消除游戏(某区间可以连续消去求最大效益)

  资源分配问题

  数字三角形问题

  漂亮的打印

  邮局问题与构造答案

  最高积木问题

  两段连续和最大

  2次幂和问题

  N个数的最大M段子段和

  交叉最大数问题

• 判定性问题的dp(如判定整除、判定可达性等)

  模K问题的dp

  特殊的模K问题，求最大(最小)模K的数

  变换数问题

• 单调性优化的动态规划

  1-SUM问题

  2-SUM问题

  序列划分问题(单调队列优化)

• 剖分问题(多边形剖分/石子合并/圆的剖分/乘积最大)

  凸多边形的三角剖分问题

  乘积最大问题

  多边形游戏(多边形边上是操作符,顶点有权值)

  石子合并(N^3/N^2/NLogN各种优化)

• 贪心的动态规划

  最优装载问题

  部分背包问题

  乘船问题

  贪心策略

  双机调度问题Johnson算法

• 状态dp

  牛仔射击问题(博弈类)

  哈密顿路径的状态dp

  两支点天平平衡问题

  一个有向图的最接近二部图

• 树型dp

  完美服务器问题(每个节点有3种状态)

  小胖守皇宫问题

  网络收费问题

  树中漫游问题

  树上的博弈

  树的最大独立集问题

  树的最大平衡值问题

  构造树的最小环

数学

数论

• 中国剩余定理

• 欧拉函数

• 欧几里得定理

• 欧几里德辗转相除法求GCD(最大公约数)

• 扩展欧几里得

• 大数分解与素数判定

• 佩尔方程

• 同余定理(大数求余)

• 素数测试

  一千万以内：筛选法

  一千万以外：米勒测试法

• 连分数逼近

• 因式分解

• 循环群生成元

• 素数与整除问题

• 进制位.

• 同余模运算

组合数学

• 排列组合

• 容斥原理

• 递推关系和生成函数

• Polya计数法

  Polya计数公式

  Burnside定理

• N皇后构造解

• 幻方的构造

• 满足一定条件的hamilton圈的构造

• Catalan数

• Stirling数

• 斐波拉契数

• 调和数

• 连分数

• MoBius反演

• 偏序关系理论

• 加法原理和乘法原理

计算几何

• 基本公式

  叉乘

  点乘

  常见形状的面积、周长、体积公式

  坐标离散化

• 线段

  判断两线段（一直线、一线段）是否相交

  求两线段的交点

• 多边形

  判定凸多边形,顶点按顺时针或逆时针给出,(不)允许相邻边共线

  判点在凸多边形内或多边形边上,顶点按顺时针或逆时针给出

  判点在凸多边形内,顶点按顺时针或逆时针给出,在多边形边上返回0

  判点在任意多边形内,顶点按顺时针或逆时针给出

  判线段在任意多边形内,顶点按顺时针或逆时针给出,与边界相交返回1

  多边形重心

  多边形切割(半平面交)

  扫描线算法

  多边形的内核

• 三角形

  内心

  外心

  重心

  垂心

  费马点

• 圆

  判直线和圆相交,包括相切

  判线段和圆相交,包括端点和相切

  判圆和圆相交,包括相切

  计算圆上到点p最近点,如p与圆心重合,返回p本身

  计算直线与圆的交点,保证直线与圆有交点

  计算线段与圆的交点可用这个函数后判点是否在线段上

  计算圆与圆的交点,保证圆与圆有交点,圆心不重合

  计算两圆的内外公切线

  计算线段到圆的切点

  点集最小圆覆盖

• 可视图的建立

• 对踵点

• 经典问题

  平面凸包

  三维凸包

  Delaunay剖分/Voronoi图

计算方法

• 二分法

  二分法求解单调函数相关知识

  用矩阵加速的计算

• 迭代法

• 三分法

• 解线性方程组

  LUP分解

  高斯消元

• 解模线性方程组

• 定积分计算

• 多项式求根

• 周期性方程

• 线性规划

• 快速傅立叶变换

• 随机算法

• 0/1分数规划

• 三分法求解单峰(单谷)的极值

• 迭代逼近

• 矩阵法

博弈论

• 极大极小过程

• Nim问题

在网上找的，大多都没见过，有能力的可以学习一下。