蓝桥杯备考

蓝桥杯算法课

时间复杂度

1
2
3
4
5
// C++算法
// 1s 执行 1亿次运算
// 一般时间小于1e8的算法就是ok的
// int +-1e9
// long long +-1e18

image-20241118110552453

image-20241212095422001

递归与递推

递归

92. 递归实现指数型枚举 - AcWing题库
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;

int n;

vector<vector<int>> res;
vector<int> path;

void dfs(int index) {
    res.push_back(path);

    if (path.size() == n) return;

    for (int i = index; i <= n; i ++ ) {
        path.push_back(i);
        dfs(i + 1);
        path.pop_back();
    }
}

int main() {
    cin >> n;

    dfs(1);

    for (int i = 0; i < res.size(); i ++ ) {
        for (int j = 0; j < res[i].size(); j ++ ) {
            cout << res[i][j] << ' ';
        }
        cout << endl;
    }

    return 0;
}
93. 递归实现组合型枚举 - AcWing题库
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 <bits/stdc++.h>

using namespace std;

int n, m;

vector<vector<int>> res;
vector<int> path;

void dfs(int index) {
    if (path.size() == m) {
        res.push_back(path);
        return;
    }

    for (int i = index; i <= n && ((n - index + 1) >= (m - path.size())); i ++ ) {
        path.push_back(i);
        dfs(i + 1);
        path.pop_back();
    }
}

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

    dfs(1);

    for (int i = 0; i < res.size(); i ++ ) {
        for (int j = 0; j < m; j ++ ) {
            cout << res[i][j] << ' ';
        }
        cout << endl;
    }

    return 0;
}
94. 递归实现排列型枚举 - AcWing题库
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
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> res;
vector<int> path;

void track_back(int n, vector<int>& visit) {
    if (path.size() == n) {
        res.push_back(path);
        return;
    }

    for (int i = 1; i <= n; i ++ ) {
        if (visit[i] == 0) {
            visit[i] = 1;
            path.push_back(i);
            track_back(n, visit);
            visit[i] = 0;
            path.pop_back();
        }
    }
}


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

    vector<int> visit(n + 1, 0);

    track_back(n, visit);

    for (int i = 0; i < res.size(); i ++ ) {
        for (int j = 0; j < res[i].size(); j ++ ) {
            cout << res[i][j] << ' ';
        }
        cout << endl;
    }

    return 0;
}
1209. 带分数 - AcWing题库
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
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

const int N = 20;
int n = 0;
int ans = 0;
int vi[N];
int co[N];

bool check(int a, int c) {
    int b = n * c - a * c;

    if (!a || !b || !c) return false;

    memcpy(co, vi, sizeof vi);

    while (b) {
        int x = b % 10;
        b /= 10;
        if (!x || co[x]) return false;
        co[x] = 1;
    }

    for (int i = 1; i <= 9; i ++ ) {
        if (co[i] == 0) return false;
    }

    return true;
}

void dfs_c(int a, int c) {
    if (check(a, c)) ans ++;

    for (int i = 1; i <= 9; i ++ ) {
        if (vi[i] == 0) {
            vi[i] = 1;
            c = c * 10 + i;
            dfs_c(a, c);
            vi[i] = 0;
            c = c / 10;
        }
    }
}

void dfs_a(int a) {
    if (a > n) return; // 少了这一句会报错，不知道为什么

    if (a) dfs_c(a, 0);

    for (int i = 1; i <= 9; i ++ ) {
        if (vi[i] == 0) {
            vi[i] = 1;
            a = a * 10 + i;
            dfs_a(a);
            vi[i] = 0;
            a = a / 10;
        }
    }
}

int main() {
    cin >> n;

    dfs_a(0);

    cout << ans;

    return 0;
}

递推

717. 简单斐波那契 - AcWing题库

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;

const int N = 50;
int dp[N];
int n;

int main() {
    cin >> n;

    dp[0] = 0;
    dp[1] = 1;

    for (int i = 2; i < n; i ++ ) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    for (int i = 0; i < n; i ++ ) {
        cout << dp[i] << ' ';
    }

    return 0;
}
P10449 费解的开关 - 洛谷 | 计算机科学教育新生态
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
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

const int N = 6;
char g[N][N], backup[N][N];
int dx[5] = {-1, 0, 1, 0, 0};
int dy[5] = {0, 1, 0, -1, 0};

void turn(int x, int y) {
    for (int i = 0; i < 5; i ++ ) {
        int a = x + dx[i];
        int b = y + dy[i];
        if (a < 0 || a >= 5 || b < 0 || b >= 5) continue;
        g[a][b] ^= 1;
    }
}



int main() {
    int T;
    cin >> T;

    while (T -- ) {
        for (int i = 0; i < 5; i ++ ) cin >> g[i];

        int res = 10;

        for (int op = 0; op < 32; op ++ ) {
            memcpy(backup, g, sizeof g);

            int step = 0;
            for (int i = 0; i < 5; i ++ ) {
                if (op >> i & 1) {
                    step ++;
                    turn(0, i);
                }
            }

            for (int i = 1; i < 5; i ++ ) {
                for (int j = 0; j < 5; j ++ ) {
                    if (g[i - 1][j] == '0') {
                        step ++;
                        turn(i, j);
                    }
                }
            }

            bool dark = false;

            for (int i = 0; i < 5; i ++ ) {
                if (g[4][i] == '0') {
                    dark = true;
                    break;
                }
            }

            if (!dark) res = min(res, step);
            memcpy(g, backup, sizeof g);
        }
        if (res > 6) res = -1;
        cout << res << endl;
    }

    return 0;
}
116. 飞行员兄弟 - AcWing题库
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
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;

const int N = 5;
char g[N][N], backup[N][N];

int get(int x, int y) {
    return x * 4 + y;
}

void turn_one(int x, int y) {
    if (g[x][y] == '+') g[x][y] = '-';
    else g[x][y] = '+';
}

void turn_all(int x, int y) {
    for (int i = 0; i < 4; i ++ ) {
        turn_one(x, i);
        turn_one(i, y);
    }
    turn_one(x, y);
}

int main() {
    for (int i = 0; i < 4; i ++ ) cin >> g[i];

    vector<PII> res;

    for (int op = 0; op < 1 << 16; op ++ ) {
        vector<PII> temp;

        memcpy(backup, g, sizeof(g));

        for (int i = 0; i < 4; i ++ ) {
            for (int j = 0; j < 4; j ++ ) {
                if (op >> get(i, j) & 1) {
                    temp.push_back({i, j});
                    turn_all(i, j);
                }
            }
        }

        // check
        bool has_closed = true;
        for (int i = 0; i < 4; i ++ ) {
            for (int j = 0; j < 4; j ++ ) {
                if (g[i][j] == '+') has_closed = false;
            }
        }

        if (has_closed) {
            if (res.empty() || res.size() > temp.size()) res = temp;
        }

        memcpy(g, backup, sizeof(g));
    }

    cout << res.size() << endl;

    for (int i = 0; i < res.size(); i ++ ) {
        cout << res[i].first + 1 << ' ' << res[i].second + 1 << endl;
    }

    return 0;
}
1208. 翻硬币 - AcWing题库
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>
#include <bits/stdc++.h>

using namespace std;

int res;

int main() {
    string s, e;

    cin >> s >> e;

    for (int i = 0; i < s.size() - 1; i ++ ) {
        if (s[i] != e[i]) {
            res ++;
            s[i] = s[i] == '*' ? 'o' : '*';
            s[i + 1] = s[i + 1] == '*' ? 'o' : '*';
        }
    }

    cout << res;

    return 0;
}

二分与前缀和

枚举、模拟和排序

枚举

1210. 连号区间数 - AcWing题库
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
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

const int N = 1e4 + 10;
int number[N];
int n;
int res;

int main() {
    cin >> n;

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

    for (int l = 1; l <= n; l ++ ) {
        int _max = number[l];
        int _min = number[l];
        for (int r = l; r <= n; r ++ ) {
            _max = max(number[r], _max);
            _min = min(number[r], _min);
            if (_max - _min == r - l) res ++;
        }
    }

    cout << res;

    return 0;
}
1236. 递增三元组 - AcWing题库
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 a[N], b[N], c[N];
int as[N];
int cs[N];
int cnt[N], s[N];
int n;

int main() {
    cin >> n;

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

    // 求as
    for (int i = 1; i <= n; i ++ ) cnt[a[i]] ++;
    for (int i = 1; i < N; i ++ ) s[i] = s[i - 1] + cnt[i];
    for (int i = 1; i <= n; i ++ ) as[i] = s[b[i] - 1];

    // 求cs
    memset(cnt, 0, sizeof cnt);
    memset(s, 0, sizeof s);
    for (int i = 1; i <= n; i ++ ) cnt[c[i]] ++;
    for (int i = 1; i < N; i ++ ) s[i] = s[i - 1] + cnt[i];
    for (int i = 1; i <= n; i ++ ) cs[i] = s[N - 1] - s[b[i]];

    long long res = 0;
    for (int i = 1; i <= n; i ++ ) {
        res += (long long)as[i] * cs[i];
    } 

    cout << res << endl;

    return 0;
}
1245. 特别数的和 - AcWing题库
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
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

const int N = 1e4 + 10;
int n;
long long res;

bool check(int x) {
    while (x) {
        int temp = x % 10;
        if (temp == 2 || temp == 0 || temp == 1 || temp == 9) return true;
        x /= 10;
    }

    return false;
}

int main() {
    cin >> n;

    for (int i = 1; i <= n; i ++ ) {
        if (check(i)) res += i;
    }

    cout << res << endl;

    return 0;
}
1219. 移动距离 - AcWing题库
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

int main() {
    int w, m, n;

    cin >> w >> m >> n;
    m --, n --;

    int x1 = m / w, x2 = n / w;
    int y1 = m % w, y2 = n % 2;
    if (x1 % 2) y1 = w - 1 - y1;
    if (x2 % 2) y2 = w - 1 - y2;

    cout << abs(x1 - x2) + abs(y1 - y2) << endl;

    return 0;
}
1229. 日期问题 - AcWing题库
1

1231. 航班时间 - AcWing题库
1
// 学会怎么处理输入输出

排序

树状数组和线段树

树状数组

树状数组是线段树的子集

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

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

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

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

树状数组为C，构建C

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

1
2
3
int lowbit(int x) {
    return x & -x;
}
1264. 动态求连续区间和 - AcWing题库
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;
}
1265. 数星星 - AcWing题库
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
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

const int N = 32010;
int tr[N], ans[N];
int n;

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

int add(int x, int y) {
    for (int i = x; i <= N; i += lowbit(i)) tr[i] += y;
}

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

int main() {
    cin >> n;

    for (int i = 0; i < n; i ++ ) {
        int x, y;
        cin >> x >> y;
        x ++;

        ans[sum(x)] ++;
        add(x, 1);
    }

    for (int i = 0; i < n; i ++ ) cout << ans[i] << endl;

    return 0;
}

线段树

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

image-20241205194141141

  • pushup：用子节点信息更新当前节点信息
  • build：在一段区间上初始化线段树
  • modify：修改
  • query：查询
1
2
3
4
5
6
struct node {
    int l, r;
    int sum;
}
// 操作1 单点修改
// 操作2 区间查询
1264. 动态求连续区间和 - AcWing题库
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;
}
1270. 数列区间最大值 - AcWing题库
  1. 跳表-ST表
1

  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
52
53
54
#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 maxv;
}tr[N * 4];

void build(int u, int l, int r) {
    if (l == r) tr[u] = {l, r, w[l]};

    else {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        tr[u].maxv = max(tr[u << 1].maxv, tr[u << 1 | 1].maxv);
    }
}

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

    int mid = tr[u].l + tr[u].r >> 1;

    int maxv = INT_MIN;

    if (l <= mid) maxv = max(maxv, query(u << 1, l, r));
    if (r > mid) maxv = max(maxv, query(u << 1 | 1, l, r));
    return maxv;
}

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

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

    build(1, 1, n);

    int l, r;

    while (m -- ) {
        cin >> l >> r;
        cout << query(1, l, r) << endl;
    }

    return 0;
}

LCA&RMQ&树差分

LCA(lowest common ancestor 最近公共祖先)

朴素算法

倍增算法

tarjan算法

双指针、BFS与图论

双指针

1238. 日志统计 - AcWing题库

BFS

1101. 献给阿尔吉侬的花束 - AcWing题库
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
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

const int N = 220;
int t;
int n, m;
char grid[N][N];
bool vis[N][N];

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

int main() {
    cin >> t;

    while (t -- ) {
        int res = 0;
        bool flag = false;
        cin >> n >> m;

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

        int x1 = 1, y1 = 1, x2 = 1, y2 = 1;
        for (int i = 1; i <= n; i ++ ) {
            for (int j = 1; j <= m; j ++ ) {
                if (grid[i][j] == 'S') {x1 = i; y1 = j;}
                if (grid[i][j] == 'E') {x2 = i; y2 = j;}
            }
        }


        queue<pair<int, int>> que;
        que.push(make_pair(x1, y1));
        int count = que.size();
        vis[x1][y1] = true;

        while (!que.empty()) {
            while (count) {
                auto it = que.front();
                if (it.first == x2 && it.second == y2) {
                    flag = true;
                    break;
                }
                que.pop();
                count --;

                for (int i = 0; i < 4; i ++ ) {
                    int nx = it.first + dx[i];
                    int ny = it.second + dy[i];
                    if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
                    if (!vis[nx][ny] && grid[nx][ny] != '#') {
                        que.push(make_pair(nx, ny));
                        vis[nx][ny] = true;
                    }
                }
            }
            if (flag) break;
            count = que.size();
            res ++;
        }
        memset(vis, 0, sizeof(vis));
        if (flag) cout << res << endl;
        else cout << "oop!" << endl;
    }

    return 0;
}

图论

1224. 交换瓶子 - AcWing题库
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
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

const int N = 1e4 + 10;
int n;
int b[N];
bool st[N];

int main() {
    cin >> n;

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

    int cnt = 0;

    for (int i = 1; i <= n; i ++ ) {
        if (!st[i]) {
            cnt ++;
            for (int j = i; !st[j]; j = b[j]) {
                st[j] = true;
            }
        }
    }

    cout << n - cnt;
    return 0;
}

贪心

1055. 股票买卖 II - AcWing题库
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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>


using namespace std;

const int N = 1e5 + 10;
int profit;
int n;
int price[N];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &price[i]);

    int now_price = price[1];
    for (int i = 1; i <= n; i ++ ) {
        if (price[i] >= now_price) profit += price[i] - now_price;

        now_price = price[i];
    }

    printf("%d", profit);

    return 0;
}
104. 货仓选址 - AcWing题库
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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 1e5 + 10;
int n;
int ind[N];
int res;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &ind[i]);

    sort(ind + 1, ind + 1 + n);

    for (int l = 1, r = n; l < r; l ++ , r -- ) {
        res += ind[r] - ind[l];
    }

    printf("%d", res);

    return 0;
}
112
1

数论

欧几里得算法

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

算术基本定理

  1. 所有正整数n都可以表示为若干个质数的乘积
1
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
// 埃氏筛 时间复杂度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;
}
  1. 求x的约数个数

image-20241225183332841

1

  1. 约数之和

image-20241225183516478

1

裴蜀定理——扩展欧几里得算法

(没看懂。。)

若gcd(a, b) = d，则必有ax + by = d，每个数都是整数

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
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>


using namespace std;

int exgcd(int a, int b, int& x, int& y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }

    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;

    return d;
}

int main() {
    int a, b, x, y;

    cin >> a >> b;
    int d = exgcd(a, b, x, y);

    printf("%d * %d + %d * %d = %d", a, x, b, y, d);

    return 0;
}

复杂DP

1050. 鸣人的影分身 - AcWing题库

DFS

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;

int t;
int m, n;
int res;

void dfs(int e, int cnt, int ne) {
    if (cnt == n) {
        if (e == 0) res ++;
        return;
    }

    for (int i = ne; i <= e; i ++ ) {
        // 逐个遍历分配给下一个分身的能量
        // ne是当前要分配的能量，而下一个要分配的能量是>=ne的，因此相当于已经排序了
        // 对于213和123 只会枚举123 而不会枚举213 避免了重复 并且对于222这种组合 也可以枚举
        dfs(e - i, cnt + 1, i);
    }
}

int main() {
    cin >> t;

    while (t -- ) {
        res = 0;
        cin >> m >> n;
        dfs(m, 0, 0);

        cout << res << endl;
    }
}
1047
1222

疑难杂题

1242
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
#include <iostream>
#include <bits/stdc++.h>

const int N = 1100000;

using namespace std;

int p[N];
int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main() {
    int n;
    cin >> n;
    
    for (int i = 1; i < N; i ++ ) p[i] = i;
    for (int i = 1; i <= n; i ++ ) {
        int x;
        cin >> x;
        x = find(x);
        printf("%d ", x);
        p[x] = x + 1;
    }
    
    return 0;
}
Leetcode
#蓝桥杯
蓝桥杯备考
http://example.com/2025/03/25/lanqiao/
Author
yuanyuan
Posted on
March 25, 2025
Licensed under