本文写于2015年暑假，当年文笔稚嫩，且内容并不全面，仅供参考。总结内容包括搜索、图论、动态规划、数据结构与数论等。

搜索

DFS

深度优先搜索（Depth-first Search，DFS），基于递归的搜索方式，它的特点是由一个状态拓展一个状态，然后不停拓展，直到找到目标或者无法继续拓展结束一个状态的递归。可以在数列中进行搜索，也可在坐标系中进行搜索。

BFS

广度优先搜索（Breadth-First Search，BFS），基于队列这种数据结构的搜索方式，它的特点是由每一个状态可以扩展出许多状态，然后再以此扩展，直到找到目标状态或者队列中头尾指针相遇，即队列中所有状态都已处理完毕。

优缺点

DFS：对于解决遍历和求所有问题有效，对于问题搜索深度小的时候处理速度迅速，然而在深度很大的情况下效率不高

BFS：对于解决最短或最少问题特别有效，而且寻找深度小，但缺点是内存耗费量大（需要开大量的数组单元用来存储状态）。

剪枝

由于时间和空间的局限性，搜索一般只能解决数据量小的问题。所以我们需要用不同的方法剪枝。剪枝方法包括：

记忆化搜索（与DP类似）；
从方法上剪枝，如采用分枝定界，启发式搜索等，适用范围较广；
双向进行搜索或者反向进行搜索；
使用其它小技巧，例如卡时。这类方法适用性虽不如以上，有时甚至只能适用一道题，但也十分有效，并且几乎每道题都存在一些这样那样的剪枝技巧，只是每题有所不同而已。

图论

图论是一个应用十分广泛而又极其有趣的数学分支。图即是由若干个不同顶点与连接其中某些顶点的边所组成的图形。
图的存储方式有邻接矩阵、边集数组和邻接表，其中邻接表适用于数据规模比较大的图的存储，也比较好用。

图的遍历

图的遍历有两种遍历方式：深度优先遍历和广度优先遍历。

最短路径

即求任意两点之间的最短路径。
四种最短路算法：

Floyd算法：三重循环，枚举每一种三个点的组合，可以一次求出任意两点的最短路。是一种动态规划算法，对于稠密图效果最好，边权可正可负。O(n^3)
Dijkstra 算法：单个源点到其他顶点的最短路，蓝白点思想，找dis最小的u，更新v。不适用于负边权，可以进行堆优化。未优化O(n^2)，优化O(nlogn)
Bellman-ford 算法：迭代n-1次，检查每条边，进行多次松弛操作，可发现负圈。O(nm)
SPFA：用FIFO队列代替Bellman的循环检查。O(nlogn)，较为常用

SPFA在稀疏图上快，因为它是通过边来增广的。
Dijkstra在稠密图上快，因为它是通过点来增广的。
某些情况下dijkstra加上堆优化在处理大数据时会比SPFA快很多，但SPFA在随机数据的综合表现中相比dijkstra优势更大

最小生成树

求图中权值最小的生成树。
两种算法：

Prim 算法：蓝白点思想，min[v]表示蓝点与白点相连最小边权。贪心思想。O(n^2)
Kruskal 算法：适用于稀疏图。利用并查集，将边权排序，不在同一个集合就连。O(eloge)

拓扑排序

适用于有向无环图，使每个点排在它所指向的点的前面。入度为0的入栈，没有就将栈顶元素出栈，将此点删掉。O(v+e)

强连通分量

对于一个强连通分量中的任意一对顶点(u，v)，都能够保证分量中存在路径使得u->v，v->u。可缩点成为DAG
两种算法：

Kosaraju 算法：两次dfs，第二次将边翻转 O(v+e)
Tarjan 算法：找代表元，记下u能回溯到的最早的顶点的编号与u被搜索的编号。 O(v+e)

二分图匹配

当且仅当图的点可被划分为两个内部两两之间没有边的部分。

判定：dfs交替染色
最大匹配：匈牙利算法：从每个点找增广路，如果有，把此路上匹配边和非匹配边互换，得到匹配比之前多1
最小点覆盖数=最大匹配数最大独立集数=总点数-最大匹配数

动态规划

动态规划（Dynamic Programming，DP）是一种思想与手段。
动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

明确阶段、决策、状态和状态转移方程。
状态转移方程是核心。
适用动态规划的问题必须满足最优化原理和无后效性。

普通的动态规划

序列型(最长上升子序列)、区间型(石子合并)、棋盘型(过河卒)、划分型(乘积最大)动态规划。

背包型动态规划

01背包(可用滚动数组)、完全、多重、混合、二维、分组、有依赖。

状态压缩动态规划

一些问题状态中所包含的信息过多，如果要用数组来保存状态的话需要四维以上的数组。所以需要通过状态压缩来保存状态。用二进制的一个数来表示一种放法。将1和0分别表示两种状态，二进制数可以表示出所有状态。

树形动态规划

树的最大独立集：节点u两种决策，不选，则问题转化为求出u的儿子的值，选，则所有u孙子加上自己。
树的重心：dfs，u为根的子树节点等于它所有儿子节点的值加一。删掉u后，最大的连通块的节点数即可求出。
树的最长路径：对于每个节点i，把所有根为其子节点的子树中根到叶子的最大距离求出，找出值前两大的相加再加2即为所求。

动态规划的优化

数据结构优化：可用树状数组、线段树对所求最值进行优化。
单调队列优化：单调队列是一种严格单调的队列，可以单调递增，也可以单调递减。队首位置保存的是最优解，第二个位置保存的是次优解…利用单调队列对dp方程进行优化，可将O(n)复杂度降至O(1)。只有形如 dp[i]=max/min (f[k]) + g[i] （k<i && g[i]是与k无关的变量）才能用到单调队列进行优化。优化的对象就是f[k]。
斜率优化：对于这样的一类DP方程f[i]=min{a[i]*x[j]+b[j]}，a[i]是和i有关的函数，x[j],b[j]是和j有关的函数或常数。求解这个问题朴素是O(n^2)的，可以将它优化到O(n)或O(nlogn)。把它改写为-a[i]*x[j]+f[i]=b[j]，
把-a[i]看作斜率，f[i]看作截距，每一个决策相当于平面上一个点。最优决策在平面点集的凸包上。要求f[i]的最小值，就相当于将一条斜率为-a[i]的直线不断向上平移，碰到的第一个点就是截距最小的点。也就是f[i]的最优决策。

数据结构

数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关

基本数据结构

栈，队列，堆，链表，并查集，树（二叉树、多叉树、森林）

树状数组

是一种查询和修改复杂度都为log(n)的数据结构。主要用于查询任意两位之间的所有元素之和，但是每次只能修改一个元素的值。
lowbit(x)=x&-x (-x为x按位取反，末尾+1)。一个节点存这个数二进制下最右边1所对应值到它自己。前缀和Si，顺着i往左上走，修改Ai，从Ci往右上走。
注意是改成一个值还是添加一个值。

线段树

线段树是一种二叉搜索树，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。使用线段树可以求最大值、最小值、区间和等，或者单点修改、区间修改。时间复杂度基本为O(logN）。
注意边的数组范围，一般要开四倍。

查询：当前结点完全包含在查询区间？；向左；向右。
单点修改：若是叶节点，直接更新，else 递归更左或右，再更本节点。
区间修改：把一个lazy操作分解成不超过2h个，完全包含时，累加边界的lazy值(递归结束前维护此点信息，即此点及其祖先都会被维护)(查询时，考虑祖先节点对它的影响，增加一个参数表示当前区间所有祖先节点lazy值之和)
值域线段树：可求逆序对，可求整个区间第k大。

分块

N可分成长度根号N的根号N块区间。

莫队

(不带修改，询问离线) 先分块，排序(左端点所属块编号，右端点大小)；按排序for，转移到下一个时，for出少了的，for掉多了的。

可持久化数据结构

部分可持久化：链形；完全可持久化：树形；
用新建节点取代修改节点信息。(指针、vector)
主席树属于可持久化线段树，求区间第k大，对于序列的每一个前缀建一棵以序列的值为下标的线段树(可离散化)，记录该前缀序列里出现的值的次数。

平衡树

Treap：略
Splay：把要查询的x提到根节点。单旋，双旋。插入，查询，同BST；删除时，把左子树内最大的splay上来，将右子树接到右边(两个儿子时)，前驱后继，对节点splay然后找到左右子树中最大或最小。

树上信息维护

DFS序：性质：一棵子树其节点一定在一段连续区间中；
祖先关系判断，子树和(换根，前缀和：距离、路径上第k小。
欧拉(括号)序：出子树时节点也加在序列中：路径点权和(LCA转化为RMQ)

树链剖分

将树剖成不向交的链。向下连size大的，存一个top，树链剖分得到的序列也是dfs序。分成的链(连起来)作为维护的序列。

性质：如果(v,u)为轻边，则size(u)*2<size[v];从根的某一点的路径上轻链，重链的个数都小于logn。把一些点(边)合成一条路径，使其在线段树的编号(下标)有序(线段树中每个点可是原树的点或边) 注意区间中的每个点不是作为树的点。

树的点分治：

树的重心：遍历所有点，删除此点后，最大的那一块最小 min{max(size)}
性质：删除重心后最大的那一块不超过树的一半。
重心C：分为过C的路径和在C的子树中的路径。

数论

数论是纯粹数学的分支之一，主要研究整数的性质。
做数论题前，一般先在纸上推出公式或找出规律，再用各种定理或者是方法处理大的数据。

欧几里德和扩展欧几里德定理

欧几里德即辗转相除，目的是求最大公约数， gcd(a,b)=gcd(b,a%b), 有存在性唯一性，复杂度O(logn);
扩展欧几里德，ax+by=gcd(a,b)，求满足的x、y。x1=y2, y1=x2-(a/b)y2；x1与y1的值可由x2、y2推知，拓展欧几里得算法就是不断地的将b放小，直至b等于0，最后反推求回x和y。主要用于解不定方程、解线性同余方程。
注意：x*y=gcd(x,y)*lcm(x,y)

唯一分解定理(算术基本定理)

N可以唯一分解成有限个质数的乘积N=p1^a1+p2^a2+p3^a3……+pk^ak;
唯一性证明：若p|ab，则p|a或p|b。设n= p1^a1+p2^a2+p3^a3……=q1^b1+q2^b2……
N为最小的不符合的数，则p1|q1^b1+q2^b2,即q1q2…中有一个能被p1整除，不妨设为q1，而q1为质数则p1=q1。假设a1>b1，p1^a1-b1p2^a2…=q2^b2q3^b3…。同上p1能整除q2,q3…中的数，但p1=q1!=qi 所以不存在a1>b1。同理a1不会小于b1，所以a1=b1。那么n0= p2^a2+p3^a3……= q2^b2……,而n是最小有多种分解的，
所以n0只有一种分解，推出n只有一种分解。

欧拉函数

欧拉函数是积性函数，欧拉定理 (a,n)=1则a^φ(n) ≡1(mod n)。
欧拉筛法求欧拉函数，欧拉筛法筛素数即线筛。复杂度 O(n)
线筛：对于当前的一个数i，欧拉筛法把从2，3，5…到小于 i 的最大素数分别和 i 相乘得到的数标记成合数。并且过程中一旦发现 i % （p[j]） == 0，则跳出循环。保证每个合数只被他的最小素因子筛到一次

快速幂，矩阵快速幂

用到了二分的思想，快速高效的求a^b mod m. O(logn)
将所求的幂不断除以2，改变底数，注意要先乘再模。
矩阵乘法：m $\times$ n与n $\times$ p -> m $\times$ p 。第[i,j] 上的数为矩阵一第i行上的n个数与矩阵二上第j列上的n个数，对应相乘的积之和。
矩阵快速幂，即将矩阵乘进行快速幂，可用于求一些数列。