第17届蓝桥杯省赛C/C++ B组题解

A-青春常数#

除以 2 即可。注意由于 x 可以取到 0，所以要 +1

Code#

1
// Problem: Luogu P16232
2
// Contest: Luogu
3
// URL: https://www.luogu.com.cn/problem/P16232
4
// Time: 2026-04-12 20:29:57
5
#include <iostream>
6
using namespace std;
7

8
int main()
9
{
10
    cout << "1013101260121012" << endl;
11
    return 0;
12
}

B-双碳战略#

首先考虑打表来观察规律，用一个数组来存储状态，使用 bfs 来打表，每种状态对应一个数组。

打表代码如下：

1
// Problem: Luogu P16233
2
// Contest: Luogu
3
// URL: https://www.luogu.com.cn/problem/P16233
4
// Time: 2026-04-12 20:32:24
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
int n;
9
queue<vector<int>> q;
10
map<vector<int>, int> mp;
11

12
int main()
13
{
14
    cin >> n;
15
    vector<int> s(n);
16
    q.push(s);
17
    mp[s] = 0;
18

19
    while (q.size())
20
    {
21
        auto u = q.front();
22
        q.pop();
23

24
        for (int i = 0; i < n; i++) // 选定任意一个位置
25
        {
26
            auto v = u; // 下一个状态
27
            if (mp[u] % 2 == 0) // 上一次操作的步数是偶数，则当前是奇数步
28
            {
29
                for (int j = i; j < n; j++)
30
                    v[j] ^= 1; // 反转
31
            }
32

33
            else // 上一次操作的步数是奇数，则当前是偶数步
34
            {
35
                for (int j = 0; j <= i; j++)
36
                    v[j] ^= 1; // 反转
37
            }
38

39
            if (!mp.count(v))
40
            {
41
                q.push(v);
42
                mp[v] = mp[u] + 1;
43
            }
44
        }
45
    }
46

47
    int res = 0;
48
    for (auto &[v, dist]: mp)
49
    {
50
        for (auto &x: v)
51
            cerr << x << " ";
52
        cerr << "步数：" << dist << endl;
53
        res += dist;
54
    }
55
    cout << res << endl;
56
    return 0;
57
}

n = 3 时，结果为 0 1 3 1 2 2 2 1，总数为 12

0 有 1 个，1 有 3 个，2 有 3 个，3 有 1 个

n = 4 时，结果为 0 1 3 1 3 4 3 1 2 2 3 2 2 2 2 1，总数为 32

0 有 1 个，1 有 4 个，2 有 6 个，3 有 4 个，4 有 1 个

观察到规律是杨辉三角，下面考虑每个数对答案的贡献。

以 n = 4 的情况为例，显然 1 的贡献是 1*4，2 的贡献是 2*6，以此类推

则答案为 $\sum_{i=0}^{n} i \cdot C_n^i$ ，其中 n = 2026

根据组合数学恒等式 $\sum_{k=0}^{n} k \binom{n}{k} = n \cdot 2^{n-1}$ ，答案可进一步简化为 $2026 \cdot 2^{2025} \pmod{998244353}$

最终解得答案为 $792264670$

1
// Problem: Luogu P16233
2
// Contest: Luogu
3
// URL: https://www.luogu.com.cn/problem/P16233
4
// Time: 2026-04-12 20:32:24
5
#include <bits/stdc++.h>
6
using namespace std;
7
const int mod = 998244353;
8
typedef long long LL;
9

10
LL qmi(LL a, LL k)
11
{
12
    LL res = 1;
13
    while (k)
14
    {
15
        if (k & 1)
16
            res = res * a % mod;
17
        a = a * a % mod;
18
        k >>= 1;
19
    }
20
    return res;
21
}
22

23
void solve()
24
{
25
    int n = 2026;
26
    vector<LL> f(n + 1, 1), g(n + 1, 1);
27

28
    for (int i = 1; i <= n; i++)
29
    {
30
        f[i] = f[i - 1] * i % mod;
31
        g[i] = g[i - 1] * qmi(i, mod - 2) % mod;
32
    }
33

34
    int res = 0;
35
    for (int i = 0; i <= n; i++)
36
    {
37
        LL C = f[n] * g[i] % mod * g[n - i] % mod;
38
        res = (res + C * i % mod) % mod;
39
    }
40
    cout << res << endl;
41
}
42

43

44
int main()
45
{
46
    // solve();
47
    LL res = (2026 * qmi(2, 2025) % mod) % mod;
48
    cout << res << endl;
49
    return 0;
50
}

C-循环右移#

抽象成一个比大小问题，一个数组满足“循环右移”的条件，当且仅当所有数都相同。

Code#

1
// Problem: Luogu P16234
2
// Contest: Luogu
3
// URL: https://www.luogu.com.cn/problem/P16234
4
// Time: 2026-04-12 21:19:54
5
#include <bits/stdc++.h>
6
using namespace std;
7
typedef long long LL;
8
void solve()
9
{
10
    LL n, x, y;
11
    cin >> n >> x >> y;
12

13
    LL res = y - x + 1;
14
    if (res <= 0)
15
        cout << 0 << '\n';
16
    else
17
        cout << res << '\n';
18
}
19

20
int main()
21
{
22
    int T;
23
    cin >> T;
24
    while (T--)
25
        solve();
26
    return 0;
27
}

D-蓝桥竞技#

首先发现 sum % 5 必须等于 0，且一定要有 sum / 5 支队伍。

我们发现，假如一共有 3 支队伍，那么每个位置上不能超过 3 个人，否则没办法分配

则我们得到了必要条件 1： $\sum a_i \bmod 5 = 0$

必要条件 2： $\forall i,\ a_i \leqslant \frac{\sum a_i}{5}$ ，也就是说给定数组的最大值不能大过 sum / 5

根据摩尔投票算法，可以推导出一个结论：必要条件 1 + 必要条件 2 -> 充要条件

Code#

1
// Problem: Luogu P16235
2
// Contest: Luogu
3
// URL: https://www.luogu.com.cn/problem/P16235
4
// Time: 2026-04-12 21:20:41
5
#include <bits/stdc++.h>
6
using namespace std;
7
typedef long long LL;
8
void solve()
9
{
10
    int n;
11
    cin >> n;
12
    LL mx = 0, sum = 0;
13
    for (int i = 0; i < n; i++)
14
    {
15
        LL x;
16
        cin >> x;
17
        sum += x;
18
        mx = max(mx, x);
19
    }
20

21
    if (sum % 5 || (sum / 5 < mx))
22
        cout << "F" << endl;
23
    else
24
        cout << "T" << endl;
25
}
26

27
int main()
28
{
29
    int T;
30
    cin >> T;
31
    while (T--)
32
        solve();
33
    return 0;
34
}

E-LQ 聚合#

做法 1-贪心 + 讨论#

根据贪心，我们把靠前的问号尽可能改成 L，靠后的问号尽可能改成 Q

也就是说，存在一个最优的分界点，在分界点前面的问号都改成 L，后面都改成 Q

字符串总长为 n，可以 $O(n)$ 的枚举每一个位置作分界点

下面考虑分界点左右的贡献计算。

Code#

1
// Problem: Luogu P16236
2
// Contest: Luogu
3
// URL: https://www.luogu.com.cn/problem/P16236
4
// Time: 2026-04-12 21:43:17
5
#include <bits/stdc++.h>
6
using namespace std;
7
typedef long long LL;
8

9
int main()
10
{
11
    int n;
12
    string s;
13
    cin >> n >> s;
14

15
    s = " " + s;
16
    vector<int> L(n + 1), Q(n + 1), X(n + 1);
17
    vector<LL> sq(n + 1), sl(n + 2);
18
    // sq统计左半部分的?Q，sl统计右半部分的L?
19

20
    int sum = 0; // 贡献6
21
    for (int i = 1; i <= n; i++)
22
    {
23
        // 预处理区间数量
24
        L[i] = L[i - 1];
25
        Q[i] = Q[i - 1];
26
        X[i] = X[i - 1];
27
        sq[i] = sq[i - 1];
28

29
        if (s[i] == 'L')
30
            L[i]++;
31
        else if (s[i] == 'Q')
32
        {
33
            Q[i]++;
34
            sq[i] += X[i];
35
            sum += L[i];
36
        }
37
        else
38
            X[i]++;
39
    }
40

41
    for (int i = n; i > 0; i--)
42
    {
43
        sl[i] = sl[i + 1];
44
        if (s[i] == 'L')
45
            sl[i] += (X[n] - X[i]);
46
    }
47

48
    LL res = 0;
49

50
    for (int i = 0; i <= n; i++)
51
    {
52
        LL add = 0;
53
        add += 1LL * X[i] * (X[n] - X[i]); // 左问号乘右问号
54
        add += 1LL * X[i] * (Q[n] - Q[i]); // 左问号乘右Q
55
        add += 1LL * L[i] * (X[n] - X[i]); // 左L乘左问号
56
        add += 1LL * sq[i] + sl[i + 1]; // 左L和左？and 右？和右Q
57
        res = max(res, add);
58
    }
59
    cout << res + sum << endl;
60
    return 0;
61
}

做法 2-DP#

根据题意，对于每个 Q，它前面有多少个 L，就做出多少的贡献，所以问题可以转化为：在每个？处决定填 L 还是填 Q，使得所有 Q 前面的 L 总数之和最大。

我们可以采取简单 DP 的思维，因为 L、Q 的选择只会影响后续的值，所以只需要逐步递推，维护三个变量去记录它们在递推中的数量变化即可。

状态表示（以单变量的形式）：

$f_i$ ：处理完前 $i$ 个字符后，当前已获得的最大 LQ 聚合数。
$l$ ：当前已经确定（包括已经决定填 L）的 L 的个数。
$q$ ：尚未扫描到的原始 Q 的数量。
$r$ ：尚未扫描到的 ? 的数量。

状态转移：

遇到 L 时： $l = l + 1, f_i = f_{i -1 }$ （最大值不变）
遇到 Q 时： $q=q-1,f_i=f_{i-1}+l$ （当前的 Q 与前面所有的 L 形成 $l$ 个新对）
遇到 ? 时：先令 $r=r-1$ （? 被消耗一个），然后比较选择 L 时未来最多能匹配的 Q 数量（ $r+q$ ）与当前选择 Q 时能和先前已有的 L 能产生的匹配数量（ $l$ ）：
- 若 $r+q > l$ ，则当前把 ? 变成 L 更优，即 $l = l + 1, f_i = f_{i -1 }$
- 否则，当前把 ? 变成 Q 更优，即 $f_i=f_{i-1}+l$

Code#

1
// Problem: Luogu P16236
2
// Contest: Luogu
3
// URL: https://www.luogu.com.cn/problem/P16236
4
// Time: 2026-04-16 22:55:44
5
#include <iostream>
6
using namespace std;
7
typedef long long LL;
8
const int N = 1e5 + 10;
9
int a[N];
10
LL f[N];
11

12
int main()
13
{
14
    int n;
15
    cin >> n;
16

17
    LL l = 0, q = 0, r = 0;
18

19
    for (int i = 1; i <= n; i++)
20
    {
21
        char x;
22
        cin >> x;
23
        if (x == '?')
24
            a[i] = 2, r++;
25
        if (x == 'L')
26
            a[i] = 0;
27
        if (x == 'Q')
28
            a[i] = 1, q++;
29
    }
30

31
    for (int i = 1; i <= n; i++)
32
    {
33
        if (a[i] == 0) // L
34
        {
35
            l++;
36
            f[i] = f[i - 1];
37
        }
38
        else if (a[i] == 1) // Q
39
        {
40
            q--;
41
            f[i] = f[i - 1] + l;
42
        }
43
        else // ?
44
        {
45
            r--;
46
            if (r + q > l)
47
            {
48
                l++;
49
                f[i] = f[i - 1];
50
            }
51
            else
52
            {
53
                f[i] = f[i - 1] + l;
54
            }
55
        }
56
    }
57
    cout << f[n] << endl;
58
    return 0;
59
}

F-应急布线#

考虑使用并查集来解决联通块问题。一开始会形成若干连通块，题目就是求把若干连通块变成一个的最小花费。那么答案一定是连通块的数量减一。

注意到每次连边会将两个机子连上，一共要连 cnt 次，n 台机器总共连 2 * cnt 次，最好的情况是给 n 个机器均摊，答案为 $\lceil \frac{2cnt}{n} \rceil$

Code#

1
// Problem: Luogu P16237
2
// Contest: Luogu
3
// URL: https://www.luogu.com.cn/problem/P16237
4
// Time: 2026-04-14 19:31:29
5
#include <bits/stdc++.h>
6
using namespace std;
7
const int N = 1e5 + 10;
8

9
int n, m, cnt;
10
int p[N];
11

12
int find(int x)
13
{
14
    if (p[x] != x)
15
        p[x] = find(p[x]);
16
    return p[x];
17
}
18

19
int main()
20
{
21
    cin >> n >> m;
22

23
    for (int i = 1; i <= n; i++)
24
        p[i] = i;
25

26
    while (m--)
27
    {
28
        int u, v;
29
        cin >> u >> v;
30
        p[find(u)] = find(v);
31
    }
32

33
    for (int i = 1; i <= n; i++)
34
        if (find(i) == i)
35
            cnt++;
36

37
    cout << --cnt << " " << ceil(2.0 * cnt / n);
38
    return 0;
39
}

G-理想温度#

思路#

Step1 - 转化题意#

首先，定义每个传感器的初始差值 $D_i = B_i - A_i$

若 $D_i = 0$ ，说明开始时已满足要求。
如果我们对区间 $[l, r]$ 补偿温度 $k$ ，那么对于区间内的传感器 $i$ ，其温度变为 $A_i + k$ 。它达到理想温度的条件是 $A_i + k = B_i$ ，即 $k = B_i - A_i = D_i$ 。

对于一次操作（区间 $[l, r]$ ，补偿值 $k$ ），最终达到理想温度的传感器数量可以分为两部分：

区间外： 原本就满足 $D_i = 0$ 的传感器数量。

区间内： 满足 $D_i = k$ 的传感器数量。

当我们选择一个区间时，原本在这个区间里的 0 会因为加上 k 而产生损失。

为了最大化最终数量，我们需要找一个 $k$ 和一个区间 $[l, r]$ ，使得 (区间内 k 的个数) - (区间内 0 的个数) 最大。

设一开始的 $D_i$ 中有 $st$ 个 0，则最终结果为** st + (区间内 k 的个数) - (区间内 0 的个数) **

Step2 - 最大子段和 DP 求解#

我们可以把这个问题看作：对于每一个出现的非零差值 $k$ ，将数组中等于 $k$ 的位置看作 $+1$ ，等于 $0$ 的位置看作 $-1$ ，其余位置看作 $0$ 。我们要在这个序列中找一个最大子段和。

预处理前缀和：
1. 计算所有的 $D_i = B_i - A_i$
2. 统计 $D_i=0$ 的位置，并记录前缀和 $s[i]$ 表示前 $i$ 个元素中有多少个 0
3. 用一个哈希表记录每个非零值 $k$ 出现的所有下标
贪心计算：

对于每一个唯一的非零值 $k$ ，假设它出现的下标序列为 $p_1, p_2, \dots, p_m$ ：

我们要最大化： $(j - i + 1) - (Z[p_j] - Z[p_i - 1])$

这里 (j - i + 1) 是区间内 k 的个数， $Z[p_j] - Z[p_i - 1]$ 是区间内 0 的个数。

可得公式 $\text{Gain} = (j - Z[p_j]) - (i - 1 - Z[p_i - 1])$

对于固定的 $k$ ，我们只需要遍历下标序列，维护一个 $(i - 1 - Z[p_i - 1])$ 的最小值，即可在 $O(m)$ 时间内算出该 $k$ 值的最大增益。

Code#

1
// Problem: Luogu P16238
2
// Contest: Luogu
3
// URL: https://www.luogu.com.cn/problem/P16238
4
// Time: 2026-04-14 23:38:15
5
#include <bits/stdc++.h>
6
using namespace std;
7
typedef long long LL;
8

9
int main()
10
{
11
    ios::sync_with_stdio(false);
12
    cin.tie(0);
13

14
    int n;
15
    cin >> n;
16

17
    vector<LL> a(n + 1), b(n + 1), d(n + 1);
18
    vector<int> s(n + 1, 0);
19

20
    int st = 0;
21

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

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

28
    map<LL, vector<int>> mp;
29

30
    for (int i = 1; i <= n; i++)
31
    {
32
        d[i] = b[i] - a[i];
33
        s[i] = s[i - 1] + (d[i] == 0 ? 1 : 0);
34

35
        if (d[i] == 0)
36
            st++;
37
        else
38
            mp[d[i]].push_back(i);
39
    }
40

41
    int mxres = 0;
42

43
    for (auto const &[v, pos]: mp)
44
    {
45
        int mnval = 0;
46

47
        for (int j = 0; j < pos.size(); j++)
48
        {
49
            int k = pos[j];
50
            int curv = j + 1 - s[k], curu = j - s[k - 1];
51

52
            mnval = min(mnval, curu);
53
            mxres = max(mxres, curv - mnval);
54
        }
55
    }
56

57
    cout << st + mxres << endl;
58
    return 0;
59
}

H-足球训练#

思路#

Step1-贪心#

假设我们给第 $i$ 个队员分配一天的训练时间，这个分配操作对整体乘积的影响（也就是增幅）为

\frac{a_i + (k_i + 1)b_i}{a_i + k_i b_i} = 1 + \frac{b_i}{a_i + k_i b_i} = 1 + \frac{1}{\frac{a_i}{b_i} + k_i}

为了让总乘积最大，我们每次都应该选增幅最大的队员。观察上式，要使增幅最大，就必须让分母最小。

也就是说，我们按照 $\frac{a_i}{b_i} + k_i$ 从小到大贪心。

Step2-模拟（60pts）#

我们考虑直接模拟，观察到对于 60% 的数据有 $m \leqslant 3000$ ，那么可以用一个优先队列直接模拟。

Code#

1
// Problem: Luogu P16239
2
// Contest: Luogu
3
// URL: https://www.luogu.com.cn/problem/P16239
4
// Time: 2026-04-12 22:42:32
5
#include <bits/stdc++.h>
6
using namespace std;
7
typedef long long LL;
8
const LL MOD = 998244353;
9

10
struct Player
11
{
12
    LL a, b;
13
    LL k; // 已分配的训练天数
14

15
    // 增幅 b / (a + kb) 最大的排在堆顶
16
    bool operator<(const Player &other) const
17
    {
18
        // 交叉相乘，代替除法比较
19
        LL left = b * (other.a + other.k * other.b);
20
        LL right = other.b * (a + k * b);
21

22
        return left < right;
23
    }
24
};
25

26
int main()
27
{
28
    ios::sync_with_stdio(false);
29
    cin.tie(0);
30

31
    int n;
32
    LL m;
33
    cin >> n >> m;
34

35
    priority_queue<Player> pq;
36
    for (int i = 0; i < n; i++)
37
    {
38
        LL a, b;
39
        cin >> a >> b;
40
        pq.push({a, b, 0}); // 初始天数 k = 0
41
    }
42

43
    for (int i = 0; i < m; i++)
44
    {
45
        // 拿出当前增幅最大的队员
46
        Player top = pq.top();
47
        pq.pop();
48

49
        top.k++;
50
        pq.push(top);
51
    }
52

53
    LL ans = 1;
54
    while (!pq.empty())
55
    {
56
        Player p = pq.top();
57
        pq.pop();
58

59
        LL strength = (p.a + p.k * p.b) % MOD;
60
        ans = (ans * strength) % MOD;
61
    }
62

63
    cout << ans << "\n";
64
    return 0;
65
}

Step3-二分答案（100pts）#

既然我们每次都是挑选 $\frac{a_i}{b_i} + k_i$ 最小的队员不断往上“填平”，这非常像一个“注水”的过程。我们可以二分最终的水面高度（阈值 V）。

对于一个阈值 V：如果某个队员当前的 $\frac{a_i}{b_i} + k_i \leqslant V$ ，那么他就需要被训练，训练天数为满足 $\frac{a_i}{b_i} + k_i - 1 \le V$ 的最大 $k_i$ 值，即 $k_i = \lfloor V - \frac{a_i}{b_i} \rfloor + 1, V \ge \frac{a_i}{b_i}$ 。

综上，我们可以二分找到一个最小的阈值 V，使得所有队员需要的训练天数总和 $\sum k_i \ge m$