各算法做法总汇

JackMerryYoung · 2020-12-05 11:32:50 · 个人记录

ST 表

ST 表可以处理可重复贡献问题。

先来看一个例子: RMQ (区间最值问题).

设 f(i,j) 是区间 [i,i + 2^j] 内最值，则：

证明：

根据题意，f(i,j) 是区间 [i,i + 2^{j}] 内最值。

RMQ 问题为可重复贡献问题，也就是满足 x \operatorname{opr} x = x.

则可以把区间 [i,j] 分成两个区间：[i,i + 2^{j - 1}] 和 [i + 2^{j - 1},i + 2^{j}] ，并求二者分别的最值，然后求两者分别所得的最值的最值。

即 f(i,j) = \max\{f(i,j - 1),f(i + 2^{j - 1},j - 1\}。

特殊的，当 j = 0 时，f(i,j) = a[i]。

设 query(l, r) 是区间 [l,r] 内最值，则：

这就能查询 \mathcal{O}(1) 啦。

线段树

待填坑。

树状数组

待填坑。

单调栈

跟单调队列功能一毛一样。

#include <bits/stdc++.h>
using namespace std;
int STACK[3000005];
int a[3000005];
int f[3000005];
int n;
int top;
int main()
{
    cin >> n;
    for(int i = 1;i <= n;i ++)
    {
        cin >> a[i];
    }
    for(int i = 1;i <= n;i ++)
    {
        if(a[i] <= a[STACK[top]] || top == 0)//杀不动或没人杀
        {
            top ++;
            STACK[top] = i;//入栈 
        } 
        else
        {
            while(a[i] > a[STACK[top]] && top != 0)//杀得动且有人杀
            {
                f[STACK[top]] = i; 
                top --;//出栈 
            } 
        } 
        top ++;
        STACK[top] = i;//入栈 
    }
    for(int i = 1;i <= n;i ++)
    {
        cout << f[i] << ' ';
    } 
    return 0;
}

LCS

设 f(i,j) 为序列 A 考虑到第 i 个人时，序列 B 考虑到第 j 个人时所得的最长公共子序列长度，则：

特殊的，当 A_i = B_i 时，则：

逆元

注： p 一定为质数。

欧拉函数

设 \varphi(n) 为 n 的互质数数目，则：

费马小定理

FFT

也称狒狒贴，全名 Fast Fast TLE.

官方名称：快速傅里叶变换。是一个用于求多项式卷积的 \mathcal{O}(N \log_2 N) 算法。

该部分的 N, x 大多为 2^k (k \in N^+), 所以高位要记得补 0.

多项式

顾名思义就是一堆单项式的和。

多项式可以表示成两种形式：

系数表示法：

点值表示法：

就是取 N + 1 个值代入算出来，表示成点。可以通过一个 N + 1 的点集确定一个 N 次多项式。

卷积

符号: *.

输出 等于 输入 与 系统 的卷积，即：\text{Output} = \text{Input} * \text{System}.

多项式的卷积：函数 F(x) 与 G(x) 的乘积。

复数相关

虚数单位 i = \sqrt{-1}. 即 i^2 = -1.

虚数：形如 ai 的数。

复数：形如 ai + b 的数。其中 a 被称为虚部, b 被称为实部。

复数的共轭：虚部相同，实部互为相反数的复数互为共轭。复数 x 的共轭表示为 \bar{x}.

复数运算：

加减乘都跟实数差不多。

除法就是分数线上下同乘上分母的共轭。

复数的表示：向量, ai + b 表示 (0, 0) 到 (a, b) 的一个向量。

模长: \sqrt{a^2 + b^2}, 向量的长度。

其他奇怪的东西

单位圆

以原点为圆心, 1 为半径的圆。

单位根

若 \omega^n_n = 1, 则称 \omega_n 为 n 次单位根。

有 n 个 n 次单位根，在复平面上表示的话恰好能等分单位圆。

逆时针标号单位根，令 \omega_n^k 为第 k 个 n 次单位根。

有三个性质：

1. 消去引理: \omega_{dn}^{dk} = \omega_{n}^{k}.

显然。

2. 折半引理：若 n 为偶数，则 \omega_n^{k + \frac{n}{2}} = -\omega_n^k.

需要欧拉公式：

对欧拉公式进行乱搞可知：

综合：

几何证明：既然是绕了半圈，必然与原数互为相反数。

3. 求和引理：若 n \nmid k (n, k \in N^+), 则有 \sum_{j = 0}^{n - 1}{(\omega_n^k)^j} = 0.

用等比数列求和即可得知。

狒狒贴有什么用

我们知道暴力乘的效率奇低，需要 \mathcal{O}(N^2).

但是我们又观察到若有 F(x) 上的点 (x, y_1), G(x) 上的点 (x, y_2), 则有 F * G 上的点 (x, y_1 \cdot y_2). 这很显然。

那么既然点值表示可以确定多项式，那么就可以将已知的点每个 y 都相乘得到新的点，再反推回去。

这说明了我们可以用 \mathcal{O}(N) 的时间求解给出了点值表示的多项式卷积。

可是代入不要时间吗？这样复杂度又成了 \mathcal{O}(N^2).

没事。不要灰心，狒狒贴能解决！

狒狒贴的原理

就两个字：分治。

第一步是 DFT, 即离散傅里叶变换。

就是由于单位根的折半引理的前提，所以我们考虑对每一项的系数分类讨论：

那么对于 F(x) = \sum_{i = 0}^{N - 1}{a_i x^i}, 令：

则显然：

代入单位根 \omega, 只用考虑 k < \frac{n}{2} 的，毕竟另一半就是重复的问题。

先代入 \omega_n^k, 根据消去引理得：

这样就可以将两个子问题的 n 砍去一半，这样复杂度就可能下降啦。

不过还要考虑另一边呢。代入 \omega_n^{k + \frac{n}{2}}, 得：

可以发现分治后只需求两个子问题，而且每一个子问题的规模缩小了一半。典型的 \mathcal{O}(N \log_2 N) 算法。

突然发现做完 DFT 还需要再变回去，那就有了 IDFT, 即离散傅里叶逆变换 这玩意简直跟 DFT 一毛一样。

IDFT 相当于将 DFT 的结果变成系数表示. DFT 可以被描述为：

已知最左边和中间的那个矩阵，要还原成最右边的矩阵，那么就考虑让 DFT 的结果乘上中间矩阵的逆矩阵。

然鹅这个逆矩阵又不好求，咋办？

先摆结论：逆矩阵就是每一项取倒数再除以 N. 为啥呢？

证明：

倒推嘛。设：

暴力展开计算：

令 S(x) = \sum_{i = 0}^{n - 1}{x^i}.

将 \omega_n^k 代入得：

乘上个 \omega_n^k 可得：

相减可得：

当 k \ne 0 时，该柿子有意义，因为 \omega_0^k = 1. 又易知 (\omega_n^n)^k = 1, 所以可知 S(\omega_n^k) = 0.

当 k = 0 时，显然 S(\omega_n^k) = n.

那就拿这个结论去考虑上面的柿子。发现当 j \ne k 时全都是 0, 除了一次 j = k 结果为 n. 所以直接可以进行大化简了：

即 a_k = \frac{c_k}{n}. 这样我们就做完啦。

狒狒贴的强劲优化

你把你刚写好的 FFT 交上洛谷，期待着 AC 的时候，突然一个橙黄的 77 分映入眼帘！

唉果然递归效率太低了，开了一大堆空间。那么就考虑优化啦。

蝴蝶操作

待填坑...

图论

最短路

Dijkstra

一个单源最短路算法。

设源点为 s，从点 i 到点 j 的图上距离为 w_{i,j}，源点到点 i 的距离 为 dis_i。

易得：

算法步骤如下:

1. 找到 dis_i 最小的点 i

2. 以 i 为中转点更新与它连接的点 j 的 dis_j。

3. 重复第 1 步，直到每个点都被作为中转点过为止。

参考博文

理由：

设当前中转点为 k，i 是 k 所可达的未被作为中转点过的点，则有：

理由显然，k 取的一定是未被作为中转点过的点中，dis_k 最小的一个。

最小生成树

树的定义：对于无向图 T，若 T 中每一个点都可以互达，且 T 只有 n - 1 条边（n 为 T 中的节点数目），那么 T 就是一棵树。

生成树的定义：对于无向图 G，若 G' 是 G 的子图，而且是一棵树，则称 G' 是 G 的一棵生成树。

其中，生成树的边权之和被称为生成树的大小。

最小生成树的定义：对于图 G，在它的生成树集中，大小最小的生成树 G'_{min} 即为 G 的最小生成树。

那么，根据定义可得，对于任意的 G'_k，都有：

接下来，我们来了解一些算法。

Kruskal

一个使用了并查集的算法。

将图中的每一条边按权值排序，按顺序尝试加入，分两种情况讨论：

1. 该边所联通的两个节点已经可以互达，选择不加入。

2. 否则加入这条边。

代码：

#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int start;
    int to;
    long long w;
}arr[200001];

int n,m;
long long MST;
long long s[50001];

bool cmp(Edge a,Edge b) {
    return a.w < b.w;
}

long long _find(int a) {

    if (s[a] == a) return a;
    else {
        return s[a] = _find(s[a]);
    }
}

void kruskal() {
    int add = 0;
    int u,v;
    for(int i = 1; i <= m; i ++) {
        u = _find(arr[i].start);
        v = _find(arr[i].to);
        if(u != v) {
            MST += arr[i].w;
            s[u] = v;
            add ++;
            if(add == m - 1) {
                break;
            }
        }
    }
}

int main() {
    cin >> n >> m;
    for(int i = 1;i <= n;i ++){
        s[i] = i;
    }
    for(int i = 1; i <= m; i ++) {
        cin >> arr[i].start >> arr[i].to >> arr[i].w;
    }
    sort(arr + 1,arr + m + 1,cmp);
    kruskal();
    cout << MST;
    return 0;
}

理由：

设当前的边为 e_i，权值为 w_i，那么升序排序后可以保证对于任意的 i，都有：

那么，我们可以顺序取边。

设 e_i 连接 u，v 两点，那么如果 u，v 已经同属一个并查集，即 u，v 两点被联通了，那么对于构造树是无意义的，并且使树的大小变大了，不符合我们对于最小生成树的定义，所以不能取 e_i 这条边。