Skip to content

Latest commit

 

History

History
179 lines (99 loc) · 8.45 KB

011.算法梳理：中级篇.md

File metadata and controls

179 lines (99 loc) · 8.45 KB

原文

算法梳理：中级篇

中级篇

  1. 二分搜索

  2. 常用技巧

  3. 数据结构（二）

  4. 动态规划（二）

  5. 网络流

  6. 计算几何

2.1 二分搜索

2.1.1 核心思想

二分搜索：对于某个有序区间，每次查找区间中点是否满足条件，并以此为依据，决定递归查询左半区间或右半区间。 反复循环上述折半过程，直到条件或精度被满足。

2.1.2 优化细节

  1. STL：以函数lower_bound()和up_bound()的形式实现了二分搜索

  2. 结束判定：1次循环可将区间减半，循环100次可达到精度10^-30 。 还可通过区间长度与EPS判断，但要避免EPS太小因浮点数精度问题造成的死循环。

2.1.3 经典模型

  1. 有序数组中查找某值

  2. 判断一个假定解是否可行

  3. 最大化最小值

  4. 最大化平均值

2.2 常用技巧

2.2.1 核心思想

  1. 尺取法：又称两点法，通过在区间上标记并顺序移动头尾两点，将复杂度降为线性。

  2. 反转（开关问题）：若为初末态确定，则可通过贪心求得最少步骤。高斯消元法也可求得一组可行解，且自由变元有限，所以也可以求得最优解。

  3. 集合的整数表示：通过二进制将集合状态映射至整数。涉及到的位运算包括：与、或、非（取反）、 异或、取负（取反+1）、逻辑左移右移、交、并。遍历所有子集或找到所有大小为k的子集，都可以通过位运算操作求得字典序升序的二进制码。

  4. 折半枚举（双向搜索）：当全局枚举复杂度太大时，可将条目折半，分别枚举所有情况。复杂度降为原本平方根。

  5. 坐标离散化：将数列排序并去重，将原数列离散化映射至有限可控的区间。

2.3 数据结构（二）

2.3.1 核心思想

  1. 线段树：是一棵完美二叉树，树上的每个节点表示一个区间。 根节点维护整个区间，其他每个节点维护父节点二分后的某个区间。查询和更新复杂度都是O(logn)。

  2. 树状数组（BIT）：将线段树每个节点的右儿子去掉，用每个节点表示区间的右边界代表该节点的索引， 这样就可以通过一个线性数组维护所有必要的区间。 索引的二进制最低位的1表示区间长度，值为x&-x。求和和更新复杂度都是O(logn)。

  3. 平方分割：将n个元素装入√n个桶内，每个桶√n个元素的分桶法，每个桶分别维护自己内部的信息。 对区间的复杂度操作可降至O(√n)。

2.3.2 优化细节

  1. 懒惰标记：线段树可以通过在父节点上维护一个懒惰标记，来表示整棵子树的状态。 在自顶向下的查询操作中，在递归该父节点时，将标记下移至两个儿子节点，并且更新父节点真正维护的直接变量。

  2. 稀疏表：与线段树类似的是其区间长度都是2的整数次幂，但每个长度层级的区间左端点都连续。 进行RMQ查询时，只需要找到不大于区间的最大2的整数幂，根据这个长度，待求解的左端点及右端点减去长度即为该行在稀疏表内的列的值。 预处理时时间和空间复杂度都高达O(nlogn)，但结合二分查找的单次查询比线段树快，只需要O(loglogn)。

  3. 维护多项式：如果需要维护的变量可以表示为索引i的n次多项式，则可以用n+1个树状数组来维护。 或者，线段树的每个节点维护n+1个值。

  4. 区域树：线段树的每个节点可以维护一个数组或维护一棵线段树，适合对矩形的区域进行处理。 并且，和树状数组一样，多重线段树嵌套可以实现高维度的区域树。

2.4 动态规划（二）

2.4.1 核心思想

  1. 状态压缩DP：通常结合进制数的特点，将每个状态压缩表示为整数。复杂特殊状态的转移就可以表示为整数下标的等式。

  2. 矩阵快速幂：若动态规划的递推关系式可以表示为多元一次多项式，则可以通过某常系数矩阵的幂与初始向量的乘积求得最后的结果向量。 其中求幂可以结合基于二分思想的快速幂算法。用n表示幂次数，m表示向量规模，则复杂度为O(m^3logn)。

2.4.2 优化细节

  1. 结合数据结构：某些时候涉及到更新和查询操作时，如果利用线段树等高级数据结构处理，可以使得转移方程中线性的遍历转化为对数级别的查询。

2.5 网络流

2.5.1 核心思想

  1. 最大流：增加反向补偿边，在残流网络上不断寻找增广路。常用朴素寻找增广路的Ford-Fulkerson算法，复杂度为O(FE)。 通过最短路算法预处理为分层图的Dinic算法，复杂度为O(EV^2)。

  2. 最小割：将割中的边全部删去后，源点无通路可再到达汇点。最小割是最大流的强对偶问题，数值相等。

  3. 二分图匹配：匈牙利算法递归每个顶点，每次递归，将已有匹配删除看能否得到更优解。

  4. 一般图匹配：常用Edmonds算法，较为复杂，尽量转化为二分图求解。

  5. 最小费用流：在残流网络上扩展最短增广路时，使用边的花费作为边权寻找最短路。 f(e)表示e中的流量，h(v)表示势（残流网络中s到v的最短路），d(e)表示考虑势后e的长度。 复杂度为O(FElogV)或O(FV^2)。或者通过不断消去负圈得到最小费用流。

2.5.2 优化细节

  1. 最大流变体：

    • 多个源点汇点：构造超级源点S和汇点T，用S连至多个源点，所有汇点连至T。

    • 无向图：构造正反方向的两条边，容量与无向边相同。

    • 顶点也有流量限制：将每点拆为入点和出点，入点至出点连边。

    • 最小流量限制：构造超级源S汇T，对于每条边构造逆向的容量为下限的满流圈；连接S到s及t到T之前，通过满流判断可行解。

    • 部分边容量发生变化：若影响原流，则设法将残流网络中对应边的容量减少或通过构造逆向圈等价减少。

    • 容量为负数：求最小割时可能出现负边，此时应通过数值变换设法消除负边。

  2. 最小费变体：

    • 类最大流变体：构造方式相似。

    • 最小流量限制：将原边容量减少下限，构造新边容量为下限且费用为原费用减去一个足够大的数。

    • 流量任意：由于点的势会不断增加，所以仅在势为负数时增广，即能保证费用不断减小。

    • 费用为负：不能用Dijkstra算法，要用Bellmen-Ford算法处理负权边。 另外，可以通过对所有边的费用和最终结果进行适当的变形避免负权边。

    • 最小化有流边的费用之和：无法通过最小费用流模型求解，需要建其他模。

  3. 匹配相关对偶问题：

    • 连通图中，最大匹配+最小边覆盖=顶点数

    • 最大独立集+最小顶点覆盖=顶点数

    • 二分图中，最大匹配=最小顶点覆盖

2.6 计算几何

2.6.1 核心思想

  1. 平面扫描：扫描线在平面上按既定轨迹移动时，不断根据扫描线扫过的部分更新，从而得到整体所求结果。 扫描的方法，可以从左向右平移与y轴平行的直线，也可以固定射线的端点逆时针旋转。

  2. 凸包：包围原点集的最小凸多边形的点组成的集合，称为原点集的凸包。凸包上的点不被原点集任意三点连成的三角形包含在内部。 通过Graham扫描算法，将点集按坐标排序后，分为上下两条链求解。每次末尾加入新顶点，如果出现了凹的部分，则把凹点删去。 Graham可以在O(nlogn)的时间内构造凸包。最远点对一定是凸包上的对踵点，可以通过旋转卡壳法不断找寻对踵点，在O(n)复杂度内求解。

  3. 数值积分：通常在复杂的几何相交或求和问题中，通过对某个方向变量的微分，将立体切片或将平面切成线段后积分得到结果。

2.6.2 优化细节

  1. 向量表示：可以使用STL的complex类表示向量，并进行相应的内积外积操作。

  2. 计算误差：计算几何中的浮点数大小比较采取与ESP结合的方式，如a<0等价于a<-ESP，a≤0等价于a<ESP。 由于double类型的精确尾数大约是10进制下的15位，当ESP太小时，可能造成假阴性。 C++中可以采用更高精度的long double，Java可以使用BigDecimal。

  3. 极限情况：当可行解可以取连续一段值时，很多时候只要考虑边界的极限情况。