算法模板

算法模板

算法

发布日期: 2021-11-17

文章字数: 6.9k

阅读时长: 37 分

数据范围：

一般ACM或者笔试题的时间限制是1秒或2秒。

在这种情况下，C++代码中的操作次数控制在 $10^7 \sim 10^8$ 为最佳。

下面给出在不同数据范围下，代码的时间复杂度和算法该如何选择：

$n \le 30$, 指数级别, dfs+剪枝，状态压缩dp
$n \le 100$ => $O(n^3)$，floyd，dp，高斯消元
$n \le 1000$ => $O(n^2)$，$O(n^2logn)$，dp，二分，朴素版Dijkstra、朴素版Prim、Bellman-Ford
$n \le 10000$ => $O(n * \sqrt n)$，块状链表、分块、莫队
$n \le 100000$ => $O(nlogn)$ => 各种sort，线段树、树状数组、set/map、heap、拓扑排5序、dijkstra+heap、prim+heap、spfa、求凸包、求半平面交、二分、CDQ分治、整体二分
$n \le 1000000$ => $O(n)$, 以及常数较小的 $O(nlogn)$ 算法 => 单调队列、 hash、双指针扫描、并查集，kmp、AC自动机，常数比较小的 $O(nlogn)$ 的做法：sort、树状数组、heap、dijkstra、spfa
$n \le 10000000$ => $O(n)$，双指针扫描、kmp、AC自动机、线性筛素数
$n \le 10^9$ => $O(\sqrt n)$，判断质数
$n \le 10^{18}$ => $O(logn)$，最大公约数，快速幂
$n \le 10^{1000}$ => $O((logn)^2)$，高精度加减乘除
$n \le 10^{100000}$ => $O(logk \times loglogk)，k表示位数$，高精度加减、FFT/NTT

基础算法

快速排序

void quick_sort(int q[], int l, int r)
{
    if(l >= r) return;

    int i = l - 1, j = r + 1, x = q[l + r >> 1]; 

    while(i < j)
    {
        do i++; while (q[i] < x);
        do j--; while (q[j] > x);
        if(i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

归并排序

void merge_sort(int q[], int l, int r)
{
    if(l >= r) return;
    int mid = l + r >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while(i <= mid && j <= r)
    {
        if(q[i] <= q[j]) tmp[k++] = q[i++];
        else tmp[k++] = q[j++];
    }

    while(i <= mid) tmp[k++] = q[i++];
    while(j <= r) tmp[k++] = q[j++];

    for(i = l, j = 0; i <= r; i++, j++)
        q[i] = tmp[j];
}

二分

使用前提：一个题目,如果一个区间具有单调性质,那么一定可以二分,但是如果说这道题目没有单调性质,而是具有某种区间性质的话,我们同样可以使用二分.

找到>=x的第一个数

int l = 0, r = n - 1;
while (l < r)
{
    int mid = l + r >> 1; //注意mid = l+r 还是l+r+1 !!!
    if (a[mid] >= x) r = mid;
    else l = mid + 1;
}

找到<x的

int l = 0, r = n - 1;
while (l < r)
{
    int mid = l + r + 1 >> 1;
    if (a[mid] <= x) l = mid;
    else r = mid - 1;
}

浮点数二分

浮点数二分不用考虑边界问题;
但是mid只能写成mid = (l + r) / 2，而mid = l + r >> 1会报错

/* 数的三次方根 */
double epi = 1e-7;
double mid;
while(r - l > epi)
{
    mid = (l + r) / 2;
    if(mid * mid * mid > n)
        r = mid;
    else 
        l = mid;
}

使用STL库函数

lower_bound( begin,end,num)：查找第一个大于或等于num的数字，通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

upper_bound( begin,end,num)：查找第一个大于num的数字，通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

高精度

高精度加法

#include<iostream>
#include<vector>

using namespace std;

vector<int> add(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    if(A.size() < B.size()) return add(B, A);

    int t = 0;//进位
    for(int i = 0; i < A.size(); i++)
    {
        t += A[i];
        if(i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }

    //如果最后一位产生进位
    if(t) C.push_back(1);
    return C;
}

int main()
{
    string a, b;
    vector<int> A, B;
    cin >> a >> b;

    //低位在前，高位在后
    for(int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
    for(int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');

    auto C = add(A, B);
    for(int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);

    return 0;
}

高精度减法

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

bool cmp(vector<int> &A, vector<int> &B)
{
    if(A.size() != B.size())  return A.size() > B.size();
    for(int i = A.size() - 1; i >= 0; i--)
        if(A[i] != B[i])
            return A[i] > B[i];
    return true;
}

//C = A - B
vector<int> sub(vector<int> &A, vector<int> &B)
{
    vector<int> C;

    int t = 0;//借位
    for(int i = 0; i < A.size(); i++)
    {
        t = A[i] - t;
        if(i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);
        if(t < 0) t = 1;
        else t = 0;
    }

    //去掉前导0
    while(C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

int main()
{
    string a, b;
    vector<int> A, B;

    cin >> a >> b;
    for(int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
    for(int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');

    if(cmp(A, B))   
    {
        auto C = sub(A, B);
        for(int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
    }
    else    
    {
        auto C = sub(B, A);
        printf("-");
        for(int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
    }
    return 0;

}

高精度乘法

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

vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;

    int t = 0;
    for(int i = 0; i < A.size() || t; i++)
    {
        if(i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }

    while(C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

int main()
{
    string a;
    int b;
    vector<int> A;
    cin >> a >> b;

    for(int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');

    auto C = mul(A, b);
    for(int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
    return 0;
}

高精度除法

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

vector<int> div(vector<int> &A, int b, int &r)
{
    vector<int> C;
    r = 0;
    for(int i = A.size() - 1; i >= 0; i--)
    {
        r = r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }

    reverse(C.begin(), C.end());
    while(C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

int main()
{
    string a;
    int b;
    int r;
    vector<int> A;
    cin >> a >> b;

    for(int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
    auto C = div(A, b, r);
    for(int i = C.size() - 1; i >=0; i--) printf("%d", C[i]);

    cout << endl << r << endl;
    return 0;
}

前缀和与差分

一维前缀和与差分

//求前缀和
s[i] = s[i - 1] + a[i];
//求[l,r]的区间和
s[m] = s[r] - s[l - 1];

//构造差分数组
b[i] = s[i] - s[i - 1];
//[l,r]每个数加c
b[l] += c;
b[r + 1] -= c;
//还原成原数组
b[i] = b[i - 1] + b[i];

二维前缀和与差分

//求前缀和
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j]
//求[x1,y1]与[x2,y2]之间的和
S = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];

//构造差分数组
a[i][j] = s[i][j] - s[i - 1][j] - s[i][j - 1] + s[i - 1][j - 1];
//选中的子矩阵中的每个元素的值加上c
a[x1][y1] += c;
a[x2 + 1][y1] -= c;
a[x1][y2 + 1] -= c;
a[x2 + 1][y2 + 1] += c;
//还原成原数组
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];

双指针算法

//求出满足 A[i]+B[j]=x 的数对 (i,j)
for(int i = 0, j = m - 1; i < n; i++)
{
    while(j >= 0 && a[i] + b[j] > x)    j--;
    if(a[i] + b[j] == x)    
    {
        cout << i << ' ' << j << endl;
        break;
    }
}

位运算

int lowbit(int x) // 每次截取一个数字最后一个1后面的所有位
{
    return x & -x;
}

离散化

主要分为5大步：

读输入。将每次读入的x,c push_back()到add中，将每次读入的位置x push_back()到alls中，将每次读入的l r push_back()到query中。
排序、去重。
通过遍历add，完成在离散化的数组映射到的a数组中进行加上c的操作（用到find函数）。
初始化s数组。
通过遍历query，完成求区间[l,r]的和。

将所有要用到的下标存放在alls数组里面
排序好了之后，查找出某一位置x在alls里面对应的下标，并返回下标加一（便于前缀和）
然后a[x] += c，再进行前缀和操作
最后遍历query，利用find函数找出左右下标，然后利用s[r] - s[l - 1]进行输出！

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

typedef pair<int, int> PII;

const int N = 300010;
int n, m;
int a[N], s[N];

vector<int> alls;
vector<PII> add, query;

int find(int x)
{
    int l = 0, r = alls.size() - 1;

    while(l < r)
    {
        int mid = l + r >> 1;
        if(alls[mid] >= x) r = mid;
        else l = mid + 1;
    }

    return r + 1;
}

int main()
{
    cin >> n >> m;

    while(n--)
    {
        int x, c;
        cin >> x >> c;
        add.push_back({x, c});

        //将所有要用到的下标存放在alls数组里面
        alls.push_back(x);
    }
    while(m--)
    {
        int l, r;
        cin >> l >> r;
        query.push_back({l, r});

        alls.push_back(l);
        alls.push_back(r);
    }

    //对所有下标进行排序
    sort(alls.begin(), alls.end());

    //进行去重
    alls.erase(unique(alls.begin(), alls.end()), alls.end());

    for(auto item : add)
    {
        //寻找下标
        int x = find(item.first);    
        a[x] += item.second;
    }

    //处理前缀和
    for(int i = 1; i <= alls.size(); i++) s[i] = s[i - 1] + a[i];

    for(auto item : query)
    {
        int l = find(item.first), r = find(item.second);
        cout << s[r] - s[l - 1] << endl;
    }

    return 0;
}

区间合并

对左端点进行排序！！

vector<PII> segs;
void merge(vector<PII> &segs)
{
    vector<PII> res;

    //按左端点排序
    sort(segs.begin(), segs.end());

    int st = segs[0].first, ed = segs[0].second;

    for(int i = 0; i < segs.size(); i++)
    {
        //无法合并则将之前的区间放入答案中
        if (ed < segs[i].first) 
        {
            res.push_back({st, ed});

            //将下一个区间的端点重置
            st = segs[i].first;
            ed = segs[i].second;
        }

        //能合并的情况
        else ed = max(ed, segs[i].second);

        //将最后一个区间放入答案中
        if( i == segs.size() - 1) res.push_back({st, ed});
    }

    segs = res;
}

数据结构

单调栈

//题意：给定一个长度为 N 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 −1
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n;
int stk[N], tt;

int main()
{
    scanf("%d", &n);

    int x;
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &x);
        while(tt && stk[tt] >= x) tt--;
        if(tt) printf("%d ", stk[tt]);
        else printf("-1 ");

        stk[++ tt] = x;
    }
    return 0;
}

单调队列

//滑动窗口：确定滑动窗口位于每个位置时，窗口中的最小值
#include<bits/stdc++.h>
using namespace std;

const int N = 1000010;
int n, k;

//a[N]存的是所有值，q[N]存的是有单调性的数的下标
int a[N], q[N];

int main()
{
    scanf("%d%d", &n, &k);

    int hh = 0, tt = -1;
    for(int i = 0; i < n; i++) 
    {
        scanf("%d", &a[i]);
        //队首滑出窗口
        if(i - k + 1 > q[hh]) hh++;
        //使队尾具有单调性
        while(hh <= tt && a[i] <= a[q[tt]]) tt--;
        q[++tt] = i;
        if(i >= k - 1) printf("%d ", a[q[hh]]);
    }
    return 0;
}

KMP算法

/*
给定一个模式串 S，以及一个模板串 P，所有字符串中只包含大小写英文字母以及阿拉伯数字。
模板串 P 在模式串 S 中多次作为子串出现。
求出模板串 P 在模式串 S 中所有出现的位置的起始下标。
*/
#include<bits/stdc++.h>
using namespace std;

const int N = 100010, M = 1000010;

int n, m;
char p[N], s[M];
int ne[N];

int main()
{
    cin >> n >> p + 1 >> m >> s + 1;

    //求next数组
    for(int i = 2, j = 0; i <= n; i++)
    {
        while(j && p[i] != p[j + 1]) j = ne[j];
        if(p[i] == p[j + 1]) j++;
        ne[i] = j;
    }

    //匹配
    for(int i = 1, j = 0; i <= m; i++)
    {
        while(j && s[i] != p[j + 1]) j = ne[j];
        if(s[i] == p[j + 1]) j++;

        //匹配成功
        if(j == n)
        {
            cout << i - n << ' ';
            j = ne[j];
        }
    }

    return 0;
}

并查集

int find(int x)  //并查集
{
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}

int find(int x)//带权并查集 
{
    if(p[x] != x){
        int t = find(p[x]);
        d[x] += d[p[x]];
        p[x] = t;
    }
    return p[x];
}

树状数组

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

typedef long long LL;

const int N = 1000010;
int n, q;
LL tr[N];

int lowbit(int x)
{
    return x & -x;
}

//1、单点加，区间求和     单点修改：O(logn) 区间查询：O(logn)
//2、用差分可以变化为区间加，求单点值 
//3、区间加（差分），区间求和维（护两个前缀和(bi和i*bi）公式为：(a1+..+ax)=(x+1) * (b1+...+bx)-(1*b1+2*b2+..x*bx)
void add(int x, int c)
{
    for(int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}

LL sum(int x)
{
    LL res = 0;
    for(int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

int main()
{
    cin >> n >> q;
    for(int i = 1; i <= n; i++){
        int x;
        cin >> x;
        add(i, x);
    } 
    while (q -- ){
        int op, a, b;
        cin >> op >> a >> b;
        if(op == 1) add(a, b);
        else{
            cout << sum(b) - sum(a - 1) << endl;
        }
    }
    return 0;
}

线段树

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

const int N = 1000010;

int n, m;
int w[N];
struct Node
{
    int l, r;
    LL sum, add;
    // TODO: 需要维护的信息和懒标记
}tr[N * 4];
//单点修改，区间查询
 
void pushup(int u)//u为根节点
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
    // TODO: 利用左右儿子信息维护当前节点的信息
}

void pushdown(int u)
{
    auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
    if(root.add)
    {
        left.add += root.add, left.sum += (LL)(left.r - left.l + 1) * root.add;
        right.add += root.add, right.sum += (LL)(right.r - right.l + 1) * root.add;
        root.add = 0;
    }
    // TODO: 将懒标记下传
}

void build(int u, int l, int r)//建树
{
    if (l == r) tr[u] = {l, r, w[r], 0};
    else
    {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

// void update(int u, int pos, int val)// 单点修改
// {
//     if(tr[u].l == pos && tr[u].r == pos) tr[u].v = val;
//     else
//     {
//         int mid = tr[u].l + tr[u].r >> 1;
//         if(pos <= mid) 
//             update(u << 1, pos, val);
//         else 
//             update(u << 1 | 1, pos, val);
//         pushup(u);
//     }
// }
void update(int u, int l, int r, int d)//区间修改
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].sum += (LL)(tr[u].r - tr[u].l + 1) * d;
        tr[u].add += d;
        // TODO: 修改区间
    }
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) update(u << 1, l, r, d);
        if (r > mid) update(u << 1 | 1, l, r, d);
        pushup(u);
    }
}

LL query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        return tr[u].sum;  
        // TODO 需要补充返回值
    }
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        LL res = 0;
        if (l <= mid ) res = query(u << 1, l, r);
        if (r > mid) res += query(u << 1 | 1, l, r);
        return res;
    }
}


int main()
{
    scanf("%d%d", &n, &m);
    
    for(int i = 1; i <= n; i++) scanf("%d", &w[i]);
    
    build(1, 1, n);
    
    while (m -- )
    {
        int op, l, r, x;
        scanf("%d%d%d", &op, &l, &r);
        if(op == 1)
        {
            scanf("%d", &x);
            update(1, l, r, x);
        }
        else printf("%lld\n", query(1, l, r));
    }
    
    return 0;
}

ST表

主要用来解决RMQ（Range Maximum/Minimum Query，区间最大/最小值查询）问题。它主要应用倍增的思想，可以实现 $O(nlogn)$预处理、$O(1)$查询。

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

const int N = 200010, M = 20;
int n, m;
int w[N];
int f[N][M];//max
int g[N][M];//min


void init()
{
    for(int j = 0; j < M; j++)
        for(int i = 1; i + (1 << j) - 1 <= n; i++)
            if(!j) g[i][j] = f[i][j] = w[i];
            else {
                f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
                g[i][j] = min(g[i][j - 1], g[i + (1 << j - 1)][j - 1]);
            }
}   

int query_max(int l, int r)
{
    int len = r - l + 1;
    int k = (int)(log(len) / log(2));
    return max(f[l][k], f[r - (1 << k) + 1][k]);
}

int query_min(int l, int r)
{
    int len = r - l + 1;
    int k = log(len) / log(2);
    return min(g[l][k], g[r - (1 << k) + 1][k]);
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%d", &w[i]);
    
    init();
    
    while (m -- ){
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", query_max(l, r) - query_min(l, r));
    }
    
    return 0;
}

搜索与图论

最短路算法分为两大类：

单源最短路，常用算法有：
(1) dijkstra，只有所有边的权值为正时才可以使用。在稠密图上的时间复杂度是 O($n^{2}$)，稀疏图上的时间复杂度是 O($mlogn$)。
(2) spfa，不论边权是正的还是负的，都可以做。算法平均时间复杂度是 O($km$)O($km$)，k 是常数。强烈推荐该算法。
多源最短路，一般用floyd算法。代码很短，三重循环，时间复杂度是 O($n^{3}$)。

最大值：INF = 0x3f3f3f3f;

初始化：memset(d, 0x3f, sizeof d);

迪杰斯特拉

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

typedef pair<int, int> PII;

const int N = 2510, M = 6210;
int n, m, x, y;

int h[N], e[M << 1], ne[M << 1], w[M << 1], idx; // 邻接表存储所有边
bool st[N];// 存储每个点的最短距离是否已确定
int d[N]; // 存储所有点到1号点的距离

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;    
}

// 求u号点到n号点的最短距离，如果不存在，则返回-1
void dijkstra(int u)
{
    memset(d, 0x3f3f3f3f, sizeof d);
    d[u] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, u}); // first存储距离，second存储节点编号
    
    while(heap.size())
    {
        auto t = heap.top();
        heap.pop();
        int ver = t.second;
        if(st[ver]) continue;
        st[ver] = true;
        
        for(int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(d[j] > d[ver] + w[i])
            {
                d[j] = d[ver] + w[i];
                heap.push({d[j], j});
            }
        }
    }
}

int main()
{
    memset(h, -1, sizeof h); // 这一步很关键！！！！！！！！！！！！！！
    scanf("%d%d%d%d", &n, &m, &x, &y);
    while (m -- ){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c); // 无向图则多添加一条反向边！！！
    }
    dijkstra(x);
    printf("%d", d[y]);
    return 0;
}

spfa

$bellman-ford$算法的优化版本，可以处理存在负边权的最短路问题。

最坏情况下的时间复杂度是 $O(nm)$，但实践证明$spfa$算法的运行效率非常高，期望运行时间是 $O(km)$，其中 $k $是常数。
但需要注意的是，在网格图中，$spfa$算法的效率比较低，如果边权为正，则尽量使用 $dijkstra$算法。

#include<bits/stdc++.h>
using namespace std;
const int N = 50010, M = 150010;
int h[N], e[M], w[M], ne[M], idx;
int d[N];
bool st[N];

void add(int a, int b, int c)  // 添加一条边a->b，边权为c
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void spfa()
{
    memset(d, -0x3f, sizeof d);
    queue<int> q;
    d[0] = 0;
    q.push(0);
    
    while(!q.empty())
    {
        int t = q.front();
        q.pop();
        st[t] = false;
        
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(d[j] < d[t] + w[i])
            {
                d[j] = d[t] + w[i];
                if(!st[j])
                {
                    st[j] = true;
                    q.push(j);
                }
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    memset(h, -1, sizeof h);
    for(int i = 1; i <= 50001; i++)
    {
        add(i - 1, i, 0);
        add(i, i - 1, -1);
    }
    
    for(int i = 0; i < n; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        a++, b++;
        add(a - 1, b, c);
    }
    spfa();
    cout << d[50001] << endl;
    
    return 0;
}

Floyd

标准弗洛伊德算法，三重循环。循环结束之后存储$d[i][j]$的就是点$i$到点$j$的最短距离。
需要注意循环顺序不能变：第一层枚举中间点，第二层和第三层枚举起点和终点。

// floyd 算法核心
for (int k = 1; k <= n; k++)
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

树上差分

99%情况下与LCA(最近公共祖先)一起出现

树上差分，准确来说不是算法，而是一种优秀的思想。是一个适用于树上区间操作的算法，它是差分数组，前缀和求解的树上拓展.

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

const int N = 50010, M = 2 * N;
int n, k;
int h[N], e[M], ne[M], idx;
int depth[N], d[N], fa[N][25], q[N];

void add(int a, int b)  // 添加一条边a->b
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void bfs(int root)
{
    memset(depth, 0x3f, sizeof depth);
    depth[0] = 0, depth[root] = 1;
    int hh = 0, tt = 0;
    q[0] = root;
    while(hh <= tt)
    {
        int t = q[hh++];
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(depth[j] > depth[t] + 1)
            {
                depth[j] = depth[t] + 1;
                q[++tt] = j;
                fa[j][0] = t;
                for(int k = 1; k <= 20; k++)
                    fa[j][k] = fa[fa[j][k - 1]][k - 1];
            }
        }
    }
}

int lca(int a, int b)
{
    if(depth[a] < depth[b]) swap(a, b);
    
    for(int k = 20; k >= 0; k--)
        if(depth[fa[a][k]] >= depth[b])
            a = fa[a][k];
    
    if(a == b) return a;
    for(int k = 20; k >= 0; k--)
        if(fa[a][k] != fa[b][k])
        {
            a = fa[a][k];
            b = fa[b][k];
        }
    return fa[a][0];
}   

int dfs(int u, int from)
{
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(j == from) continue;
        dfs(j, u);
        d[u] += d[j];
    }
}

int main()
{
    cin >> n >> k;
    memset(h, -1, sizeof h);
    for(int i = 1; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    bfs(1);
    
    for(int i = 0; i < k; i++)
    {
        int a, b;
        cin >> a >> b;
        int t = lca(a, b);
        d[a]++, d[b]++, d[t]--, d[fa[t][0]]--;
    }
    
    dfs(1, 0);
    int res = 0;
    for(int i = 1; i <= n; i++)
    {
        //printf("d[%d]:%d\n", i, d[i]);
        res = max(res, d[i]);
    }
    
    cout << res << endl;
    return 0;
}

拓扑排序

首先遍历一遍图，找出入度为0的点，把它push到队列中去，然后把这个点延伸出来的边都去除掉，（d[指向的点]–），最后判断ans数组是否大小为n，不为n则输出-1；

int topsort()
{
    int cnt = 0;
    for(int i = 1; i <= n; i++)
        if(d[i] == 0) q.push(i), cnt++;//stl的queue

    while(q.size())
    {
        int t = q.front();
        q.pop();
        ans.push_back(t); //记录拓扑序
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            d[j] --;
            if(d[j] == 0)
                q.push(j), cnt++;
        }
    }
    return ans.size() == n ;
}

匈牙利算法

解决二分图的最大匹配问题

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

const int N = 210, M = N * N;
int n, m;
int h[N], e[M], ne[M], idx;
int st[N];
int match[N];

void add(int a, int b)  // 添加一条边a->b
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

bool find(int u)
{
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(!st[j])
        {
            st[j] = true;
            if(match[j] == 0 || find(match[j]))
            {
                match[j] = u;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    while(scanf("%d%d", &n, &m) != EOF)
    {
        idx = 0;
        memset(match, 0, sizeof match);
        memset(h, -1, sizeof h);
        for(int i = 1; i <= n; i++)
        {
            int cnt;
            scanf("%d", &cnt);
            while(cnt--)
            {
                int x;
                scanf("%d", &x);
                add(i, x);
            }
        }
        
        int res = 0;
        for(int i = 1; i <= n; i++)
        {
            memset(st, 0, sizeof st);
            if(find(i)) res++;
        }
        printf("%d\n", res);
    }
    return 0;
}

Kruskal

求最小生成树

struct Edge{
    int a, b, w;//a->b，边权为w
    bool operator< (const Edge &tmp)const {
        return w < tmp.w;
    }
}edges[M];

int kruskal()
{
    sort(edges, edges + m, cmp);
    for(int i = 1; i <= n; i++) f[i] = i;

    int res = 0, cnt = 0;
    for(int i = 0; i < m; i++)
    {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;
        a = find(a), b = find(b);
        if(a != b)
        {
            f[a] = b;
            res += w;
            cnt++;
        }
    }
    if(cnt < n - 1) return INF;
    return res;
}

Prim

求最小生成树

int prim()
{
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    int res = 0;
    for(int i = 0; i < n; i++)
    {
        int t = -1;
        for(int j = 1; j <= n; j++)
            if(!st[j] && (t == -1 || d[t] > d[j]))
                t = j;

        if(d[t] == INF) return INF;
        res += d[t];

        for(int j = 1; j <= n; j++) d[j] = min(d[j], g[t][j]);
        st[t] = true;
    }
    
    return res;
}

BFS与DFS

$BFS$与$DFS$的大致模板写法

int bfs()
{
    memset(d, -1, sizeof d);
    d[1] = 0;
    q.push(1);

    while(q.size())
    {
        int t = q.front();
        q.pop();
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(d[j] == -1)
            {
                d[j] = d[t] + 1;
                q.push(j);
            }
        }
    }
    return d[n];
}

void dfs(int u)//按照字典序将所有的1~n的排列方法输出
{
    if(u == n)
    {
        for(int i = 0; i < n; i++) cout << path[i] << ' ';
        cout << endl;
    }

    for(int i = 1; i <= n; i++)
    {
        if(!st[i])
        {
            path[u] = i;
            st[i] = true;
            dfs(u + 1);
            st[i] = false;
        }
    }
}

数论

线性筛质数

void get_primes(int n)  // 线性筛质数
{
    for(int i = 2; i <= n; i++)
    {
        if(!st[i]) primes[cnt ++] = i;
        for(int j = 0; primes[j] <= n / i; j++)
        {
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break;
        }
    }
}

快速幂

LL qmi(int a, int k, int p)
{
    LL res = 1;
    while(k)
    {
        if(k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}

欧几里得算法

int gcd(int a, int b)  // 求最大公约数
{
    return b ? gcd(b, a % b) : a;
}

求组合数

版本1：

公式：$C^b_a=C^{b-1}{a-1}+C^b{a-1}$

void init()
{
    for(int i = 0; i < N; i++)
        for(int j = 0; j <= i; j++)
        {
            if(!j) c[i][j] = 1;
            else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
        }
}

版本2：

费马小定理：a^(p-1) ≡1(mod p)

当b与m互质时，b的乘法逆元为b^(m-2)

公式：$C^b_a=\frac{a!}{b!(a−b)!}=a! \ast b!^{-1} \ast (a-b)!^{-1}$

for(int i = 1; i < N; i++)
{
    fact[i] = (LL)fact[i - 1] * i % mod;
    infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
}
while (n -- ){
    int a, b;
    cin >> a >> b;
    cout << (LL)fact[a] * infact[b] % mod * infact[a - b] % mod << endl;;
}

版本3：

$Lucas$定理：$C_{a}^{b} \equiv C_{a % p}^{b % p} * C_{\frac{a}{p}}^{\frac{b}{p}}(mod\ p)$

int C(int a, int b)
{
    if(b > a) return 0;

    LL res = 1;
    for(int i = 1, j = a; i <= b; i++, j--)
    {
        res = (LL)res * j % p;
        res = (LL)res * qmi(i, p - 2) % p;
    }
    return res;
}

int lucas(LL a, LL b)
{
    if(a < p && b < p) return C(a, b);
    return (LL)C(a % p, b % p) * lucas(a / p, b / p) % p;
}

动态规划

01背包问题

n表示物体数量，m表示背包总体积

//二维形式
for(int i = 1; i <= n; i++)
    for(int j = 0; j <= m; j++)
    {
        if(j < v[i])   f[i][j] = f[i - 1][j];
        else f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
    }

//一维形式
for(int i = 1; i <= n; i++)
        for(int j = m; j >= v[i]; j--)
            f[j] = max(f[j], f[j - v[i]] + w[i]);

完全背包问题

一维形式版本

for(int i = 1; i <= n; i++)
    for(int j = v[i]; j <= m; j++)
        f[j] = max(f[j], f[j - v[i]] + w[i]);

二进制优化版本

int cnt = 0;
//利用二进制分解
for(int i = 1; i <= n; i++)
{
    int a, b, s;
    cin >> a >> b >> s;

    int k = 1;
    while(k <= s)
    {
        cnt++;
        v[cnt] = a * k;
        w[cnt] = b * k;
        s -= k;
        k *= 2;
    }

    if(s > 0)
    {
        cnt ++;
        v[cnt] = a * s;
        w[cnt] = b * s;
    }
}
n = cnt;
//然后按照01背包问题求解
for(int i = 1; i <= n; i++)
        for(int j = m; j >= v[i]; j--)
            f[j] = max(f[j], f[j - v[i]] + w[i]);

分组背包

$S_i$表示第$i$组物品组的物品个数

$v_{ij}$表示物体的体积，$i$表示组号，$j$表示组内编号

for(int i = 1; i <= n; i++)
{
    cin >> s[i];
    for(int j = 0; j < s[i]; j++)
        cin >> v[i][j] >> w[i][j];
}

for(int i = 1; i <= n; i++)
    for(int j = m; j >= 0; j--)
        for(int k = 0; k < s[i]; k++)
            if(v[i][k] <= j)
                f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);

最长上升子序列

$dp$做法

for(int i = 1; i <= n; i++)
{
    f[i] = 1;
    for(int j = 1; j < i; j++)
        if(a[j] < a[i])
            f[i] = max(f[i], f[j] + 1);
}

int res = 0;
for(int i = 1; i <= n; i++)
    res = max(res, f[i]);

贪心做法

vector<int> stk;//模拟堆栈

void change(int x)
{
    int l = 0, r = stk.size() - 1;
    while(l < r)
    {
        int mid = l + r >> 1;
        if(stk[mid] >= x) r = mid;
        else l = mid + 1;
    }

    stk[r] = x;
}

int main()
{
    vector<int>arr(n);
    for (int i = 0; i < n; i++) cin >> arr[i];
    stk.push_back(arr[0]);
    
    for (int i = 1; i < n; i++) {
        if (arr[i] > stk.back())//如果该元素大于栈顶元素,将该元素入栈
            stk.push_back(arr[i]);
        else//替换掉第一个大于或者等于这个数字的那个数
            change(arr[i]);
    }
    cout << stk.size() << endl;
}

区间dp

所有的区间$dp$问题，第一维都是枚举区间长度，一般 $len = 1$ 用来初始化，枚举从$len = 2$开始，第二维枚举起点 $i$（右端点 j 自动获得，$j = i + len - 1$）

for(int i = 1; i <= n; i++)
{
    cin >> a[i];
    s[i] = s[i - 1] + a[i];//前缀和
    f[i][i] = 0;
}
// 区间 DP 枚举套路：长度+左端点 
for(int len = 2; len <= n; len++)// len表示i和j堆下标的差值
    for(int i = 1; i + len - 1 <= n; i++)
    {
        int l = i, r = i + len - 1; // 自动得到右端点
        for(int k = l; k < r; k++)
            f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
    }

Allen Sun

http://sun-hailong.github.io/2021/11/17/suan-fa-ban-zi/

本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Allen Sun !

算法模板

用随机梯度下降来优化人生

最近看到李沐老师的文章，勉励一下自己。

2021-11-25 生活

生活

六级英语写作

整理了一些六级英语写作的好用模板

2021-11-11 六级英语

英语写作

基础算法

快速排序

归并排序

二分

高精度

前缀和与差分

双指针算法

位运算

离散化

区间合并

数据结构

单调栈

单调队列

KMP算法

并查集

树状数组

线段树

ST表

搜索与图论

迪杰斯特拉

spfa

Floyd

树上差分

拓扑排序

匈牙利算法

Kruskal

Prim

BFS与DFS

数论

线性筛质数

快速幂

欧几里得算法

求组合数

动态规划

01背包问题

完全背包问题

分组背包

最长上升子序列

区间dp

你的赏识是我前进的动力