算法学习笔记

（四边形不等式看标题可能觉得很难，其实比较简单） 四边形不等式是一种DP优化的技巧，一般针对二维DP进行优化。 在DP中，往往会有多个决策点，而其中就有一个是最优的，设 $d_{i,j}$ 的最优决策点为 $f_{i,j}$。 （以下假设DP枚举决策点的复杂度为 $O(n)$，DP状态数为 $O(n^2)$） 而四边形不等式就是说，如果满足 $f_{i,j-1} \leq f_{i,j} \leq f_{i+1,j}$，那么可以把DP枚举决策点的范围降至 $[f_{i,j-1},f_{i+1,j}]$，然后DP的复杂度就从 $O(n^3)$ 降到了 $O(n^2)$。 而这个（复杂度）怎么证明呢？我们画一下 $f$ 数组的表： （此处，我们以 $i$ 为行号，以 $j$ 为列号，行、列号都从 $1$ 开始编号） 然后，画几个标记： 这些标记指的是，在转移 $d_{1,2}$ 的时候，转移点枚举的左右端点分别就是红箭头指向的两个数。 同时，为了方便观察，此处还画了个蓝色的虚线。 同理，还可以画出 $d_{2,3}$ 对应的标记： 以此类推： 可以发现，其实这时候所有蓝线的长度（蓝线连接的两个数字的差值定义为这个蓝线的长度）之和，最多只有 $n$。 而对于 $d_{1,3}$ 一“类”的标记： 可以发现，其实那些蓝线的长度之和也是最多只有 $n$。 在画出所有蓝线之后： 可以发现，一共就有 $n$ “类”蓝线，一“类”蓝线的长度之和最多 $n$，至此，可以证明复杂度（所有蓝线的长度之和）为 $O(n^2)$。 接下来讲几类四边形不等式解决的经典题型： 第一类：$d_{l,r}=\min { d_{l,k}+d_{k+1,r} | l \leq k \leq r }+w_{l,r}$，合并石子类。 第二类：$d_{i,j}=\min { d_{k,j-1}+w_{k+1,i} | 0 \leq k \leq i }$，区间分割类。 （这两类对应的公式里的 $\min$ 也可以替换成 $\max$） ...

同余最短路看名字感觉很难，但其实非常简单，也好理解，先说一道题： 题目 原型：洛谷P3403 跳楼机 有一栋 $h$ 层的大楼（层数编号从 $1$ 到 $h$），有 $n+1$ 种移动方式： 回到 $1$ 层 向上走 $x_1 \sim x_n$ 层 楼层不是循环的，你无论如何都无法到达 $h+1$ 层或以上。 最初你可以在任意一层（但也无关紧要），问你能到达多少个不同的楼层。 题解 分类 我们按楼层模 $x_1$ 的余数分类，把楼层 $i$ 分到 $i \bmod x_1$ 类。 这样分类有什么用呢？见下。 定义状态 有了这个分类，我们可以定义状态 $d_i$（$i \in [0,x_1)$）代表不用「向上走 $x_1$ 层」操作能到达的、最小的第 $i$ 类楼层是多少。 那么，由于有「向上走 $x_1$ 层」操作，所以 $d_i,d_i+x_1,d_i+2x_1,\dots$（比 $d_i$ 大或相等的第 $i$ 类楼层）都是可达的。 接下来考虑转移这个状态。 转移 其实也很好想，比如用一次「向上走 $x_2$ 层」操作，那么 $d_i$ 可以转移到 $d_{(i+x_2) \bmod x_1}$，转移代价为 $x_2$，所以： $d_{(i+x_2) \bmod x_1}=\min(d_{(i+x_2) \bmod x_1},d_i+x_2)$ ...

前言 首先，网络流不是一个算法，而是一个整合包（玩MC玩的），说白了就是网络流是多个算法的统称： 最大流 EK Dinic 最小割 费用流 … 而且，有些不常用的，可能就不会提，粘个OI Wiki的链接就不详细写了。 接下来就按照这个目录挨个讲一下每个算法。 最大流 如果有哪里没有说清楚，可以看这里，里面还有我没有说到的最大流类型。 看到最大流这个名字很多人都很陌生，这里就先从定义说起。 定义 还是拆词法，“网络流”就可以大致理解为“网络”上的“流”，接下来就挨个说一下这两个的定义。 网络 先说网络的定义。（当然不是Internet） 我们在理解的时候可以认为是管道，但实际上它是一张特殊的有向图。 建设管道的必然知道，管道内流过的水，准确来说是单位时间内流过的水，必然是有上限限制的，否则管道就炸了。 这里也一样，对于每条边 $x \to y$，都有一个函数 $c(x,y)$ 表示这条边的限制，又称容量。 如果在图上没有这条边，则统一规定 $c(x,y)=0$。 最后，还是跟最短路一样，它有一个起点和一个终点，又称源点 $S$ 和汇点 $T$（$S \not= T$）。 流函数 再说流函数。 流函数就是说，在真实操作中，一个单位时间内一条边 $x \to y$ 流过的水量 $f(x,y)$。 这里默认保证每个单位时间内都得流过这么多。 其实很好理解。 流函数性质 顺便说一下流函数要满足的性质。 首先，源点可以无限输出水，汇点可以无限输入水。 接下来就是一堆性质： 对于每个 $x,y$，显然 $f(x,y) \leq c(x,y)$（容量限制）。 对于每个 $x,y$，$f(x,y)=-f(y,x)$（斜对称）。 对于每个 $x$，满足不是源点也不是汇点，$\sum\limits_{u \to x} f(u,x)=\sum\limits_{x \to v} f(x,v)$（流量守恒）。 这里说一下最后一点性质。 ...

（说是斜率优化，其实和斜率几乎没有关系） （e…更新后确实有关系） 其实斜率优化和决策二分栈（队列）很像，下面分几种类型来讲。 一维斜率优化 针对形如 $d_i=\min\limits_{j=0}^{i-1} \big( d_j+w(j+1,i) \big)$ 的方程，而且需要满足决策单调性。 此处重新说一下，如果我们发现一个转移点 $x$ 在 $d_i$ 的时候已经比另外一个转移点 $y$ 要更优了（$x>y$），那么转移点 $y$ 在后面（$d_{i+1}$ 及以后）就不可能比转移点 $x$ 要更优了，那么这个DP一定满足决策单调性，而且反过来也一样（见"决策单调性.md"）。 其实证明是否满足单调性只用看：如果一个决策点 $x$ 如果在 $d_i$ 的转移中已经比决策点 $y$ 要优了，那么 $d_{i+1}$ 中是否仍然满足这个条件。 证明了满足决策单调性后，就可以开始斜率优化了。 我们首先要考虑推斜率式： 其实斜率式就是把式子 $d_x+w(x+1,i)<d_y+w(y+1,i)$（$x>y$）不断移项、变化，直到式子左边只和 $x$、$y$ 有关，右边只和 $i$ 有关为止。 此时的斜率式一般左边是个分数，而且这个分数还需要把分子和分母的下标对应： 如果斜率式最后是像这样的： $\dfrac{d_x-d_y}{v_y-v_x}>-a_i$ 那么就不是个合法的斜率式，需要变成： $\dfrac{d_x-d_y}{v_x-v_y}<a_i$ 才是合法的。 注意，这里说的是“合法的”，而不是“正确的”，其实最上方的斜率式也可以使用，就是不能叫“斜率式”了（斜率的公式是 $\dfrac{y_2-y_1}{x_2-x_1}$）。 设此时的斜率式就是上面说的： $\dfrac{d_x-d_y}{v_x-v_y}<a_i$ 那么，我们就定义 $\text{slope}(y,x)=\dfrac{d_x-d_y}{v_x-v_y}$。 有了上面函数，显然如果存在两个转移点 $x$ 和 $y$（$x>y$）在转移到 $d_i$ 的时候满足 $\text{slope}(x,y)<a_i$，那么就说明转移点 $x$ 比转移点 $y$ 更优，转移点 $y$ 在后面就不需要了。 下面默认推出来的斜率式就是上式，并默认 $a$ 数组单调不降。 ...

要说行列式，就得先说一下矩阵（其实是方阵）的秩的定义。 对于一个方阵，其秩的定义就是矩阵里线性无关的极大值。 听这个定义有点难懂，这里解释一下。 其实一个方阵就可以被当做是一个没有右项的方程集。 而一个方阵的秩就可以当做是，这个没有右项的方程集在经过高斯消元后，非 $0$ 行的数量。 有了这个定义，矩阵的秩还可以被当做是，这个没有右项的方程集中，不会被其他方程替代掉的方程数量： 解释一下，如果方程长这样： $ \begin{cases} -x_1+2x_2+5x_3=11 \ 2x_1=8 \ x_1+2x_2+5x_3=19 \end{cases} $ 那么，其实第三个方程式可以通过前两个方程式推出来，也就称作第三个方程式可以被前两个方程式替代掉。 知道了“替代”的定义后，就知道了一件事，就是上面说的“会被其他方程替代掉的方程”，这些方程可以直接从方程组里去掉，而不影响最终的解。 所以，我们就可以对奥数里的一个点做一个更简洁的解释： 在奥数里，讲了解 $n$ 元一次方程（组）的方法。 同时还说了，在这个 $n$ 元一次方程组内，如果“有用”的方程数量，刚好等于未知数的数量，或者大于未知数的数量，那么这个方程组就有唯一解。 这一点可以被更简洁地解释为： 这个 $n$ 元一次方程组，转化为“高斯矩阵”，并删除最后一列后（变成 $n \times n$ 的方阵），如果这个方阵的秩刚好为 $n$，那么这个方程组就有唯一解。 然后，我们回归正题，说行列式。 行列式是对于一个方阵来讲的，一个方阵有行列式有且仅当这个方程的秩刚好等于方阵的大小（行或者列）。 行列式的定义此处不讲，因为： 太复杂了 （几乎）没有用处 行列式的计算方法是用的高斯消元。 在高斯消元的思路里，提到了三种“基本行变换”：（以下全部以高斯矩阵的角度去说） 将一行全部乘上一个非 $0$ 实数 $x$，解不变。 将一行内的所有元素对应地加上/减去另一行对应的元素乘上一个非 $0$ 实数 $x$，解不变。 交换两行，解不变。 这三种基本行变换在执行前后，行列式并不是都不变的： 将一行全部乘上一个非 $0$ 实数 $x$，行列式也会乘上 $x$。 将一行内的所有元素对应地加上/减去另一行对应的元素乘上一个非 $0$ 实数 $x$，行列式不变。 交换两行，行列式变号（负数变成正数，反之亦然）。 所以我们只用写一下高斯消元，然后处理一下对行列式的值的变化即可。 但这儿还有一点问题，就是行列式怎么求。 求法很好记，如果说当前方阵是个上三角矩阵（设方阵叫 $a$，那么 $a$ 是个上三角矩阵有且仅当对于所有的 $(i,j)$，如果满足 $i>j$，那么 $a_{i,j}$ 一定要等于 $0$，当然其他方格不做要求），那么这个方阵的行列式就是这个方阵中正对角线上的元素的乘积。 ...

说一个非常重要的语法错误。 如果你写这样一句话： v[x] = newnode(); 其中： v为一个vector。 x为不越界的非负整数，且不会变化。 newnode()函数内会向vector内push_back一个新元素，并返回加入元素（即最后一个元素）的下标。 那么，你会发现，v[x]的值并不是这样变化的： 1,2,3,4,5,6,7,... 而是类似于这样的：（非真实输出结果，仅供参考） 1,1,2,2,3,4,4,5,6,7,8,8,9,10,11,12,13,14,15,16,16,17,18,19,20,... 你会发现部分情况下，v[x]没有变化！ 这实际上是因为vector的内部机制。 vector会有一个capacity，就是提供的内存大小。 每次push_back的时候，如果说加入后，不超过当前的capacity，就会直接加入。 否则，vector会新开辟一块等于当前capacity的两倍（这个在不同编辑器上是不一样的，有些可能是每次新增 $5$ 个）的新空间，并把原本的数据拷进这块新空间内。 比如说现在的vector是： 内存354~357位置：3 1 2 4 且capacity是 $4$，那么我们如果尝试push_back一个 $5$，则vector就会发现大于了capacity，便会新开一块等于当前capacity的两倍的空间： 内存354~357位置：3 1 2 4 内存382~389位置： 并把当前数据拷进去： 内存354~357位置：3 1 2 4 内存382~389位置：3 1 2 4 然后在新空间内加入 $5$： 内存354~357位置：3 1 2 4 内存382~389位置：3 1 2 4 5 并把所有v[x]指向的内存都改成382~389这块新内存内对应的地方。 不过由于C++的赋值机制，系统会先找到要赋值给的变量的指针，然后求出要赋的值，赋给以前找到的指针。（这一步是推测，可能不准确） 所以就会导致把newnode()的值赋给了原本的v[x]，导致输出的时候访问的新v[x]值出错。 解决方法也很简单，把newnode()用个临时变量t存储，并将v[x]赋值为t即可。

在数学、编程界里，可能会经常遇到方程，而且有时候还会遇到一种特殊方程——一元二次方程。 除此之外，还有含参一元二次方程，这里也会一起讲。（待补充） 其实还有如二元一次方程、一元三次方程等的特殊方程，但在这里不讲。 一元二次方程 有人看到“一元二次方程”就不知道是啥意思，这里先说一下定义 定义 首先，方程相信大家都见过，所以这里不写对方程的定义解释。（废话 而 $x$ 元 $y$ 次方程就是这么定义的： 这个方程经过化简后，共有 $x$ 个未知数，且未知数上的最大指数为 $y$ 的方程。 如： $3(x+1)=6x$：一元一次方程，也是最常见的方程。 $3(x+1)^2=2(x+1)$：一元一次方程，因为两边可以同时除以 $x+1$ 以让指数减少 $1$。 $x^2-4x+1=0$：一元二次方程，也是下面要讲的方程类型。 $x^3+2x^2-1=16x$：一元三次方程，也是一种不常见的方程类型。 讲完定义，接下来说怎么解 解法 推导 我们把方程一般化，变成： $ax^2+bx+c=0$ 其中 $a$、$b$、$c$ 均为常量。 然后，我们不断对方程做一些推导。 移项 $ax^2+bx=-c$ 同时除以 $a$ 常量 $x^2+\dfrac{b}{a}x=-\dfrac{c}{a}$ 这个式子很多人看了就不知道怎么继续推导了。 但还是可以继续转化的。 我们考虑配方，即把式子的左/右项同时加/减/乘/除一个相同的数，然后让这个等式的左/右项变成一个数的平方的形式。 这一步比较考验数感，一个结论就是，我们同时加上 $\left( \dfrac{b}{2a} \right)^2$ 常量 即可。 $x^2+\dfrac{b}{a}x+\left( \dfrac{b}{2a} \right)^2=-\dfrac{c}{a}+\left( \dfrac{b}{2a} \right)^2$ 化简 $\left( x+\dfrac{b}{2a} \right)^2=\dfrac{-c}{a}+\dfrac{b^2}{4a^2}$ 二次化简 $\left( x+\dfrac{b}{2a} \right)^2=\dfrac{b^2-4ac}{4a^2}$ 同时开根号 $x+\dfrac{b}{2a}=\sqrt{\dfrac{b^2-4ac}{4a^2}}$ ...

感谢这篇文章的作者 整除分块主要解决求解 $\sum\limits_{i=1}^n \lfloor \frac{n}{i} \rfloor$ 的值。 一看这个公式，可能毫无头绪，但画张图你就有点思路了：（$n=11$） （灰色线：$y=\frac{11}{x}$，绿色点：$y=\lfloor \frac{11}{x} \rfloor$，橙色线：仅为辅助） 这张图其实就是在提示我们： $\lfloor \frac{n}{i} \rfloor$ 的值随着 $i$ 的增长而非单调递减 $\lfloor \frac{n}{i} \rfloor$ 的值往往会在一段区间内相等 所以，我们就有一个思路了，就是求出所有值（下面的“值”都代指的是 $\lfloor \frac{n}{i} \rfloor$）相等的极大区间集，然后就可以快速统计了。 有人问，这不就是个常数级别的优化吗，怎么能叫“快速”呢？其实区间个数总是 $O(\sqrt{n})$ 级别，最多约 $2 \times \sqrt{n}$。 证明： 我们把 $i$ 分成两部分去考虑，一部分是 $i \leq \sqrt{n}$，另一部分是 $i>\sqrt{n}$。 在第一部分内，$i$ 也就只有 $\sqrt{n}$ 种取值，$\lfloor \frac{n}{i} \rfloor$ 最多只有约 $\sqrt{n}$ 种取值。 在第二部分内，$\lfloor \frac{n}{i} \rfloor$ 在 $i$ 最小时（$i=\sqrt{n}+1$）会达到最大值，约 $\sqrt{n}$；而上面说“$\lfloor \frac{n}{i} \rfloor$ 的值随着 $i$ 的增长而非单调递减”，所以易得 $\lfloor \frac{n}{i} \rfloor$ 最多也只有约 $\sqrt{n}$ 种取值。 $\lfloor \frac{n}{i} \rfloor$ 的总取值种数最多只有第一、二部分的取值个数和，即 $2 \times \sqrt{n}$，证毕。 ...

整体二分类似于线段树上二分，在讲这个算法前，先引入几个问题。 解决题型 整体二分一般解决的是如下的问题： 给你一个【集合/序列/矩阵/树】，要求【静态/动态】维护所有【元素/区间/子矩阵/链/子树】中的第 $k$【可能每次给定】大元素，【可能强制在线】。 下面是一堆例题。 例题1 动态查询集合第k大（可离线） 题意 让你维护一个初始为空的多重集合 $s$，并支持 $q$ 次操作，操作都是下面三种之一： 添加一个数 $x$ 到集合 $s$ 中。 在集合 $s$ 中删除一个数 $x$（保证元素存在）。 查询集合第 $k$ 大（保证第 $k$ 大存在）。 数据范围 $1 \leq q \leq 2 \times 10^5$ $0 \leq x \leq 10^9$ 题解 维护一个权值线段树（权值线段树其实就是一个维护值域的线段树），维护一段值域里有多少个数，每次询问在线段树上二分即可。 具体地，对于线段树上某个节点对应的区间 $[l,r]$，这个节点上的值为集合中，值在 $[l,r]$ 的数的个数有多少。 在询问时，我们要记录当前节点编号 $x$，$x$ 维护区间 $[l,r]$，以及要查询值在 $[l,r]$ 内的所有数的第 $k$ 大。 当递归到某个状态后，我们看这个节点的左子树 $\text{lc}$ 内有多少个值，如果大于等于 $k$，则递归到左子树；否则递归到右子树，且 $k$ 减去(左子树内数的个数)。 由于值域较大，权值线段树可能会爆，所以要先把所有询问离线下来，做个离散化，然后就可以把 $x$ 控制到 $q$ 级别，就不会爆了。 ...

中国剩余定理，Chinese Remainder Theorem，又称CRT，我们接下来就讲一下这个算法的原理。 要说原理，就得从古代说起。 （你到底是在讲编程课还是在讲历史课） （真的是在将编程课） 在古代，有一个问题，叫做“物不知数问题”，原文是这样的： 有物不知其数 三三数之剩二 五五数之剩三 七七数之剩二 问物几何？ 这个问题翻译过来就是问以下方程的所有正整数解： $ \begin{cases} x \equiv 2 \pmod{3} \ x \equiv 3 \pmod{5} \ x \equiv 2 \pmod{7} \end{cases} $ 这个问题在后来有一个解了，解出来这个问题的人，编了一首诗，叫做“孙子歌诀”，原文： 三人同行七十稀 五树梅花廿一支 七子团圆正半月 除百零五便得知 这个解翻译过来就是说，若设 $r_3$ 为方程中 $x$ 模 $3$ 的余数，$r_5$、$r_7$ 同理，那么所有解 $x$ 一定满足： $x \equiv r_3 \times 70+r_5 \times 21+r_7 \times 15 \pmod{105}$ 其中 $105$ 的实际来源是上面三个方程的模数的 $\text{lcm}$，即 $\text{lcm}(3,5,7)=3 \times 5 \times 7=105$。 关于 $70$、$21$、$15$ 的来源下面再说，我们先证明一下这个解是正确的。 由于 $105$ 是三个模数的 $\text{lcm}$，所以说如果 $x$ 是满足条件的，$x-105$、$x+105$ 都是满足条件的（此处暂时忽略“正整数解”的限制），显然。 ...