算法模版

算法模版

前言：

这是笔者在学习算法过程中遇到的一些经典问题，针对这些问题，整合了一套算法模版，来帮助自己复习。

二分算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 整数二分
while (l <= r) {
    int mid = (l + r) > 1;
    if (q[x] > q[mid]) {
        l = mid + 1;
    } eles if (q[x] < q[mid]) {
        r = mid - 1;
    } else return mid;
}

// 浮点数二分
bool check(double x) {/* ... */} // 检查x是否满足某种性质

double bsearch_3(double l, double r) {
    const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求
    while (r - l > eps) {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

高精度问题

  1. 高精度加法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <vector>

using namespace std;

const int N = 1e6 + 10;

vector<int> add(vector<int>& A, vector<int>& B) {
    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size() || i < B.size(); i ++ ) {
		if (i < A.size()) t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }
    
    if (t) C.push_back(t);
    
    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 -- ) cout << C[i] << ' ';
    
    return 0;
}
  1. 高精度减法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <vector>

using namespace std;

const int N = 1e6 + 10;

bool cmp(vector<int>& A, vector<int>& B) {
    // A是否大于等于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;
}

vector<int> sub(vector<int>& A, vector<int>& B) {
    vector<int> C;
    for (int i = 0, t = 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 -- ) cout << C[i] << ' ';
    } else {
        auto C = sub(B, A);
        cout << '-';
        for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i] << ' ';
    }
       
    return 0;
}
  1. 高精度乘低精度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <vector>

using namespace std;

const int N = 1e6 + 10;

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;
    }

    return C;
}

int main() {
	string a;
    int b;
    vector<int> A;
    
    
    cin >> a;
    cin >> 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 -- ) cout << C[i] << ' ';
       
    return 0;
}
  1. 高精度除以低精度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#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;

    cin >> a >> b;

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

    int r; // 余数
    auto C = div(A, b, r);

    for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i] << ' ';
    cout << endl << r << endl;
    return 0;
}

约瑟夫环问题

  1. 问题介绍

​ 编号为 1-N 的 N 个士兵围坐在一起形成一个圆圈，从编号为 1 的士兵开始依次报数（1，2，3…这样依次报），数到 m 的 士兵会被杀死出列，之后的士兵再从 1 开始报数。直到最后剩下一士兵，求这个士兵的编号。

  1. 代码
1
2
3
int f(int n, int m){
    return n == 1 ? n : (f(n - 1, m) + m - 1) % n + 1;
}

排序算法

  1. 快速排序
1
2
3
4
5
6
7
8
9
10
11
12
void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;
    int i = l - 1, j = r + 1, x = q[l];
    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);
}
  1. 归并排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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];
}

  1. 堆排序
  • 堆是一个完全二叉树
  • 大根堆、小根堆
  • 上滤：$o(log^n)$
  • 下滤：$o(logn)$
  • 建堆：从上往下插入元素，每插入一个元素，执行上滤 $o(nlogn)$
  • 建堆：自下而上，对每个非叶结点执行下滤操作 $o(n)$
  • 下标为i的父节点(i - 1) / 2
  • 下标为i的左孩子 (i * 2) + 1
  • 下标为i的右孩子 (i * 2) + 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

void heapify(vector<int>& arr, int len, int i) {
    int largest = i;
    int lson = i * 2 + 1;
    int rson = i * 2 + 2;

    if (lson < len && arr[largest] < arr[lson]) {
        largest = lson;
    }

    if (rson < len && arr[largest] < arr[rson]) {
        largest = rson;
    }

    if (largest != i) {
        swap(arr[largest], arr[i]);
        heapify(arr, len, largest);
    } 
}

void heap_sort(vector<int>& arr, int len) {
    int i;

    // 第一个非叶节点
    // 最后一个节点下标为len - 1, len - 1的父节点为len / 2 - 1
    for (i = len / 2 - 1; i >= 0; i -- ) {
        // 对每个非叶结点执行下滤
        heapify(arr, len, i);
    }

    // 排序
    for (i = len - 1; i > 0; i -- ) {
        swap(arr[i], arr[0]);
        // 传入i的原因是 每次取走一个元素 数组长度-1
        heapify(arr, i, 0);
    }
}

int main() {
     vector<int> num = {-1, 2, 0, 9, 3};
     heap_sort(num, num.size());

     for (int i = 0; i < num.size(); i ++ ) cout << num[i] << ' ';
     return 0;
}

前缀和和差分

  1. 前缀和

一维：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int n, m;
int a[N], s[N];

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

    for (int i = 1; i <= n; i ++ ) cin >> a[i];

    for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + a[i]; 

    while (m -- ) {
        int l, r;
        cin >> l >> r;
        cout << s[r] - s[l - 1] << endl;
    }

    return 0;
}

二维：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

const int N = 1e3 + 10;

int n, m, q;
int a[N][N], s[N][N];

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

    for (int i = 1; i <= n; i ++ ) {
        for (int j = 1; j <= m; j ++ ) cin >> a[i][j];
    }

    for (int i = 1; i <= n; i ++ ) {
        for (int j = 1; j <= m; j ++ ) s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j- 1] + a[i][j];
    }

    while (q --  ) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;

        cout << s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1] << endl;
    }


    return 0;
}
  1. 差分

一维

构造$b$数组，使得$ai = b1 + b2 + b3 + … +bi$

如果想让$a$数组$[l, r]$区间统一加上或减去某个值$c$，只需要让$bl + c, br - c$

我们可以假定$a$数组初始全部为$0$，那么$b$数组初始也全部为$0$，我们可以执行$n$次插入操作，让$a[i, i]$位置加上$a[i]$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>

using namespace std;

const int N = 1e4 + 10;

int n, m;
int a[N], b[N];

void insert(int l, int r, int c) {
    b[l] += c;
    b[r + 1] -= c;
}

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

    for (int i = 1; i <= n; i ++ ) cin >> a[i];

    for (int i = 1; i <= n; i ++ ) insert(i, i, a[i]);

    while (m -- ) {
        int l, r, c;
        cin >> l >> r >> c;
        insert(l, r, c);
    }

    for (int i = 1; i <= n; i ++ ) b[i] += b[i - 1];

    for (int i = 1; i <= n; i ++ ) cout << b[i] << ' ';

    return 0;
}

二维

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>


using namespace std;

const int N = 1e3 + 10;

int n, m, q;
int a[N][N], b[N][N];

void insert(int x1, int y1, int x2, int y2, int c) {
    b[x1][y1] += c;
    b[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y2 + 1] += c;
}

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

    for (int i = 1; i <= n; i ++ ) {
        for (int j = 1; j <= m; j ++ ) {
            cin >> a[i][j];
        }
    }

    for (int i = 1; i <= n; i ++ ) {
        for (int j = 1; j <= m; j ++ ) {
            insert(i, j, i, j, a[i][j]);
        }
    }

    while (q -- ) {
        int x1, y1, x2, y2, c;
        cin >> x1 >> y1 >> x2 >> y2 >> c;
        insert(x1, y1, x2, y2, c);
    }

    for (int i = 1; i <= n; i ++ ) {
        for (int j = 1; j <= m; j ++ ) {
            b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
        }
    }

    for (int i = 1; i <= n; i ++ ) {
        for (int j = 1; j <= m; j ++ ) {
            cout << b[i][j] << ' ';
        }
        cout << endl;
    }

    return 0;
}

双指针、位运算、离散化、区间合并

双指针

1
2
3
4
5
6
7
8
9
for (int i = 0, j = 0; i < n; i ++ )
{
    while (j < i && check(i, j)) j ++ ;

    // 具体问题的逻辑
}
常见问题分类：
    (1) 对于一个序列，用两个指针维护一段区间
    (2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作

模版题：
LCR 016. 无重复字符的最长子串 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    unordered_map<char, int> umap;
    int lengthOfLongestSubstring(string s) {
        int res = 0;
        for (int i = 0, j = 0; i < s.size(); i ++ ) {
            // 先把当前字符加进来
            umap[s[i]] ++;

            // 去掉不符合的情况
            while (umap[s[i]] > 1) {
                umap[s[j]] --;
                j ++;
            }

            // 更新结果
            res = max(res, i - j + 1);
        }
        return res;
    }
};

位运算

1
2
3
4
5
6
7
8
9
10
11
// 最常用的两种操作
// 判断x的第i位是0还是1
(x >> i) & 1

// lowbit(x) 返回x的最后一位1
int lowbit(int x) {
    return x & -x;
}

// 求x的二进制表示中有多少个1
while (x) x -= lowbit(x); cnt ++;

离散化

  1. 对a数组去重
  2. 如何算出a[i]离散化后的值
1
2
3
4
// 把数组a中的元素映射到某个区间
vector<int> a;
sort(a.begin(), a.end());
a.erase(unique(a.begin(), a.end()), a.end());

模版题：

AcWing 802 区间和_acwing 802区间和-CSDN博客

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <vector>
#include <algorithm>

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;
    for (int i = 0; i < n; i ++ ){
        int x, c;
        cin >> x >> c;
        add.push_back({x, c});
        alls.push_back(x);
    }
 
    for (int i = 0; i < m; i ++ ){
        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;
}

区间合并

有交集的区间，就合并

  1. 按照区间左端点排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef pair<int, int> PII;

int n, l, r;
vector<PII> segs;

void merge(vector<PII> &segs)
{
    vector<PII> res;
    
    sort(segs.begin(), segs.end());//按区间左端点排序，sort默认排序segs的第一项
    
    int st = -2e9, ed = -2e9;//此时st和ed只要比-1e9小就可以
    for (auto seg : segs)
    {
        if (ed < seg.first)
        {
            if (st != -2e9) res.push_back({st, ed});
            st = seg.first;
            ed = seg.second;
        }
        else ed = max(ed, seg.second);
    }
    
    if (st != -2e9) res.push_back({st, ed});
    
    segs = res;//不能忘
}

int main()
{
    cin >> n;
    
    for (int i = 0; i < n; i ++ )
    {
        cin >> l >> r;
        segs.push_back({l, r});
    }
    
    merge(segs);
    
    cout << segs.size() << endl;
    
    return 0;
}//该代码引用AcWing网站的代码

数据结构

这一部分主要是讲解如何用数组模拟常用的数据结构，面试中不常考，笔试中可以用

链表与邻接表

AcWing 826. 单链表（C++算法）_acwing c++ 链表实现-CSDN博客

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
// 单链表中的邻接表最常用，可以用来存储树和图
#include <iostream>

using namespace std;

void init();
void add_to_head(int x);
void remove_(int k);
void add(int k, int x);

const int N = 100010;

int head, idx, e[N], ne[N];//head表示头结点的下标，idx记录用到第几个点（从0开始），e[idx]表示这个点的值，ne[idx]表示这个点后一个点的下标

void init()//初始化函数
{
    head = -1;
    idx = 0;
}

void add_to_head(int x)//将一个数x插入头结点，原头结点的数后移
{
    e[idx] = x;
    ne[idx] = head;
    head = idx ++ ;//其实是先让head表示新的头结点的下标idx,idx再计数
}

void remove_(int q)//删掉下标为q的数的后面那个数
{
    ne[q] = ne[ne[q]];
}

void add(int q, int x)//将一个数x插入下标为q的数的后面一位
{
    e[idx] = x;
    ne[idx] = ne[q];
    ne[q] = idx ++ ;
}//该代码引用AcWing网站的代码

int main()
{
    int m;
    cin >> m;
    
    init();//一定要初始化
    
    while (m -- )
    {
        char op;
        int x, k;
        
        cin >> op;
        
        if (op == 'H')
        {
            cin >> x;
            add_to_head(x);
        }
        else if (op == 'D')
        {
            cin >> k;
            if (k == 0) head = ne[head];//题中“当k为0时，表示删除头结点”
            else remove_(k - 1);
        }
        else
        {
            cin >> k >> x;
            add(k - 1, x);
        }
    }
    
    for (int i = head; i != -1; i = ne[i]) cout << e[i] << ' ';
    
    return 0;
}

栈与队列

1

KMP

1

进制转换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

int main() {
    int a, k;
    vector<int> path;
    cin >> a >> k;
    // 八进制
    cout << oct << a << endl; 

    // 十六进制
    cout << hex << a << endl;

    // 进制转换
    // 将a转为k进制
    while (a != 0) {
        int t = a % k;
        path.push_back(t);
        a = a / k;
    }
    for (int i = path.size() - 1; i >= 0; i -- ) cout << path[i] << ' ';
    return 0;
}

树状数组和线段树

  1. 树状数组

树状数组是线段树的子集

树状数组代码短，运行效率高

$O(logn)$的时间复杂度执行两种操作

  • 给某个位置上的数加上一个数(单点修改)
  • 求前缀和(区间查询)

原数组为A，A下标从1开始

树状数组为C，构建C

$C[i]$表示$(x - lowbit(x), x]$这个区间的和，左开右闭，$lowbit(x) = 2^k$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
int n, m;
int a[N], tr[N];

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

void add(int x, int v) {
    // 在x位置上加上v
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += v;
}

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

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

    for (int i = 1; i <= n; i ++ ) cin >> a[i];

    for (int i = 1; i <= n; i ++ ) add(i, a[i]);

    while (m -- ) {
        int k, x, y;
        cin >> k >> x >> y;
        if (k == 0) cout << query(y) - query(x - 1) << endl;
        else add(x, y);
    } 

    return 0;
}
  1. 线段树

线段树是一个完全二叉树，线段树里每个元素是一个结构体

image-20241205194141141

  • pushup：用子节点信息更新当前节点信息
  • build：在一段区间上初始化线段树
  • modify：修改
  • query：查询
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
// 线段树
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int n, m;
int w[N];

struct node {
    int l, r;
    int sum;
} tr[N * 4];

void pushup(int u) {
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

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

int query(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
    int mid = tr[u].l + tr[u].r >> 1;

    int sum = 0;
    if (l <= mid) sum += query(u << 1, l, r);
    if (r > mid) sum += query(u << 1 | 1, l, r);
    return sum;
}

void modify(int u, int x, int v) {
    if (tr[u].l == tr[u].r) tr[u].sum += v;
    else {
        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid) modify(u << 1, x, v);
        else modify(u << 1 | 1, x, v);
        pushup(u);
    }
}

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

    for (int i = 1; i <= n; i ++ ) cin >> w[i];

    build(1, 1, n); 

    while (m -- ) {
        int k, a, b;

        cin >> k >> a >> b;

        if (k == 0) {
            // 求和
            cout << query(1, a, b) << endl;
        } else {
            modify(1, a, b);
        }
    }

    return 0;
}

并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int n = 1005;
vector<int> father = vector<int> (n, 0);

void init() {
    for (int i = 0; i < n; i ++ ) father[i] = i;
}

int find(int u) {
    if (u == father[u]) return u;
    else return father[u] = find(father[u]);
}

bool isSame(int u, int v) {
    u = find(u);
    v = find(v);
    return u == v;
}

void join(int u, int v) {
    u = find(u);
    v = find(v);
    if (u == v) return;
    else fater[v] = u;
}

最小生成树

  1. prim算法(适合稠密图)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
// prim算法
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

int res;

int main() {
    int v, e;
    int x, y, k;

    cin >> v >> e;

    vector<vector<int>> grid(v + 1, vector<int>(v + 1, 1e4 + 10));

    while (e -- ) {
        cin >> x >> y >> k;
        grid[x][y] = k;
        grid[y][x] = k;
    }

    vector<int> min_Dist(v + 1, 1e4 + 10);
    vector<bool> vis(v + 1, false);

    min_Dist[1] = 0;

    for (int i = 1; i <= v; i ++ ) {
        int cur = -1; 
        int dis_min = INT_MAX;
        for (int j = 1; j <= v; j ++ ) {
            if (vis[j] == false && min_Dist[j] < dis_min) {
                dis_min = min_Dist[j];
                cur = j;
            }
        }
        vis[cur] = true;
        res += dis_min;

        for (int j = 1; j <= v; j ++ ) {
            if (grid[cur][j] < min_Dist[j]) {
                min_Dist[j] = grid[cur][j];
            }
        }
    }

    cout << res;

    return 0;
}
  1. kruskal算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
// kruskal算法
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

struct node {
    int l, r, val;
    node() : l(0), r(0), val(0) {}
    node(int _l, int _r, int _val) : l(_l), r(_r), val(_val) {}
};

const int N = 1e4 + 10;
int min_Dist[N];
int father[N];
int v, e;
int res;

void init() {
    for (int i = 1; i <= v; i ++ ) father[i] = i;
}

int find(int u) {
    if (u == father[u]) return u;
    else return father[u] = find(father[u]);
}

bool is_Same(int u, int v) {
    u = find(u);
    v = find(v);
    return u == v;
}

void join(int u, int v) {
    u = find(u);
    v = find(v);
    if (u == v) return;
    else father[v] = u;
}

int main() {
    cin >> v >> e;

    init();

    vector<node> grid;
    for (int i = 1; i <= e; i ++ ) {
        int l, r, val;
        cin >> l >> r >> val;
        node temp = node(l, r, val);
        grid.push_back(temp);
    }

    sort(grid.begin(), grid.end(), [](node a, node b) {return a.val < b.val;});

    for (int i = 0; i < grid.size(); i ++ ) {
        if (!is_Same(grid[i].l, grid[i].r)) {
            res += grid[i].val;
            join(grid[i].l, grid[i].r);
        }
    }

    cout << res;

    return 0;
}

拓扑排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
int n, m;
int in_grid[N]; // n个节点的入度

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

    unordered_map<int, vector<int>> umap; // 节点之间的依赖

    for (int i = 1; i <= m; i ++ ) {
        int l, r;
        cin >> l >> r;
        umap[l].push_back(r);
        in_grid[r] ++;
    }

    vector<int> ans;
    queue<int> que; // 存放入度为0的点
    for (int i = 0; i < n; i ++ ) {
        if (in_grid[i] == 0) que.push(i);
    }

    while (!que.empty()) {
        int top = que.front();
        que.pop();
        ans.push_back(top);

        // 从top到i有边 说明i依赖top
        vector<int> temp = umap[top];
        for (int i = 0; i < temp.size(); i ++ ) {
            in_grid[temp[i]] --;
            if (in_grid[temp[i]] == 0) que.push(temp[i]);
        }
    }


    if (ans.size() < n) cout << -1;
    else {
        for (int i = 0; i < ans.size() - 1; i ++ ) cout << ans[i] << ' ';
        cout << ans[ans.size() - 1];
    }

    return 0;
}

单源最短路径 Dijkstra算法

1

任意点的最短路径 floyd算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// floyd算法
// floyd算法对于负权图、有向图、无向图都适用
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

int main() {
    // n个节点 m条边
    int n, m, p1, p2, val;
    cin >> n >> m;

    vector<vector<int>> grid(n + 1, vector<int>(n + 1, 10010));

    for (int i = 0; i < m; i ++ ) {
        cin >> p1 >> p2 >> val;
        grid[p1][p2] = val;
        grid[p2][p1] = val;
    }

    // floyd
    for (int k = 1; k <= n; k ++ ) {
        for (int i = 1; i <= n; i ++ ) {
            for (int j = 1; j <= n; j ++ ) {
                grid[i][j] = min(grid[i][j], grid[i][k] + grid[k][j]);
            }
        }
    }

    int z, start, end;
    cin >> z;
    while (z -- ) {
        cin >> start >> end;
        if (grid[start][end] == 10010) cout << -1 << endl;
        else cout << grid[start][end] << endl;
    }

    return 0;
}

启发式搜索 A*算法

1

数论算法

欧几里得算法

1
2
3
4
5
// 辗转相除法求最大公约数
int gcd(int a, int b) {
    if (a % b == 0) return b;
    else return gcd(b, a % b);
}

素数筛选

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 埃氏筛 时间复杂度O(nloglog2n)
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

int primes[N], cnt;
bool st[N];

void get_primes(int n) {
    for (int i = 2; i <= n; i ++ ) {
        if (!st[i]) {
            primes[cnt ++ ] = i;
            for (int j = 2 * i; j <= n; j += i) st[j] = 1;
        }
    }
}

int main() {
    get_primes(10000);
    
    for (int i  = 0; i < 20; i ++ ) printf("%d\n", primes[i]);
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// 线性筛 O(n)的时间复杂度 求出1-n中所有的质数 以及每个数的最小质因子
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

int primes[N], cnt;
bool st[N];
int minp[N]; // 存放每个元素的最小质因子,质数没有最小质因子

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

int main() {
    get_primes(10000);
    
    for (int i  = 0; i < 20; i ++ ) printf("%d\n", primes[i]);
    
    return 0;
}
Leetcode
#Cpp语法 #常用算法模版
算法模版
http://example.com/2025/03/31/algorithm_template/
Author
yuanyuan
Posted on
March 31, 2025
Licensed under