ACM Contest Algorithms In 10,000 words

很多年没有再接触ACM方面的算法了，不过这一块其实不时还会提到，在此姑且做个简陋的总结，望诸位不吝赐教^_^。

动态规划

动态规划，核心在于定义”状态”及”状态转移方程”，能保证从任意状态开始都会产生该状态下的最优策略(Principle of Optimality)。

基本技巧

  • 定义状态，可以定义”花费刚好为v时的最优值”和”花费至多为v时的最优值”两种；
  • 记录最优方案，则开多一个数组记录来源状态，及状态转移选择(如果来源状态不暗含的话)；
  • 求方案总数，最小值等，则将max改成sum、min；
  • 求第K优解，则在状态数组中多开一维(就是每个状态变一个队列)，记录前K优解。

背包
有限空间内放置各种价值不同资源(物品)的最优值问题。这个问题崔添翼大牛在《背包九讲》里面讲得超清楚，简单概括一下好了。

  1. 01背包：各种物品只有一件。$F[i,v]=max\{F[i-1,v],F[i-1,v-C_i]+W_i\}$，即选择取或不取。循环每件物品时，如倒序扫描DP数组，可以降低一维空间复杂度。
  2. 完全背包：各种物品无限件。$F[i,v]=max\{F[i-1,v],F[i,v-C_i]+W_i\}$。01背包改成顺序扫描DP数组就可以了。预处理去掉明显性价比低的物品，能进一步优化。
  3. 多重背包：各种物品$M_i$件。$F[i,v]=max\{F[i-1,v-kC_i]+kW_i\},0\le k\le M_i$。可以将$M_i$拆分成二进制表示的多件物品，进行01背包，优化复杂度。单调队列优化容后补充
  4. 多维背包：以上问题扩展到多维有限空间。二维为例，$F[i,v,u]=max\{F[i-1,v,u],F[i-1,v-C_i,u-D_i]+W_i\}$，多一重循环就好了，比如二维01背包就两重倒序扫描。
  5. 分组背包：以上问题的物品分组，每组最多取一件。$F[k,v]=max\{F[k-1,v],F[k-1,v-C_i]+W_i\},i\in 组k$。先循环组，再倒序扫描DP数组每次取组内一件。
  6. 有依赖的背包：以上问题选用物品要满足依赖关系，依赖关系是一个森林。由于每一个结点及其儿子都有$2^k$种选择，这相当于多次背包的结果再合并的问题。就用树状DP的方法，从叶子开始，每一个结点都进行一次01背包减少选择。

插头
二维格子平面，和格子之间连通状态有关，逐格进行状态转移的动态规划问题。特点是之前多格连通状态都要考虑，因此需要进行状态压缩。称已决策和未决策格子的分界线为轮廓线，若两个格子相连通则称其公共边为一个插头，然后用一个某进制数S表达轮廓线上插头的连通状态。
为了让S的进制尽可能小：

  1. 若插头两两匹配且连通路线不交叉，S就可以类似括号序列一样用3进制就够(表达无插头,左插头,右插头)。
  2. 若1的条件不满足，则将连通的插头用同一标号表示。
    若题目允许，S的进制增加到$2^k$就可以位运算来转移加快运算速度。更多介绍见集训论文

其他常见类型

上面总结的都是比较经典的问题，其他类型的DP网上总结比较杂乱，我也一下想不起来太多，因此简单总结如下：

  • 先后手博弈：考虑状态是先手胜态/后手胜态，一般通过从博弈完结状态开始逆推来建立状态转移方程。（一些问题有数学解，可以通过设计一个函数及一种组合运算，将问题拆分成多个连续的子博弈，分别求得子博弈的函数值，然后通过组合运算得出原博弈解。如NIM博弈可以定义SG函数为后继状态SG函数中未出现的最小自然数，且无法移动的状态SG(x)=0；定义组合运算为异或运算；若SG(x1,x2,..)=0则先手胜。更多变形参见。）
  • 树状：从子结点开始归纳状态转移方程。一般一维是节点编号，其余维描述子树状态。
  • 序列/区间/字符串：常以起始位置、连续区间长度作为状态的维度。
  • 矩阵：注重预处理的一类动态规划。典型的如最大子矩阵和(悬线法O(n^2))。

相关优化

  • 滚动数组：因为动态规划方程中，最外层循环每次往往只需要用到上一次循环的数据，所以只开能够存下两次大循环的空间就好，而不是全部循环的空间。
  • 状态压缩：将本来需要多维(一般32维以下)表达的状态，压缩为一个某进制（一般就是二进制、三进制）的整数来表达，整数的每一位就是原来一个维度。这样好处在于思路清晰代码简洁，二进制还可以方便地通过为运算进行状态转移。常见于矩阵、图、树上的动态规划。
  • 单调队列：一般应用于状态转移中，要求旧状态带有”最大/最小”条件的问题。关键是发现可以抛弃掉的、更老的状态，作为单调队列可抛弃的状态。对于有区间限制的题目，可以将{状态值，状态位置}对建成单调双端队列，左限制右求最值。每次状态转移时就可以从单调队列中提取，而不必往前扫描。没有区间限制求第k大/k小的题目，若发现了可抛弃的状态，亦可构建一个单调序列，用二分查找提取(最长不下降子序列)。见此总结
  • 数学优化(如四边形不等式)：对于特定形式的状态转移方程，且代价函数满足一定条件的问题，可以限制代码某重循环的上/下界。如四边形不等式优化在代价函数满足四边形不等式及单调性后（形象用四边形记忆，左下加右上<=左上+右下且右下<=左上），可以将$O(n^3)$降至$O(n^2)$。常见于序列上的动态规划。See.

最后，推荐一下：Amber的总结,

树与图论

Adjacency List

Topological Sort
BFS每次向有序序列中加入入度为0的点，并删除所有从它出发的边，若删的时候有边指回已经加入序列的点就有环路。或DFS，递归完时再将点加入有序序列(倒序)，若DFS到已经在DFS里面的点就有环路。一个图可能存在多种拓扑排序结果。
Huffman Codes
使用不定长个二进制位来表达字符串的一个字母(单位)以尽可能压缩字符串。相当于只计算叶结点代价和的最优二叉搜索树。每次从优先队列中取代价最小的两颗子树合并就好。
LCA/RMQ问题 - Tarjan/Sparse Table

  • RMQ(区间最值查询)问题可使用在线的Sparse Table法，本质是一种动态规划。F[i, j]表示i起点2^j长度的区间内的最值，F[i, j]=opt{F[i, j-1], F[i+2^j-1, j-1]}，查询的时候查询重叠的两个边界子区间如opt[3,8]=opt{F[3,2],F[5,2]}。每次插入时修改相关的区间就好，O(nlogn)预处理O(1)查询。或者用线段树解决O(n)预处理O(logn)查询。
  • LCA(最近公共祖先)问题可使用离线的Tarjan法，DFS遍历每一个点，并使用并查集记录遍历过程，遍历完了一个点及其子树后就处理与之相关的查询。如果另一端也处理过了，答案就是并查集根（要么是兄弟子树上的，其并查集根就是父亲，要么是自身子树上的，合并后并查集根就是自己）。

两个问题可以互相转化，求RMQ问题就相当于求按原序列为中序的堆的LCA问题，求LCA问题就相当于该树中序遍历序列的相应两个点之间的RMQ问题。
强连通分支问题 - Kosaraju
有向图求强连通分支(任意点相互可达)的算法。先DFS一次记录访问顺序，然后所有边取反，逆访问顺序多次DFS，每次DFS到的点即为一个强连通分支。

  • 类似的算法还有Tarjan和Gabow，不过时间复杂度上的优化并不算太大，暂时不写啦

Dijkstra
正权图单源最短路，以贪心为基础。维护一个数组，记录源点到每个点当前已知最短路边权和，初始除了源点全为无穷大。循环V次，每次取数组中的最小值，即为到该对应点的最短路。$O(V^2)$

  • 也可以用邻接表保存边，维护一个二叉堆而不是数组。$O((E+V)logV)$

Bellman-ford
任意图单源最短路。遍历V-1次边集进行松弛。如果遍历后还有边可以松弛，则存在负权环。$O(VE)$

SPFA
用队列优化Bellman-ford算法。一开始只有源点在队列中。每次循环遍历队头的点的邻边，所有被松弛的点加入队列。如果某个点的入队次数超过V，则存在负权环。

  • SLL优化：对于要入队的元素i，队首j，若$dist[i] < dist[j]$，i插入队首；
  • LLL优化：队首j，若$dist[j] < average(dist[])$，j延至队尾处理；

其中dist[i]是到第i个点的当前最短路(边权和)。核心思路是提前可能更优的松弛。加上两个优化平均可提速50%。

Floyd-warshall
任意图多源最短路，动态规划为基础。维护一个邻接矩阵，三重循环，每次以对角线的点为中心作十字用v[i,k]+v[k,j]更新v[i,j]。$O(V^3)$

Johnson
任意图多源最短路，稀疏图上比Floyd表现好。正权图直接每个点出发各跑一遍堆优化Dijkstra。带负权图先设一个到所有点都有权0的边的新点s，跑一遍s出发的Bellman-ford/SPFA求得最短距离h[v]，然后原来的每条边e[u,v]+=h[u]-h[v]，再重复开始正权图步骤。

Prim
任意图的最小生成树算法。维护一个数组，记录每个”已到点”连接某个”未到点”的最小边权。循环V次，每次取数组中的最小值，对应边即为最小生成树树枝，对应点加入”已到点”。O(V^2)

  • 也可以用邻接表保存边，维护一个二叉堆而不是数组，但写这个不如写Kruskal。O((E+V)logV)

Kruskal
任意图的最小生成树算法。边集按权值从小到大排序逐条尝试加入解，并维护一个并查集以保证不形成环路，直到成功加入V-1条边。O(VlogV+ElogE)

网络流

重要定理：最大流=最小割。
Ford-Fulkerson
网络流算法的基础思想。不断简单地DFS寻找一条增广路。
Edmonds-Karp
每次BFS出一条长度最短的增广路。BFS时使用临时数组推演可能作出的流量变化。
Dinic
优化后的求最大流算法。每次先BFS建立层次图(离源点距离i的点在第i层)，然后DFS逐层递归找一条增广路(能增加流量的路径，流量为路径中权值最小的边)，然后增广值加入总流量，并把整条增广路反向。循环至汇点不能到达。动画及代码见这里。
SAP
相比Dinic，常数上更快但是代码行数和细节更多的算法。初始化时先BFS建立层次图（SAP是里汇点的距离）。然后循环进行原点出发的回溯(DFS写成while)来寻找增广路。每条可行弧必须刚好降一层。如果某个点没有可行弧，就更新它的层次值为min{它可以去的相邻点的层次值}，再继续回溯。直到没有属于某个中间层次的点出现断层，或者源点层次值大于等于点数n了。评价见这里。
Hungarian
求最大二分图匹配的算法。左半部每个点依次贪心，每次出发递归寻找右边一个可增广的未连接点后即可(递归过程中可以标记一下，每个点只需要访问一次)。
Kuhn-Munkres
求带权二分图的最佳匹配(权和最大)的算法。每个点设一个点权L，先左半部$L[X_i]=max\{e_{ij}\}$，右半部$L[Y_j]=0$。同样每次从$X_i$出发，用匈牙利算法找所有边满足$L[i]+L[j]=e_{ij}$的”等值子图”的增广路，找增广路时右半部每个点记录$slack[Y_j]=max\{L[i]+L[j]-e_{ij}\}$。如果找不到增广路，令$d=min\{slack[Y_j]\}$，找增广路过程中访问到的每个点$L[X_i]=L[X_i]-d, L[Y_j]=L[Y_j]+d$，未访问点$slack[Y_j]=slack[Y_j]-d$，再循环匈牙利算法直至找同一个点的增广路。最后找到等值子图的完全匹配(就是每个点都匹配到)就是解。$O(n^3)$

数据结构

Monotonic Queue
一个双端队列，左边抛掉不符合新条件的旧元素，右边新元素入队时抛掉不能保持单调性的。
能够求最大最小/k大k小问题。经常被用于优化动态规划算法。
Segmentation tree
一个结点记录一条线段的值，子结点将父结点代表线段对半分。由于对半分的特性，线段树是完全二叉树，每个结点表示的线段可以推导出(作为递归参数)而不必记录。更新/询问时要么递归下去直到叶结点。要么lazy优化，结点线段被包含在要求线段之内就好。如果有必要就记录这个结点这次更新的值。下次需要更加细化地更新/询问时，再将这个值往下推。反正因为包含关系，叶结点更新的量是一样的。
二维问题也可能用到线段树(扫描线法)，如求矩形面积叠合后和，x轴作为离散化的线段建立线段树，然后按y轴顺序往树上添加矩形的上底和下底，并记录每条线段目前是被上底覆盖还是下底覆盖，这样添加的时候就可以算面积。参考这里。
Disjoint Set
数组记录的树，记录父结点及子树元素个数。查找：递归查找出树根a，然后沿路将父结点全部置为a。合并：要合并的两个结点分别查找出树根a,b，然后元素少的树根a父结点置为b

BST
搜索树是一系列方便快速查找的数据结构。最简单的BST，左儿子小右儿子大，建树、插入、查找都是从树根开始的递归。删除则是该结点与左子树的最大结点互换后删除（因为这个结点不可能有两棵子树。如果换右子树最小也可以）
AVL
左右子树深度差最多是1。在BST的操作以外，插入完后往上一层算平衡度(左树高减右树高)，如果要进行平衡，看被插入的子子树相对该结点位置。如果路径是LL或RR就单旋，如果是RL或LR就双旋(比如先在儿子左旋，再在该结点右旋)。删除也一样。
每次插入至多只需要做一次单旋或双旋。删除删成链状的话可能要两次。不过不想写那么细节的话还是都检查并更新了吧。
所有操作平均及最坏情况都是O(logN)。旋转平均只需O(1)。
Splay
思路是将要访问的结点比较平衡地旋转(Splay)到树根，这样访问比较频繁的结点都在树根附近。和AVL一样是看结点、父结点和祖父结点的走向关系，LL/RR就单旋/连续单旋(Zig/Zig-Zig)，LR/RL就双旋(Zig-Zag)。插入/查找都是旋转该点到根结点。删除则是把替换前的父结点旋转到根结点(有其他算法变种)。分裂是把作为分裂界的结点旋转到树根后切掉左子树或右子树变成一大一小两棵树。合并的话两棵树必须一大一小，把小树的最大元素旋转到根然后合并。
虽然单次最坏情况可能有O(n)，均摊复杂度也是O(logN)。长远来看比AVL平均更快，代码比AVL简单，还支持合并和拆分，不过不能用于并行环境中。
Red-Black
将结点分为红黑两类，所有空结点视为黑的叶结点，要求红结点必须连着黑结点，所有根到叶的路径黑结点数必须相同，而且根是黑结点。
插入时，插入点设为红。若父结点和兄弟同红，把父结点和兄弟变黑，祖父变红，然后回溯考虑祖父，直到1.父结点和兄弟异色，类似AVL，插入点是外儿子就做单旋/内儿子双旋，旋上去的结点为黑，另外两结点为红；2.父结点为黑；3.或已经到了根结点直接变为黑。
删除时，先按BST交换数据删除，若被删位置与其儿子一红一黑，把儿子涂黑放上来就好。如果都是黑，考虑放上来后的兄弟S及其内外儿子。若S及儿子全黑，变为父亲P黑S红。若仅S内子(RL/LR)红就双旋，其他情况(S/外子有红)单旋，新根与P换色，原来S的位置变黑。
以上过程已据Wiki简化，写起来还是略复杂，不过平衡度要求没有AVL严格。所以插入和删除相比更快，而查找更慢。
Treap
每个结点插入时加上一个随机的优先级，要求结点值满足BST性质同时优先级值满足堆性质。插入时比较插入结点和父结点的优先级，进行左旋或右旋。删除时则比较两个儿子的优先级，将要删除结点往下旋到叶结点删除。分裂时将分裂界插入并给予最大/最小优先级让它成为新根，一左一右就分好了。合并时比如A树根结点优先值小，A根为新根，B树根据A根分裂，然后递归合并A左子树和B裂后小子树，右子树和裂后大子树分别为新左右子树。没AVL平衡，有常数时间上差异，但代码比AVL等简单很多。
SBT
出于陈启峰大神的论文。保证每棵子树的Size比另一边子树的任意子树(也就是”孙树”)Size大。若外孙树大，单旋后依次递归旋下去的根和新根；若内孙树大，双旋后依次递归新的两个儿子和新根。
代码简单，同时因为记录了子树大小，可以很快找到第k大元素。
B(B-), B+, B* Tree
B(B-)：$M$叉树，根有$[2,\ M]$个儿子，其他内点$[\ \lceil M/2 \rceil,\ M]$个儿子，叶结点同高，遵循BST左小右大的原则，一个结点”儿子数-1”个值升序排列，每个值作为子树的值的分隔界(key)，并在树中只出现一次。插入时一个结点放不下了，就分裂，中间作key的值放到父亲里面，如此递归。删除时将要删的值和左子树最大值(在叶结点)交换。叶结点删了后若其左右兄弟的值有多，兄弟最大/最小值上移key拿下来，否则合并兄弟和key再递归此问题到父结点。

  • B+：相比B树，所有值都在叶结点出现一遍，内结点仅记录当前作为分隔界的值。且叶结点相互链接以方便连续访问一片值。插入时是把分裂出的新结点的最小值复制到内结点作为key，删除是直接找叶结点的值，其他同B树。
  • B*：相比B树，保证每个结点$\frac{2}{3}M$的值是满的。值太多先让兄弟保留，兄弟保留不下再二裂为三。

因为叉数多，深度浅，适用于访问结点代价昂贵的场合，如硬盘/数据库的读写。用数组存key会有不少空位，浪费空间，但在查找时可以用二分；用链表牺牲了查找效率但插入和删除比较方便一点。相比较而言，B树在记录每个子树大小后能快速访问第k大的点，B+树适合连续访问一片数据，B*比B-操作复杂但能节省空间。
Optimal Binary Search Tree
用于无插入和删除，知道每个值搜索概率的静态查找。设树中每个点代价=深度*概率(点权)，总代价是所有点代价和(Huffman Code是叶结点代价和)。因此用动态规划构建完全二叉树，状态为以序列第i个值开始的连续K个结点构建，状态转移时记录上一个状态来源，由此构建好树。

Trie
每个点表示一个字母，或者二进制里面一位。根为空，从根走到某结点表示一个单词或数字，并在末尾结点存其相应属性的树。数据稠密，长度不大或可以并行处理的情况下可能比Hash表表现的好而且不用考虑冲突或hash法。不过比Hash表更费空间。
Suffix Tree / Suffix Array
设原字符串为S
后缀树：因为在Trie上存了从任意位置开始的后缀，还为后缀属于哪个字符串做了标识，且Trie又可进行前缀搜索，而任意子串都必定是某后缀的前缀，这样后缀树就囊括了字符串的所有子串。因此可用于查找出现次数/重复次数/最长重复出现/最长回文/最长公共字串(两个字符串连起来做后缀树)等问题上。

  • 朴素(Suffix Tree)：先在最后加一个S中没有的字符(下称间隔符)，然后对S的每个后缀串建立Trie，这样所有后缀都在叶结点上。然后对所有单儿子的路径压缩成一点。

后缀数组：相比后缀树仍缺少了什么路径被压缩了的信息。可以求字典序相邻的两个后缀的最长公共前缀h[i]，这也就是每个后缀在后缀树中的树高。利用性质h[i]>=h[i-1]-1, 限定二重循环扫描确认前缀的范围就可以均摊O(n)求得h[i]。因为任意后缀的最长公共前缀是min{h[i:j]}，相当于LCA问题转化为RMQ问题，后缀树很多类似问题也可以由此推理得解。

  • 倍增算法(Suffix Array)：后缀数组即构建一个数组存储按字典序降序排第i的后缀的开头位置。每轮对S[j:j+2^i]这样定长2^i的子串根据字典序排序，排序方法根据上一轮结果对每个子串的两个关键字进行基数排序即可(无第二关键字就给最高或最低优先级)，到最后2^i>Len(S)的时候就是各后缀的后缀数组了。O(nlogn)
  • DC3算法(Suffix Array)：S最后先加一个间隔符得S’，然后S’[1],S’[2] (注意S’从0开始)补间隔符至长度是3的倍数后拼在一起得S*，然后对所有S*[j:j+2]进行基数排序，这样就得到了S中所有从3j+1和3j+2开始的后缀之间的顺序R。而3j开始的后缀之间的顺序可利用R和第一个字母进行基数排序得出R’。最后通过头字母和R与R’的比较，类似归并排序一样得到全序即可。O(n)，代码复杂度略甚于倍增算法。

Binary Indexed Tree / 树状数组
一个可以动态维护的用于求序列信息(一般是求和，要求信息可减，见后文)的树。设结点的序号i(i>=1)的二进制末尾0的个数是k，那么结点i就汇总前面K=2^k个结点的信息。求和时sum(i,j)=sum(1,j)-sum(1,i)，求sum(1,i)从i开始倒着来汇总就好了因为K必定不减，修改则是和sum相反从前往后就好。以上是一个数轴的情况，此方法可以组合应用于多个维度。

下面全部以小根堆为例，大根堆同理。除了基本的二叉堆没有合并操作外，其他堆结构基本都以合并操作为核心，插入等同合并，删除根等同合并子树，删除其他结点（注意这必须指定，堆本意就没打算查找最小结点以外的结点）则相当于把该节点的值改成无穷小，然后进行删除根操作（或者原地删除后合并子树并往上递归保证特定的堆性质）。
性能评价方面，堆查找最小都是O(1)，二叉堆没有合并且最坏O(N)，斜堆都是O(logN)的，左式堆常数上更优，二项堆插入均摊为了O(1)，Fibonacci堆删除以外都是O(1)。
Binary Heap
顶上是最小值，且每个子树都满足这个堆性质。用完全二叉树结构(数组存就好)，插入时插到最后然后上滤(递归地跟父结点比较)，删除时和队尾交换然后新根下滤，改小/改大分别则上滤/下滤。建堆则从最后一个非叶结点开始逐个下滤，直到根结点。
Skew Heap
二叉堆之余定义了特别的合并操作，无条件交换每层左右子树。合并时对于根小的堆A，其根作为新根，A右子树成为新左子树，然后递归A左子树和另一个堆的合并。
（非递归版合并：所有堆沿最右路径切片，形成的子树按堆根从小到大排序，每次最小堆变次小的堆左树，原左树变右树，然后排序继续）
Leftist Heap/左偏树
每个点记录到最近叶结点的距离，左子树的距离一定不小于右子树。合并时根小的堆A及其左子树保留，递归合并右子树和根大的堆，然后从下往上把不满足左偏性质的左右交换。
Binomial Heap(Queue)
每个二项堆实际是一个树序列(森林)，序列中i位置(中间可能有空位)是结点数为2^i的i叉树。合并时就相当于从序列低位到高位实行二进制加法，每棵树上的合并则是简单地让根值大的树直接作为根值小的树的子树(如果此前有进位，进位直接作为新堆该位的树)。可以通过在合并(包括插入和删除)时记录最小值所在的位置，从而让查找与其他堆一样是O(1)的。
Fibonacci Heap
核心思想是尽可能地延后各种操作。也是一个树序列(一般用双向链表表达序列和树每一层)。合并时宏观上一直合并到所有树大小不同(用一个以树大小为index的数组扫描)，微观上也是根大的直接做根小的子树。插入时直接放入序列不进行合并。改小内结点时，该结点为根的树放到序列上，然后mark父亲，父亲若mark过了，父亲为根的树也放上去然后再递归祖父。

数学&计算几何

这块内容过于分散，暂且不作总结。

思路/基本功

排序算法

ACM非常少用到，姑且就当算法课基础复习了

  • Bubble：每次第i个元素往上冒泡。稳定。
  • Insertion：每次第i个元素在已排序元素中找到应插入位置，后面的已排序元素逐个后移。稳定。
  • Selection：每次选未排序元素中的最大的，与数组最前面元素交换。不稳定。
  • Shell：设一个增量，相隔是增量的倍数的为同一组，分组插入排序；增量不断折半。不稳定。复杂度略大于O(NlogN)。
  • Quick：每次选一个Key，左右两端各自扫描，小于Key的放一边，大于Key的放另一边，扫描index仍未交错则交换元素，递进index继续扫描，递归分治此过程。Key的选择可以是固定，或优化为随机 / 前中后三元素比较选中值。不稳定。
  • Heap：建堆(从倒数第二层开始倒着逐个下滤)，逐个删掉根结点(下滤)，删完的数组就是了。不稳定。
  • Merge：分治到底回溯归并，每层用临时数组归并两端，再把归并好的值放回去。稳定。
  • Radix：从最次要的关键字开始，每轮用上一轮排好序的结果，再根据该轮关键字扫一次数组进行排序。如对数字排序则是从最低位到最高位每个进制位排一次。稳定。复杂度O(dN)，近似O(NlogN)。
  • Bin：将数据根据关键字分发到多个有序桶中，桶内有多个元素再进行上述的比较排序。稳定。
  • Intro：开始采用快速排序算法进行排序,当递归达到一定深度时就改为堆排序来处理。不稳定。

字符串匹配算法

设模式串P，待匹配串(文本串)T，问P是否是T的子串。匹配算法的核心思路都是出现匹配失败时，不要耿直地只移一位然后把匹配过的东西再扫一遍，而是利用对P的预处理，建立跳转表L，匹配失败时根据跳转表进行跳转。

  • KMP：思路是失败时，根据当下P已匹配串的后缀和前缀的相等关系跳过一段。L[i]=next[i]=k，每次T和P的第i位匹配失败时，可继续递归匹配P[L[i]]。优化后的KMP算法与L构建举例如图。
  • Boyer-Moore：既考虑T的匹配失败字符(Bad Character)也考虑P的已匹配字符(Good Suffix)。考虑Bad——建二维表L，不匹配就跳至L[T的不匹配字母，在P未匹配部分中且离匹配失败位置最近]。考虑Good——不匹配就跳至L’[已匹配后缀在P中前一个出现的位置且后缀前一个字符(匹配失败位)不相等(若后缀没出现则部分的前缀匹配部分后缀亦可)]。每次跳转max{L, L’}位。见这里
  • Horspool：L记录所有可能出现字母在与P最右的最小距离。从T左边开始，每次从P的右侧往左匹配，一旦发现不匹配，就跳L[T的对应P最右侧的字母]位，继续匹配。
  • Sunday：同Horspool，唯一不同在于不匹配时跳L[T的对应P最右侧的字母“的下一个字母”]位(所以最后一个字母也要计入T)。
    以上算法都是单字符串匹配，最坏情况O(nm)，均摊O(n)的算法，一般来说靠下的算法比靠上的算法常数时间上更有优势。下面是其他常见的字符串匹配相关算法：
  • Aho–Corasick(AC自动机)：应用于有多个模式串可匹配的场合。所有模式串先建立一个Trie，每个是模式串结尾的结点都标记一下(方便判断输出什么)，然后BFS遍历Trie，将字母相同的的结点连接起来(也称失败指针)。实际扫描模式串进行匹配时，一旦某一个结点不能继续往下匹配，就根据失败指针转移到另一个根字母相同的子树上继续寻找匹配机会。
  • Manacher：应用于寻找回文串的O(n)算法。核心思想同样是利用前面寻找回文串时得到的信息。定义p[i]是以i为中心的回文串往一侧延伸的最长长度(就是总长的一半)，就可以分情况如下利用已有信息。另外每个字母间都间插同一个特殊字符，就可以将所有偶数长度的回文串转为奇数长，方便运算。

Hash

Hash本身思想很简洁优雅，但考虑怎么减少碰撞减少麻烦上出了很多经验法或者无法理解的方法。下面仅摘取一些易记易用，效果也不错的Hash算法。注意在算法结尾求余时，一般选取较大的素数作为Hash表长度。

  • BDKR Hash：字符串哈希。不断h’=h*seed+s[i]，无视越界(unsigned)，其中seed=131（或31,1313,13131….）
  • DJB Hash：字符串哈希。不断h’=(h<<5)+h+s[i]，即*33，hash初值为5381。无视越界(unsigned)。
  • SDBM Hash：字符串哈希。不断h’=(h<<6)+(h<<16)-h+s[i]，即*65599，初值为0。无视越界(unsigned)。

  • 整数 Hash：都比较诡异。如h’=(h>>3)2654435761，或直接求余，见此，及此。
    .
    *搜索算法及技巧

  • 二分(折半)查找：顾名思义，不过变种比较多，剩下两个数就可以结束了，记得循环内要先写结束条件，循环后还要判断一下。

  • 双向BFS：两个方向交替逐层搜索(如果一边状态扩展慢很多可以优先多搜几层)。状态记录一般需要压缩或者哈希来实现判重。
  • 迭代加深搜索(ID-DFS)：逐步增加限定深度(一般每次+1)，每次从头开始DFS到限定深度。能够节约大量空间，时间复杂度不变(只是多花了常数倍)，适用于状态难以记录且状态数量增长很快的问题。
  • A*：对所有可达状态进行评估(f()=g()+h()，其中g是达到该状态代价，h是从该状态到结束状态的代价预估(启发式函数))。将初始状态加入优先队列，然后每次从优先队列中取出一个点进行拓展，将新的可达状态加入队列并更新已有状态的f。其中g保证最优性，h加快搜索速度；若两点启发函数之间的差值超过两点的实际转移代价(h大于g)，结果可能不具最优性。常见的h包括曼哈顿距离/对角线距离/欧几里德距离。可以通过g进行状态之间的区分，通过扩大h系数打破过多f相等的状况或进行加速。
  • 迭代加深A*(IDA*): 类似迭代加深搜索，不过限制变为f值，每次从头搜索并逐步加深。
  • 记忆化搜索：借鉴动态规划的思想，记录下每个搜索过的状态的最优值，从而实现很好的剪枝效果。

C++ STL
虽然STL和算法无关，但是由于STL的存在，很多数据结构不用自己写，是ACM比赛中必备外挂……下面直接罗列常用的操作。

容器：都有函数empty, size, swap。要求放入的对象实现==和<运算符。同一个容器内并没有多线程保护。

  • 标准序列容器：vector<> deque<>　list<>，内存分配分别是连续，小片连续，不连续。三类共有常用操作: begin, end, rbegin, rend, cbegin, cend, crbegin, crend。max_size, front, back。push_back, pop_back, assign(), insert(), emplace(), emplace_front(), erase(), clear。 get_allocator。注意不要用vector\因为它被压缩为一个元素只占一位，单个元素无法提取而且操作将会很慢(历史原因。至少请以deque替代)。而操作方面，size可能会耗费线性时间，返回的是无符号类型不要随意做减法。
  • 标准关联容器：set<> multiset<> map<,> multimap<,>，对应集合，可重复集合，一对一映射，一对多映射。都用红黑树实现，元素有序排列，效率O(logN)。四类共有常用操作：begin, end, rbegin, rend, cbegin, cend, crbegin, crend。max_size。insert(), emplace(), emplace_hint(), erase(), clear。key_comp, value_comp。find(), count(), lower_bound(), upper_bound(), equal_range()。get_allocator。
  • 容器适配器：queue<> queue<T,list<T>> stack<> stack<T,list<T>> priority_queue<> priority_queue<T, vector<T>, greater<T>>，标准序列容器变种，提供受限的底层容器接口，没有迭代器。队列和堆栈默认deque作为底层容器，优先队列默认使用vector作为底层容器。共有操作push, pop, emplace。队列还有front, back，其他则是top。
  • 似容器：string<> valarray<> bitset<>，valarray可以直接逐元素进行各种数学操作，bitset则能更好地进行各种位操作。
  • 容器迭代器：vector<T>::iterator vector<T>::const_iterator，后者不可以改元素值。
  • 其他：tuple<> pair<>：允许多种类型聚集在一起的定长容器。常见操作make_tuple/make_pair，get。tie(拆开tuple)。

常用算法：

  • 来自<algorithm>。sort(begin,end,cmp), 相比c的qsort，用的是intro_sort，不会退化。stable_sort。transform。unique, shuffle, fill, remove/find/copy/count_if, all/not_of, binary_search, lower/upper_bound。还有堆化和集合化容器上的操作不赘述。
  • 来自<functional>：包括plus,minus,greater等等，用以自定义函数对象，放到algorithm里面用。

算法可视化参考：
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

更清楚的算法总结Wiki参见NOCOW。

以下是被提到过但是觉得使用频率并不高的算法，或者本人尚不熟悉未能抽出时间学习的算法。鉴于时间有限，暂不再进行学习总结，包括：
Rabin-Karp, Finger Tree, Pair Heap, Blossom算法, Sollin算法, 度限制最小生成树, k小生成树, 均摊时间复杂度的分析方法(potential method), 差分约束系统, 模拟退火, ELFHash, Scapegoat Tree, 后缀树的Ukkeonen方法, 次小生成树/K短路，随机调整搜索，Dancing Links，遗传算法，蚁群算法，块状链表，树链剖分、Link-Cut Tree、悬线法动态规划、凸包、二分答案、贪心。