这里是OI知识点的总结

经过这几年的学习信息奥赛，现在此写下我的感受。

更新：2019年，NOIP取消，我成为了最后一界NOIP选手。以此纪念我三年的信息奥赛生涯

贪心算法

贪心算法指：求解某一问题时，做的某一个策略一直是局部最优解。每次将问题规模减少，直至减少到基础情况。

时间复杂度 \(O(n)\)~\(O(n\log n)\)甚至更高
空间复杂度 \(O(1)\)~\(O(n)\)或者更高

适合使用贪心算法的条件

具有最优子结构：一个题目的最优解，一定包含当前的局部最优解。这可以通过数学方法证明。
无需具有可后撤性
题目的数据范围极大，甚至无法用\(O(n\log n)\)算法拿满分
想不出正确的DP做法，试图通过奇怪的贪心拿部分分

适合配合使用的算法

随机化

对于无法直接贪心的题目，配合随机化，将贪心步骤打乱，可能会产生更优的解，以此更新最优答案。

调整

有些题目的正解是贪心+调整，每一步都采取贪心策略，将然后剔除部分不是最优的解，这样下去可能会产生最优解。

不适合使用贪心算法的情景

求解方案数
全局最优解和局部最优解极度不相关
数据范围较小，这种题目的正解显然不是贪心

动态规划

动态规划是一种依据子问题来确定当前问题的最优解的过程，一般是一种自底向上的做法。通常来讲，正解是贪心的题目一定有动态规划的做法，正解是动态规划的题目一定有搜索做法。通常递推的做法也可以算作动态规划。动态规划的核心是状态转移方程，每个状态只由已知的状态推导出。

适应于动态规划的题目

问题可以分解为若干子问题，子问题之间没有干扰，不具备后效性，做出一个决策只和当前状态有关，不会影响后续的状态
具有最有子结构，全局最优解一定是由局部最优解构成
子问题具有重叠性，每个子问题都是一样的。

不适应于动态规划的题目

数据范围较大，不适合\(O(n^2)\)的时间复杂度。这一点有例外，将在后来讲。
决策具有后效性，当前的决策会影响后来的决策，或其他子问题的决策。这一点可以通过拓扑排序或dfs序排序来消除。如果不能消除，则不存在有效的动态规划做法。
过于复杂的题目，动态规划做法很难写对，这属于个人问题。
显然存在贪心做法的题目
各种数据结构题

动态规划的题型

区间DP

常见的题目描述是，给定一个长度为n的序列，他们有xxx属性，要求某个全局最优解。通常按照合并区间的方法进行DP，以石子合并为例，有方程\[f_{i,j}=\min \{f_{i,k}+f_{k+1,j}\}+sum[i][j]\] #### 线性DP 常见的题目有求两个字符串的最长公共子串、子序列、编辑距离等，也有求一个序列的最长上升子序列，还有一些算法，比如线性筛算法，也可以规划到线性DP中（虽然比较少见） #### 树上DP 这一类DP是在树上进行的，利用DFS的顺序进行转移，通常状态多而杂，很容易写错，但这类题目的正解一般只有这一种。例题有：没有上司的舞会、树型依赖背包问题 #### 背包DP 背包DP是比较常见的一类DP，有01背包、完全背包、多重背包、有依赖关系的背包、分组背包、最后是泛化背包，这些将在后面讲解。 #### 状压DP 利用数字的性质，将某种状态转换为整数来存储，在此基础上DP #### 环形DP 一般这种情况可以复制一份，转换成线性DP或区间DP，然后在新的数组上DP。 #### 方案DP 如果一个题目要求求出方案数，可以将初始状态设为0，直接+=。 #### 数位DP 针对某些数据范围极大的数学题，求具有某些特点的数字的个数 #### 图上DP 可以利用拓扑序dp，也可以用jarjan算法缩点后，建立一棵树再进行dp #### 插头DP Q:什么题目使用插头dp? A:关键词：超小数据范围，网格图，连通性。 Q:什么是“插头”？ A:一个格子通过某些方向与另一个格子相连，这些连接的位置叫做“插头”。形象地理解，网格图上每一个格子是一块拼图，那么两块拼图的接口就叫做“插头”。

对于动态规划的优化

预处理

对于一些和状态无关的变量，可以进行预处理，比如前缀和，做到\(O(1)\)查询。

数据结构优化

对于一些形如\[f_i = \sum \limits_{j\lt i}\{f_j\} + a_i\]的转移方程，可以用树状数组、线段树来加速转移，使时间复杂度由\[O(n^2)\]降低到\[O(n \log n)\] 一些求最大最小值的状态转移方程，可以用优先队列优化，复杂度同上。

单调队列/栈优化

对于\[f_i = \max \limits_{a\le j\le b \lt i}\{f_j\} + a_i\]形式的转移方程，可以采用单调队列优化，每次直接取出最优解，再维护最优解。具体来说，这应该维护一个单调递减的单调队列，每次取队尾，如果队尾元素过期，则将它出队。更新当前状态后，要将队头的非最优元素出队。时间复杂度是\(O(n)\)的

斜率优化

对于一些带有平方项的状态转移方程，状态是关于\(i,j\)两项的，这时就不能直接利用数据结构优化了。不过还是有优化的方法的。

首先进行一波公式推导，发现对于当前状态\(i\),有\(j,k\)两个状态可以转移，其中\(j\)更优的条件是 \[ \frac{a_j-a_i}{j-i} \lt \frac{a_k-a_i}{k-i}\]则可以在单调站内维护一个下凸包，每次取出最优解，入栈时维护单调站的性质来加速转移。

背包问题

很多问题都可以转换成背包问题，背包问题的描述是这样的：给定一些物品，编号1-n，有价值和体积。现在有一个容量为V的背包，求怎样装可以做到价值最大、或者求符合要求的方案数。几乎所有背包问题都是用DP来做的。 ### 01 背包和完全背包有状态转移方程\[f_j= f_{j-w_i}+v_i\]，j是体积，阶段i隐藏在转移过程中，表示当前的背包装填了1-n的若干物品，用了j容量的最大价值。区别是，01背包要从后向前转移，为了避免当前阶段的决策对当前阶段其他状态的影响；而完全背包没有这个限制，甚至需要这个“副作用”。时间复杂度\[O(NV)\]，空间复杂度\[O(V)\] ### 更大体积的01背包这一类问题的特征是，\[n \approx 40\]，\[j\]更大，甚至达到1e9，显然传统的做法是没法做的，直接枚举选择物品会超时。这时可以将物品分为两部分，每部分约20个。之后枚举一组的所有情况，存到一个map中，然后对另一组做同样处理。处理好之后，对第一组的每一个可以选的状态，在第二组里查找可行解，组合、记录最优解。时间复杂度\[O(2^{\frac n 2}\log 2^{\frac n 2})=O(2^{\frac n 2})\] 可见，它和体积无关。 ### 分组背包对于一个分组，只能选择一样物品，那么就把这些物品捆绑起来，枚举怎样选择，就可以了。 ### 多重背包每个物品有k件，求体积限制内最大价值。可以枚举件数，也可以二进制拆分成\[\log a_i\]件单一物品，一般这就足够了。另外有剩余类的单调队列优化，对于某一个状态\[f_i\]，它只会被用来更新\[f_{i+kv_i}\]，所有\[i \mod v_i\]构成一个剩余类，我们开多个单调递减队列，分别维护每个剩余类的最大值，再转移就好了。时间复杂度\[O(NV)\] ### 依赖背包给定多个物品，其中每个物品可以被选择，仅当某一个特定的物品被选择，就限定体积内的最大价值。形象的理解是”进化树“ 这样的题目有津津的存储计划，访问艺术馆等津津的存储计划这道题，每个物品只能被两个物品依赖，依赖关系只有一层，更优的做法是，将每个被依赖的物品拆成4个，然后进行01背包的求解。访问艺术馆就没这么简单了，它需要实打实地进行依赖背包的dp。思路是，把每一个物品都看做一个背包，对于每一个体积，都有特定的价值，然后问题成了给定若干个背包，要求按顺序合并这些背包。合并中的需要处理的地方有、如果某个背包是被依赖的，合并它的子物品所代表的背包时，要加入一个容量上的偏移，这个偏移就是主件的体积。再建立一个虚拟物品0，所有物品都依赖它，然后0背包的解就是答案了 ### 多重依赖背包这种DAG背包问题有两种，一种是魔兽地图类型的，经过预处理后，可以转换为传统的背包问题；另一种是”科技树“、”软件包管理器“类型的，无法转换为传统背包问题。第一种无非码量大一些，预处理后按照常规方法可以解决。第二种是无法在多项式时间内处理出来的，因为它具备后效性。如果试图转换成图来做，节点数目也是\(O(2^n)\)级别的，边的数目会更多。所以只能搜索或者枚举，参考更大体积的01背包

搜索&穷举算法

几乎任何题目都是可以通过搜索或穷举做出来的。缺点是复杂度极高。搜索的复杂度可以称玄学\(O(\frac {n!} {XuanXue})\)，但是通常不会跑满 ### 技巧没有后效性的搜索，可以通过记忆化来实现，这和DP是等价的。有时候因为思维难度低，复杂度跑不满，也非常优秀。复杂的状态可以通过哈希来存储，略微有些冲突一般不会影响到答案。剪枝是很有必要的，有些题目没有图论、结论、Dp、贪心做法，就只能搜索。剪枝的优秀性和数据强度决定了搜索算法的分数。

模拟

多用结构体，多写函数。模拟时要按照题意来，不要偷懒，也不要理解错误，别的没什么好说的。

图论

最短路

最短路是图论里最经典的题目。

算法名称	适应条件	时间复杂度
Dijkstra	不存在负权边、在稠密图上性能良好、求单源最短路	\(O((V+E)\log E)\) 或\(O(E + V \log V)\)
SPFA-- 队列优化的BellmanFord	稀疏图、单源最短路	\(O(kn)\)到\(O(n^2)\)
Floyd	稠密图、多源最短路	稳定\(O(n^3)\)

最小生成树

最小生成树的性质有：两点之间的边权最大值最小，在连通的所有子图中，所有边权之和最小

算法名称	适应条件	时间复杂度
Prim	稠密图中表现良好	\(O(Elog V)\)
Kruskral	稀疏图中表现良好，实现简单，常数小	\(O(Elog E)\)

强连通分量

常用算法有tarjan算法。tarjan可以做的事情有很多，比如求强连通分量、缩点、求割点、求割边。通过tarjan算法，可以将一个图转换成DAG，进而可以进行拓扑排序，这是tarjan非常重要的应用。

欧拉回路

欧拉回路指，经过所有边恰好一次的一条路径。做法很简单，dfs即可。确定入点后，遍历完一条边后标记一下，dfs退栈时将当前点加入一个栈中，最后将栈内元素取出就是经过的路程。

二分图

二分图匹配是什么，自己百度吧…有一些题目是需要用二分图匹配的做法的，比如某些棋盘放置，求方案的问题，用二分图匹配的复杂度远低于搜索。

bool dfs(int u,int vistime) {
/*
    *vistime为时间戳
    *具体的，对于点u，如果dfn[u]<>vistime
    *则点u在本轮匹配中还没有被匹配到
*/
    for(rg int i=hd[u];i;i=edge[i].nxt) {
        int &to=edge[i].to;
        if(dfn[to] != vistime) {
            dfn[to]=vistime;
            if((!mch[to]) || (dfs(mch[to],vistime))) {
                mch[to]=u;return true;
            }
        }
    }
    return false;
}

## 数论

关于求素数、欧拉函数的算法参考我之前的文章。 ### 最大公约数

简单的欧几里得算法就可以解决\[\gcd(a, b)= b==0?a : \gcd (b,a\mod b)\]

最小公倍数

有公式\[lcm(a,b)=\frac {ab} {\gcd(a,b)}\]

拓展欧几里得

拓展欧几里得算法如下：

void gcd(ll a,ll b,ll &d,ll& x,ll& y){
    if(!b){ d=a, x=1, y=0; }
    else{ gcd(b,a%b,d,y,x); y-=x*(a/b); }
}

扩展欧几里德算法的应用主要有以下三方面： 1. 求解不定方程 \(ax+by=c\) > gcd(a,b) = gcd(b, a%b) > ax+by=gcd(a, b) > =>bx+(a%b)y=gcd(b,a%b) > b = 0时，x = 1, y = 0 > 然后就可以回溯回去了 2. 求解模线性方程（线性同余方程） 3. 求解模的逆元

Jeekr's site

NOIP知识点总结