2026 蓝桥杯省赛 C/C++ 大学 B 组题解
本文按“题意简述 → 思路分析 → 正确性说明 → 复杂度 → 参考代码”的顺序整理。
由于蓝桥杯题面较长，正文只做精炼转述，不逐字复刻题面。
目录
- A. 青春常数
- B. 双碳战略
- C. 循环右移
- D. 蓝桥竞技
- E. LQ 聚合
- F. 应急布线
- G. 理想温度
- H. 足球训练
A. 青春常数
题意简述
给定：
N = 2026202520242023
求非负整数对 (x, y) 的数量，满足：
x + y = N
0 <= x < y
该题是结果填空题。Dotcpp 题面也说明 A 题只需提交整数答案。([Dotcpp][1])
思路分析
因为 y = N - x，条件 x < y 等价于：
x < N - x
2x < N
所以：
x <= floor((N - 1) / 2)
当 N 为奇数时，合法的 x 为：
0, 1, 2, ..., floor(N / 2)
共有：
floor(N / 2) + 1
种。
本题中：
N = 2026202520242023
所以答案为：
1013101260121012
答案
1013101260121012
B. 双碳战略
题意简述
有 2026 盏灯，初始全亮。每次操作交替进行：
- 第奇数次：选择一盏灯
i，翻转i及其右侧所有灯； - 第偶数次：选择一盏灯
i，翻转i及其左侧所有灯。
对所有 2^2026 种状态，求从初始全亮到该状态的最少操作次数之和，答案对 998244353 取模。题面明确要求累加所有状态的最少操作次数。
思路分析
先把“亮/灭状态”看成与初始状态的异或差分状态。对于长度为 n 的灯串，可以观察小规模情况：
| n | 各状态最短步数分布 |
|---|---|
| 1 | C(1,0), C(1,1) |
| 2 | C(2,0), C(2,1), C(2,2) |
| 3 | C(3,0), C(3,1), C(3,2), C(3,3) |
也就是说，最短操作步数为 k 的状态数正好是：
C(n, k)
因此所有状态的最短步数和为：
sum_{k=0}^{n} k * C(n, k)
根据二项式恒等式：
sum_{k=0}^{n} k * C(n, k) = n * 2^{n - 1}
本题 n = 2026，所以答案是：
2026 * 2^2025 mod 998244353
计算得：
792264670
答案
792264670
C. 循环右移
题意简述
给定 T 组数据，每组给定 N, X, Y。求长度为 N 的数组 A 数量，满足：
- 每个元素
Ai都在[X, Y]内； - 任意连续子数组循环右移一次后，子数组不变。
题面约束中 N, X, Y 可到 10^18，T 可到 10^3。
关键观察
只看长度为 2 的连续子数组：
[Ai, A{i+1}]
循环右移一次后变为：
[A{i+1}, Ai]
若二者完全相同，则必须有：
Ai = A{i+1}
对所有相邻位置都成立，所以整个数组必须所有元素相等。
反过来，如果整个数组所有元素都相等，那么任意连续子数组循环右移后显然不变。
因此，合法数组数量就是可以选择的公共元素个数：
max(0, Y - X + 1)
复杂度
每组 O(1)。
参考代码
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int64 N, X, Y;
cin >> N >> X >> Y;
if (X > Y) cout << 0 << '\n';
else cout << Y - X + 1 << '\n';
}
return 0;
}
D. 蓝桥竞技
题意简述
有 N 种位置，第 i 种位置有 Ai 名选手。要把所有选手分成若干支队伍，每支队伍恰好 5 人，且同一队伍中 5 人必须来自 5 种不同位置。判断是否存在合法分组方案。题面要求输出 T 或 F。
思路分析
设所有选手总数为：
S = sum Ai
如果能分队，则队伍数为：
G = S / 5
显然需要：
S % 5 == 0
又因为同一种位置在同一支队伍中最多出现一次，所以第 i 种位置的 Ai 名选手必须分散到 Ai 支不同队伍中。
因此必须满足：
Ai <= G
这个条件也是充分的。
可以把问题看成：有 G 个队伍，每个队伍有 5 个槽位；每种位置最多往每个队伍放 1 人。只要总人数刚好填满 5G 个槽位，并且没有某个位置人数超过队伍数，就可以完成分配。
判定条件
S % 5 == 0
max(Ai) <= S / 5
复杂度
每组 O(N)。
参考代码
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int N;
cin >> N;
vector<int64> A(N);
int64 sum = 0, mx = 0;
for (int i = 0; i < N; i++) {
cin >> A[i];
sum += A[i];
mx = max(mx, A[i]);
}
if (sum % 5 != 0) {
cout << 'F' << '\n';
continue;
}
int64 teams = sum / 5;
if (mx <= teams) cout << 'T' << '\n';
else cout << 'F' << '\n';
}
return 0;
}
E. LQ 聚合
题意简述
给定长度为 N 的字符串，只含 L、Q、?。把所有 ? 替换成 L 或 Q 后，最大化二元组数量：
i < j, s[i] = 'L', s[j] = 'Q'
题面中 N <= 10^5。
思路分析
对于两个问号位置 i < j：
- 如果
i填Q，j填L，它们之间不能贡献LQ； - 如果交换成
i填L，j填Q，至少不会更差。
因此最优方案中，所有 ? 的填法一定可以看成：
前面一段 ? 填 L，后面一段 ? 填 Q
也就是只需要枚举分界点。
做法
先假设所有 ? 都填成 Q，计算当前的 LQ 数量。
然后从左到右扫描字符串，每遇到一个 ?，就把它从 Q 改成 L。
设：
L_before：当前位置左边已有多少个L；Q_after：当前位置右边还有多少个Q。
当一个 ? 从 Q 改成 L 时：
- 它原本作为
Q，贡献了L_before个二元组； - 改成
L后，它可以和右侧Q_after个Q组成二元组。
所以变化量为：
Q_after - L_before
不断更新答案最大值即可。
复杂度
O(N)。
参考代码
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
string s;
cin >> N >> s;
int64 cur = 0;
int64 leftL = 0;
// 初始：把所有 ? 都看成 Q
for (char c : s) {
if (c == 'L') {
leftL++;
} else {
// Q 或 ? 都作为 Q
cur += leftL;
}
}
int64 ans = cur;
int64 qAfter = 0;
for (char c : s) {
if (c == 'Q' || c == '?') qAfter++;
}
leftL = 0;
for (char c : s) {
if (c == 'L') {
leftL++;
} else if (c == 'Q') {
qAfter--;
} else {
// 当前 ? 原本是 Q，先从右侧 Q 数量中移除
qAfter--;
// 把它改成 L
cur += qAfter - leftL;
leftL++;
ans = max(ans, cur);
}
}
cout << ans << '\n';
return 0;
}
F. 应急布线
题意简述
给定 N 个点、M 条已有边。当前图可能不连通。需要加最少数量的新边使整张图连通；在加边数量最少的前提下，最小化“单个点接入的新边数量”的最大值。题面约束 N, M <= 10^5。
第一问：最少加几条边？
如果当前图有 c 个连通块，那么要把它们连成一个连通图，最少需要：
c - 1
条新边。
第二问：最大接入数最小是多少？
把每个连通块看成一个“超级点”，我们需要用 c - 1 条边把 c 个超级点连成一棵树。
这棵树的度数和为：
2(c - 1)
这些度数最终要分配到原图的 N 个点上。
如果每个点最多接入 1 条新边，那么总接入能力是 N。
若：
N >= 2(c - 1)
则最大接入数可以做到 1。
否则，至少有某个点需要接入 2 条新边。由于 c <= N，最大值不会超过 2，所以答案为 2。
特殊情况：如果 c = 1，已经连通，不需要加边，第二个答案也是 0。
总结
如果 c = 1：
输出 0 0
否则：
第一问 = c - 1
第二问 = 1, 若 N >= 2(c - 1)
= 2, 否则
复杂度
并查集 O((N + M) α(N))。
参考代码
#include <bits/stdc++.h>
using namespace std;
struct DSU {
vector<int> fa, sz;
DSU(int n = 0) {
init(n);
}
void init(int n) {
fa.resize(n + 1);
sz.assign(n + 1, 1);
iota(fa.begin(), fa.end(), 0);
}
int find(int x) {
if (fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
void unite(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return;
if (sz[x] < sz[y]) swap(x, y);
fa[y] = x;
sz[x] += sz[y];
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, M;
cin >> N >> M;
DSU dsu(N);
for (int i = 0; i < M; i++) {
int a, b;
cin >> a >> b;
dsu.unite(a, b);
}
int cnt = 0;
for (int i = 1; i <= N; i++) {
if (dsu.find(i) == i) cnt++;
}
if (cnt == 1) {
cout << "0 0\n";
} else {
int need = cnt - 1;
int mx = (N >= 2 * need ? 1 : 2);
cout << need << ' ' << mx << '\n';
}
return 0;
}
G. 理想温度
题意简述
有两个数组 A 和 B。可以选择一个连续区间 [l, r]，并给区间内所有 A[i] 加上同一个整数 k。问操作一次后，最多有多少个位置满足：
A[i] = B[i]
题面约束 n <= 2 * 10^5。
转化
令：
D[i] = B[i] - A[i]
如果不操作，已经满足的位置是：
D[i] = 0
如果选择区间并加上 k，那么区间内满足的位置变为：
D[i] = k
对于某个固定的非零 k：
- 区间内
D[i] = k的位置会变好，贡献+1； - 区间内
D[i] = 0的位置原本好，操作后变坏，贡献-1； - 其他位置不变，贡献
0。
于是问题变成：
对每个非零值
k，在一个权值数组中求最大子段和：
D[i] = k时权值为+1；D[i] = 0时权值为-1；- 否则权值为
0。
答案为：
原本 D[i] = 0 的数量 + 最大增益
如何做到 O(n log n) 或 O(n)
不能对每个 k 都扫一遍数组。
我们只处理每个非零 D[i] 出现的位置。
对同一个值 v，假设它出现的位置为：
p1, p2, ..., pt
在相邻两个出现位置之间，只需要知道有多少个 D[i] = 0，因为其他值权重为 0。
因此可以用前缀和统计零的数量，然后对每个值的出现位置做压缩版 Kadane。
复杂度
所有位置只会进入自己对应的分组一次，所以总复杂度：
O(n)
若使用 unordered_map，期望 O(n)。
参考代码
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int64> A(n + 1), B(n + 1), D(n + 1);
for (int i = 1; i <= n; i++) cin >> A[i];
for (int i = 1; i <= n; i++) cin >> B[i];
vector<int> zeroPrefix(n + 1, 0);
int base = 0;
unordered_map<int64, vector<int>> pos;
pos.reserve(n * 2);
for (int i = 1; i <= n; i++) {
D[i] = B[i] - A[i];
zeroPrefix[i] = zeroPrefix[i - 1] + (D[i] == 0);
if (D[i] == 0) {
base++;
} else {
pos[D[i]].push_back(i);
}
}
int bestGain = 0;
for (auto &kv : pos) {
const vector<int> &v = kv.second;
int cur = 0;
int last = 0;
for (int p : v) {
int zerosBetween = zeroPrefix[p - 1] - zeroPrefix[last];
cur -= zerosBetween;
if (cur < 0) cur = 0;
cur += 1;
bestGain = max(bestGain, cur);
last = p;
}
}
cout << base + bestGain << '\n';
return 0;
}
H. 足球训练
题意简述
有 n 名队员，第 i 名队员初始实力为 ai，天赋为 bi。一共训练 m 天，每天选择一名队员训练一次。若第 i 名队员训练 ki 天，则最终实力为：
ai + ki * bi
最大化所有队员最终实力的乘积，答案对 998244353 取模。题面约束为 n <= 100000，m <= 10^9，ai, bi <= 10^5。
关键贪心
如果当前第 i 名队员已经训练了 k 次，再训练一次，乘积会乘上：
(ai + (k + 1)bi) / (ai + kbi)
化简为：
1 + bi / (ai + kbi)
这个收益会随着 k 增大而递减。
因此这是一个“多条递减收益序列取前 m 大”的问题。
进一步看收益大小：
1 + bi / (ai + kbi)
比较收益大小等价于比较：
ai / bi + k
值越小，下一次训练越划算。
所以每名队员产生一条序列：
ai / bi, ai / bi + 1, ai / bi + 2, ...
我们要选出全体序列中最小的 m 项。
做法：二分阈值 + 少量堆调整
直接优先队列模拟 m 次不行，因为 m 可达 1e9。
我们二分一个实数阈值 T，统计有多少项满足：
ai / bi + k <= T
对第 i 名队员，满足条件的 k 数量为：
floor(T - ai / bi) + 1
若为负则取 0。
二分得到第 m 小附近的阈值后：
- 先把严格小于阈值的训练次数批量分配；
- 剩余不超过
O(n)次，用优先队列按下一次收益继续补齐； - 最后计算乘积取模。
注意
由于二分使用浮点数，工程实现中要留一点 eps。
堆比较下一次训练收益时，不要用浮点，直接用交叉乘法比较：
(ai + ki * bi) / bi
谁小，谁下一次更优。
复杂度
O(n log V + n log n)
其中 V 是二分精度相关常数。
参考代码
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
using i128 = __int128_t;
const int64 MOD = 998244353;
struct Player {
int id;
int64 a, b;
};
struct Node {
int id;
int64 num; // a + k * b
int64 den; // b
// priority_queue 默认大根堆，这里反过来写，让 num / den 小的排前面
bool operator < (const Node &other) const {
return (i128)num * other.den > (i128)other.num * den;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
int64 m;
cin >> n >> m;
vector<Player> p(n);
for (int i = 0; i < n; i++) {
cin >> p[i].a >> p[i].b;
p[i].id = i;
}
auto countLE = [&](long double T) {
long long total = 0;
for (auto &x : p) {
long double start = (long double)x.a / x.b;
if (T + 1e-18 < start) continue;
long double val = T - start;
long long cnt = (long long)floor(val + 1e-12) + 1;
if (cnt > 0) {
total += cnt;
if (total > m) return total;
}
}
return total;
};
long double L = 0, R = 1e18;
for (int it = 0; it < 120; it++) {
long double mid = (L + R) / 2;
if (countLE(mid) >= m) R = mid;
else L = mid;
}
long double T = R;
vector<int64> k(n, 0);
int64 used = 0;
// 先选严格小于 T 的项
for (auto &x : p) {
long double start = (long double)x.a / x.b;
long double val = T - start - 1e-10;
if (val >= 0) {
int64 cnt = (int64)floor(val) + 1;
k[x.id] = cnt;
used += cnt;
}
}
// 如果由于 eps 导致略超，回退若干次
if (used > m) {
priority_queue<Node> removeQ;
for (auto &x : p) {
if (k[x.id] > 0) {
int64 lastNum = x.a + (k[x.id] - 1) * x.b;
removeQ.push({x.id, -lastNum, x.b});
}
}
while (used > m) {
auto cur = removeQ.top();
removeQ.pop();
int id = cur.id;
k[id]--;
used--;
if (k[id] > 0) {
int64 lastNum = p[id].a + (k[id] - 1) * p[id].b;
removeQ.push({id, -lastNum, p[id].b});
}
}
}
// 剩下的用堆补齐
priority_queue<Node> pq;
for (auto &x : p) {
int id = x.id;
int64 curVal = x.a + k[id] * x.b;
pq.push({id, curVal, x.b});
}
while (used < m) {
auto cur = pq.top();
pq.pop();
int id = cur.id;
k[id]++;
used++;
int64 newVal = p[id].a + k[id] * p[id].b;
pq.push({id, newVal, p[id].b});
}
int64 ans = 1;
for (auto &x : p) {
int id = x.id;
int64 finalVal = (x.a % MOD + (k[id] % MOD) * (x.b % MOD)) % MOD;
ans = ans * finalVal % MOD;
}
cout << ans << '\n';
return 0;
}
总结
这一组题整体梯度比较明显：
| 题目 | 核心考点 |
|---|---|
| A 青春常数 | 数学计数 |
| B 双碳战略 | 状态最短步数分布、二项式恒等式 |
| C 循环右移 | 相邻元素约束 |
| D 蓝桥竞技 | 分组可行性、最大频次限制 |
| E LQ 聚合 | 贪心、枚举问号分界点 |
| F 应急布线 | 连通块、树度数分配 |
| G 理想温度 | 差值转化、最大子段和 |
| H 足球训练 | 递减边际收益、二分阈值、堆调整 |
比较容易失误的地方：
- C 题不要被“任意连续子数组”吓到，长度为
2已经足够推出全数组相等。 - D 题只看总人数不够，还必须检查
max(Ai) <= 队伍数。 - G 题操作会让原本正确的位置变错，所以
D[i] = 0要记作-1。 - H 题不能模拟 m 天训练，必须批量处理。
更多推荐
11
0- 0
已为社区贡献4条内容
所有评论(0)