alisa22580

公告

记录一些比较面向基础的东西，满足个人的一点创作欲，希望能帮到你。

Learn More

标签

alisa22580

公告

记录一些比较面向基础的东西，满足个人的一点创作欲，希望能帮到你。

Learn More

标签

ADB Android Demo GKD Markdown SelectEcho Shizuku Tutorial VPN vscode 算法竞赛蓝桥杯题解

656 字

2 分钟

蓝桥杯 C++ B 组常用板子

2026-04-10

Tutorial

蓝桥杯

/

算法竞赛

NOTE
个人复习用，由于打的 B组太难的也用不上，只整理了一点，用 ai 审核了一遍似乎是都能用在 cpp11 ，但是其实还是会心慌
希望一切顺利。

1. 基础中的基础#

1.1 基本板子#

1
#include <bits/stdc++.h>
2
using namespace std;
3
#define int long long
4
#define endl '\n'
5
#define all(x) (x).begin(), (x).end()
6

7
void solve()
8
{
9

10
}
11

12
signed main()
13
{
14
    cin.tie(0)->sync_with_stdio(0);
15
    cout << setiosflags(ios::fixed) << setprecision(2);
16
    int tt = 1;
17
    cin >> tt;
18
    while (tt--)
19
    {
20
        solve();
21
        cout << endl;
22
    }
23
}

1.2 常见类型范围#

int 约 $2.1 \times 10^9$ 。
long long 约 $9 \times 10^{18}$ 。

1.3 排序与比较器#

1
vector<pair<int,int>> a;
2
// cpp11 不支持 泛型lambda 因此传参时候不能使用 auto&& 可惜可惜
3
sort(a.begin(), a.end(), [](pair<int, int> x, pair<int, int> y) {
4
    if (x.first != y.first) return x.first < y.first;
5
    return x.second > y.second;
6
});

2. STL 高频容器和用法#

2.1 `string`#

子串：s.substr(pos, len)。
查找：s.find("abc")，找不到返回 string::npos。

2.2 `queue` / `priority_queue`#

1
queue<int> q;
2
q.push(1);
3
q.pop();
4

5
priority_queue<int> maxh; // 大根堆
6
priority_queue<int, vector<int>, greater<int>> minh; // 小根堆

2.3 `set` / `map` 与 `unordered_set` / `unordered_map`#

set/map：有序，复杂度通常 $O(\log n)$ 。
unordered_*：均摊 $O(1)$ ，但极端可能退化。

1
unordered_map<int, int> cnt;
2
for (int x : {1,2,2,3,3,3}) cnt[x]++;

3. 简单的板子#

3.1 前缀和#

适用：区间和查询频繁。

1
vector<int> v(n + 1), pre = v;
2
for (int i = 1; i <= n; i++)
3
{
4
    pre[i] = pre[i - 1] + v[i];
5
}

3.2 差分#

适用：区间加法更新频繁。

1
vector<int> diff(n + 2, 0);
2
// 给 [l, r] +k
3
diff[l] += k;
4
diff[r + 1] -= k;
5

6
for (int i = 1; i <= n; i++)
7
{
8
    diff[i] += diff[i - 1];
9
    // diff[i] 就是最终值
10
}

3.3 二分答案#

发现“答案满足单调性”时，优先考虑二分。

1
int l = 0, r = 1e18;
2
int ans = r;
3
while (l <= r) {
4
    auto mid = (l + r) >> 1;
5
    if (check(mid))
6
    {
7
        r = (ans = mid) - 1;
8
    }
9
    else
10
    {
11
        l = mid + 1;
12
    }
13
}

3.4 双指针#

适用：区间性质可维护（例如“窗口内不同元素数不超过 k”）。

核心套路：

右指针扩展。
不满足条件时左指针收缩。
每步更新答案。

NOTE
差不多是枚举一个更新另一个这样

3.5 BFS#

具有无优先级搜索的特性，稍加改造就变成 dijk 适用：无权图最短路、迷宫最短步数。

3.6 Dijkstra#

跟 bfs 是大致相同的，把 queue 换成 priority_queue 就行了。

要特别注意的是插入优先队列的元素是 pair<距离, 节点>，而不是 pair<节点, 距离>，因为优先级是根据距离来排序的。

3.7 DFS 与回溯#

适用：全排列、组合枚举、连通块统计。

回溯写法注意：

进入下一层前“做选择”。
回来后“撤销选择”。

TIP
全排列还可以用
1
do {
2

3
} while (next_permutation(all(a)));
值得一提的是，上面的 next_permutation 是 copilot 帮我补全的，可见我的补全依赖已经到达了一个叹为观止的地步。

3.8 并查集（DSU）#

1
 class DSU
2
{
3
private:
4
    vector<int> parent, rank, size;
5
    int count;
6

7
public:
8
    DSU(int n) : parent(n + 1), rank(n + 1, 0), size(n + 1, 1), count(n)
9
    {
10
        iota(all(parent), 0ll);
11
    }
12

13
    int find(int x)
14
    {
15
        return parent[x] == x ? x : parent[x] = find(parent[x]);
16
    }
17

18
    void merge(int i, int j)
19
    {
20
        int ri = find(i), rj = find(j);
21
        if (ri == rj)
22
        {
23
            return;
24
        }
25

26
        if (rank[ri] < rank[rj])
27
        {
28
            swap(ri, rj);
29
        }
30
        parent[rj] = ri;
31
        size[ri] += size[rj];
32
        if (rank[ri] == rank[rj])
33
        {
34
            rank[ri]++;
35
        }
36
        count--;
37
    }
38

39
    bool issame(int i, int j)
40
    {
41
        return find(i) == find(j);
42
    }
43

44
    int getsize(int x)
45
    {
46
        return size[find(x)];
47
    }
48

49
    int getgroups()
50
    {
51
        return count;
52
    }
53
};

写的简短些似乎可以

1
vector<int> parent(n + 1);
2

3
void init()
4
{
5
    iota(all(parent), 0ll);
6
}
7

8
int find(int x)
9
{
10
    return x == parent[x] ? x : parent[x] = find(parent[x]);
11
}
12

13
void merge(int i, int j)
14
{
15
    auto ri = find(i), rj = find(j);
16
    parent[ri] = rj;
17
}

剩下的 size, count 等属性自己慢慢往里面添加即可。

3.9 BIT#

适用于频繁的区间求和和单点更新。复杂度 $O(\log n)$ 。

1
class Fenwick
2
{
3
private:
4
    vector<int> tree;
5
    int n;
6
public:
7
    Fenwick(int n) : tree(n + 1, 0), n(n) {}
8

9
    int lowbit(int x)
10
    {
11
        return x & -x;
12
    }
13

14
    void update(int i, int delta)
15
    {
16
        for (; i <= n; i += lowbit(i))
17
        {
18
            tree[i] += delta;
19
        }
20
    }
21

22
    int query(int i)
23
    {
24
        int sum = 0;
25
        for (; i > 0; i -= lowbit(i))
26
        {
27
            sum += tree[i];
28
        }
29
        return sum;
30
    }
31

32
    int range_query(int l, int r)
33
    {
34
        return query(r) - query(l - 1);
35
    }
36
}

3.10 线段树#

代码量略大，基本不考虑了…

1
class SegTree
2
{
3
private:
4
    int n;
5
    vector<int> sum, ad;
6
    vector<int> v;
7

8
public:
9
    void build(int l, int r, int i)
10
    {
11
        ad[i] = 0;
12
        if (l == r)
13
        {
14
            sum[i] = v[l];
15
            return;
16
        }
17

18
        auto mid = (l + r) >> 1;
19
        build(l, mid, i << 1);
20
        build(mid + 1, r, i << 1 | 1);
21
        up(i);
22
    }
23

24
    SegTree(int n) : n(n), sum(n << 2), ad(n << 2), v(n + 1)
25
    {
26
        build(1, n, 1);
27
    };
28

29
    SegTree(vector<int> &v) : n(v.size() - 1), sum(n << 2), ad(n << 2), v(v)
30
    {
31
        build(1, n, 1);
32
    }
33

34
    void lazy(int i, int v, int len)
35
    {
36
        sum[i] += v * len;
37
        ad[i] += v;
38
    }
39

40
    void up(int i)
41
    {
42
        sum[i] = sum[i << 1] + sum[i << 1 | 1];
43
    }
44

45
    void down(int i, int ln, int rn)
46
    {
47
        if (ad[i])
48
        {
49
            lazy(i << 1, ad[i], ln);
50
            lazy(i << 1 | 1, ad[i], rn);
51
            ad[i] = 0;
52
        }
53
    }
54

55
    void update(int jobl, int jobr, int v, int l, int r, int i)
56
    {
57
        if (jobl <= l and jobr >= r)
58
        {
59
            lazy(i, v, r - l + 1);
60
            return;
61
        }
62

63
        auto mid = (l + r) >> 1;
64
        down(i, mid - l + 1, r - mid);
65

66
        if (jobl <= mid)
67
        {
68
            update(jobl, jobr, v, l, mid, i << 1);
69
        }
70
        if (jobr > mid)
71
        {
72
            update(jobl, jobr, v, mid + 1, r, i << 1 | 1);
73
        }
74
        up(i);
75
    }
76

77
    void update(int jobl, int jobr, int v)
78
    {
79
        update(jobl, jobr, v, 1, n, 1);
80
    }
81

82
    int query(int jobl, int jobr, int l, int r, int i)
83
    {
84
        if (jobl <= l and jobr >= r)
85
        {
86
            return sum[i];
87
        }
88
        auto mid = (l + r) >> 1;
89
        down(i, mid - l + 1, r - mid);
90
        int res = 0;
91
        if (jobl <= mid)
92
        {
93
            res += query(jobl, jobr, l, mid, i << 1);
94
        }
95
        if (jobr > mid)
96
        {
97
            res += query(jobl, jobr, mid + 1, r, i << 1 | 1);
98
        }
99
        return res;
100
    }
101

102
    int query(int jobl, int jobr)
103
    {
104
        return query(jobl, jobr, 1, n, 1);
105
    }
106
};

4. 动态规划入门框架#

我能做到这玩意吗

大部分 DP 题目都可以从这些角度入手：

状态是什么（dp[i]、dp[i][j]）？
转移从哪里来？
初始化和遍历顺序是什么？

5. 数学与数论高频点#

5.1 gcd \ lcm#

gcd

1
int gcd(int a, int b)
2
{
3
    return b == 0 ? a : gcd(b, a % b);
4
    // 可以记 babab
5
}

lcm

1
int lcm(int a, int b)
2
{
3
    return a / gcd(a, b) * b;
4
    // 这是为了避免乘法溢出
5
}

5.2 快速幂#

1
int ksm(int base, int exp)
2
{
3
    int ans = 1;
4
    while (exp)
5
    {
6
        if (exp & 1)
7
        {
8
            ans = ans * base % MOD;
9
        }
10
        base = base * base % MOD;
11
        exp >>= 1;
12
    }
13
    return ans;
14
}

5.3 质数筛#

1
const int N = 1e7;
2
vector<int> isprime(N + 1, 1);
3
vector<int> primes;
4
isprime[0] = isprime[1] = 0;
5

6
void init()
7
{
8
    for (int i = 2; i <= N / i; i++)
9
    {
10
        if (isprime[i])
11
        {
12
            primes.emplace_back(i);
13
            for (int j = i * i; j <= N; j += i)
14
            {
15
                isprime[j] = 0;
16
            }
17
        }
18
    }
19
}

5.4 逆元#

1
int inv(int x)
2
{
3
    return ksm(x, MOD - 2);
4
}

5.5 组合数#

1
const int N = 1e6;
2
// 预处理阶乘和逆元阶乘
3
vector<int> fact(N + 1, 1), invf(N + 1, 1);
4
void init()
5
{
6
    fact[0] = 1;
7
    for (int i = 1; i <= N; i++)
8
    {
9
        fact[i] = fact[i - 1] * i % MOD;
10
    }
11

12
    invf[N] = inv(fact[N]);
13
    for (int i = N - 1; i >= 1; i--)
14
    {
15
        invf[i] = invf[i + 1] * (i + 1) % MOD;
16
        // 可以记成 1/(i!) = 1/((i+1)!) * (i+1)
17
    }
18
}
19

20
/* C(n, k) = n! / (k! * (n - k)!)
21
当 n < k 或 k < 0 时 C(n, k) = 0
22
*/
23

24
int C(int n, int k)
25
{
26
    if (n < k or k < 0)
27
    {
28
        return 0;
29
    }
30
    return fact[n] * invf[k] % MOD * invf[n - k] % MOD;
31
}

蓝桥杯 C++ B 组常用板子

https://alisa22580.pages.dev/posts/lanqiao-cpp-b-common/

作者

alisa22580

发布于

2026-04-10

许可协议

CC BY-NC-SA 4.0

部分信息可能已经过时

蓝桥杯 C++ B 组省赛 A-H 题解（2026）

GKD -- 李跳跳的平替推荐

1. 基础中的基础#

1.1 基本板子#

1.2 常见类型范围#

1.3 排序与比较器#

2. STL 高频容器和用法#

2.1 string#

2.2 queue / priority_queue#

2.3 set / map 与 unordered_set / unordered_map#

3. 简单的板子#

3.1 前缀和#

3.2 差分#

3.3 二分答案#

3.4 双指针#

3.5 BFS#

3.6 Dijkstra#

3.7 DFS 与回溯#

3.8 并查集（DSU）#

3.9 BIT#

3.10 线段树#

4. 动态规划入门框架#

5. 数学与数论高频点#

5.1 gcd \ lcm#

5.2 快速幂#

5.3 质数筛#

5.4 逆元#

5.5 组合数#

2.1 `string`#

2.2 `queue` / `priority_queue`#

2.3 `set` / `map` 与 `unordered_set` / `unordered_map`#