当前位置：首页 > news >正文

2025 蓝桥杯省赛c++B组个人题解

news 来源：原创 2025/9/13 7:05:55

声明

本题解为退役蒻苟所写，不保证正确性，仅供参考。

花了大概2个半小时写完，感觉比去年省赛简单，难度大概等价于 codeforces dv4.5 吧

菜鸡不熟悉树上背包，调了一个多小时

题目旁边的是 cf 预测分

所有代码均以通过洛谷蓝桥杯同步题

A题

算一下弧长和半径即可得 1576

B题

正解 $2^{1022} \mod10^9+7=781448427$

C: 可分解的正整数（1000）

问题描述
判断给定正整数能否表示为长度≥3的连续整数序列之和。

输入格式

第一行：正整数N。
第二行：N个正整数A1,A2,…,AN。

输出格式
可分解的正整数数量。

样例输入

3
3 6 15

样例输出
3

评测用例规模

1≤N≤105，1≤Ai≤109。

题解

打一下表发现 106 以内所有数除了 1 以外都可以这样分解，因此答案即为非 1 的数的数量

#include <bits/stdc++.h>using namespace std;
void solve()
{int n;cin >> n;int ans = n;for (int i = 0; i < n; i++){int x;cin >> x;if (x == 1)ans--;}cout << ans << "\n";
}
int main()
{ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int _ = 1;// std::cin >> _;while (_--){solve();}return 0;
}

D: 产值调整 (1000)

问题描述
三矿山产值A,B,C每年按以下规则调整K次：

$A' = ⌊(B + C) /2 ⌋$
$B' = ⌊(A + C) /2 ⌋$
$C' = ⌊(A + B) /2 ⌋$

输入格式

第一行：测试用例数T。
每行：A,B,C,K。

输出格式
调整后的A,B,C。

样例输入

2
10 20 30 1
5 5 5 3

样例输出

25 20 15
5 5 5

评测用例规模

$1≤T≤10^5$ ， $1≤A,B,C,K≤10^9$ 。

题解

观察发现 A,B,C 都在向 $\frac{A+B+C}{3}$ 收敛，且速度很快，所以模拟一下直到三个相等即可。

#include <bits/stdc++.h>using namespace std;using ll = long long;
void solve()
{ll A, B, C, K;cin >> A >> B >> C >> K;while (K--){ll NA = (B + C) >> 1;ll NB = (A + C) >> 1;ll NC = (A + B) >> 1;A = NA, B = NB, C = NC;if (A == B && B == C)break;}cout << A << " " << B << " " << C << "\n";
}
int main()
{ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int _ = 1;std::cin >> _;while (_--){solve();}return 0;
}

E: 画展布置 (1200)

问题描述
从N幅画中选M幅排列，最小化艺术价值变化程度 $L=∑^{i=1}_{M−1}|B_{i+1}^2−B_{i}^2|$ 。

输入格式

第一行：N和M。
第二行：N个艺术价值A1,A2,…,AN。

输出格式
L的最小值。

评测用例规模

$2≤M≤N≤10^5;1≤Ai≤10^5$ 。

题解

题目要求从 N 幅画中选出 M 幅，并排成一列，使得艺术价值变化程度 $L=∑^{i=1}_{M−1}|B_{i+1}^2−B_{i}^2|$ 最小。

注意到只要将选中的画按某种顺序排列，如果能让各个相邻画作的 “平方值” 单调变化，则 $L=B_M^2−B_1^2$ ,

其中 B12 和 BM2 分别是选中画作中最小和最大的平方值。

因为对于任意一个选定的集合，无论中间顺序如何，若将它们重新排序为“平方值”递增的顺序，其变化总和必定为 $max(B_i^2)−\min(B_i^2)$

#include <bits/stdc++.h>using namespace std;using ll = long long;
void solve()
{int N, M;cin >> N >> M;vector<ll> A(N), S(N);for (int i = 0; i < N; i++){cin >> A[i];S[i] = A[i] * A[i];}sort(S.begin(), S.end());ll ans = LLONG_MAX;for (int i = 0; i + M - 1 < N; i++){ll diff = S[i + M - 1] - S[i];if (diff < ans)ans = diff;}cout << ans << "\n";
}
int main()
{ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int _ = 1;// std::cin >> _;while (_--){solve();}return 0;
}

F: 水质检测 (1600)

问题描述
在2×n河床上添加最少检测器，使所有检测器连通。

输入格式

两行：每行长度为n的字符串，#表示检测器，.表示空白。

输出格式
最少需添加的检测器数。

样例输入

.# #.....#
.# .# .#...

样例输出
5

评测用例规模

1≤n≤106

题解

贪心解不可行，正解是dp。

对于每一列 i，我们先根据输入得到该列的检测器状态。

若第 1 行第 i 个位置为 #，则该列有上检测器，对应二进制位 1， $s t a [i] ∣ = 1$
若第 2 行第 i 个位置为 #，则该列有下检测器，对应二进制位 2， $s t a [i] ∣ = 2$

我们可以在每一列中选择是否添加检测器。由于我们要求连通，我们考虑只在从最左侧出现强制检测器的列到最右侧出现强制检测器的列这一连续区间内填充检测器。

在每一列，我们可以的最终状态是：

在该列放置检测器的情况用一个二进制数表示（1 表示上有检测器，2 表示下有检测器，3 表示两行都有）；我们规定空列是不允许的，因为中断列会导致连通性断裂。因此在每一列的状态可以是 1、2 或 3。

设区间 [L, R] 为所有存在强制检测器的列的最小与最大列号。如果没有任何强制检测器，则答案为 0 。

令 $d p [i] [j]$ 表示从列 L 到列 i，将第 i 列状态设为 j 且保证前后连通时的最小添加数。状态 j 只能取 1、2、3，但必须满足与 sta[i] 匹配。

转移方程：
对于第 i 列，遍历其允许状态 j，再枚举前一列 i−1 允许的状态 k 满足 j&k≠0 ，则

$dp[i][j]=min{dp[i−1][k]+calc(j,k)}$

设状态 j 取值为 1、2、3。在列 k，若我们选择状态 j，则需要补充的检测器数量为

$c a l c (j, k) = p o p co u n t (k) - p o p co u n t (s t a [j])$

其中 popcount 是状态中 1 的个数。例如：若 sta[i] = 0，状态 1 或 2 费用为 1，状态 3 费用为 2；若 sta[i] = 1，则状态 1 费用为 0，状态 3 费用为 1；以此类推。

#include <bits/stdc++.h>using namespace std;const int inf = 0x3f3f3f3f;void solve()
{string s1, s2;cin >> s1 >> s2;int n = s1.size();vector<int> sta(n);for (int i = 0; i < n; i++){if (s1[i] == '#')sta[i] |= 1;if (s2[i] == '#')sta[i] |= 2;}int L = n, R = -1;for (int i = 0; i < n; i++){if (sta[i] != 0){L = min(L, i);R = max(R, i);}}if (R == -1){cout << 0 << "\n";return;}vector<vector<int>> dp(n, vector<int>(4, inf));auto calc = [&](int p, int t) -> int{int cnt = 0;if (t & 1)cnt++;if (t & 2)cnt++;int num = 0;if (sta[p] & 1)num++;if (sta[p] & 2)num++;return cnt - num;};auto check = [&](int x, int t) -> bool{return (t & sta[x]) == sta[x] && (t != 0);};for (int i = 1; i < 4; i++){if (check(L, i))dp[L][i] = calc(L, i);}for (int i = L + 1; i <= R; i++){for (int j = 1; j < 4; j++){if (!check(i, j))continue;int add = calc(i, j);for (int k = 1; k < 4; k++){if (!check(i - 1, k))continue;if ((k & j) == 0)continue;dp[i][j] = min(dp[i][j], dp[i - 1][k] + add);}}}int ans = inf;for (int i = 1; i < 4; i++){if (check(R, i))ans = min(ans, dp[R][i]);}cout << ans << "\n";
}
int main()
{ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int _ = 1;// std::cin >> _;while (_--){solve();}return 0;
}

G: 生产车间 (1800)

问题描述
树形结构设备网络，叶节点生产材料，根节点打包成品。调整节点使所有节点产能不超限，求根节点最大打包量。

输入格式

第一行：设备数n。
第二行：各节点权值w1,w2,…,wn。
后续n−1行：树边。

输出格式
根节点的最大成品量。

样例输入

9
9 7 3 7 1 6 2 2 7
1 2
1 3
2 4
2 5
2 6
6 7
6 8
6 9

样例输出
8

评测用例规模

$1≤n≤10^3;1≤wi≤10^3$

题解

跑一下树上背包即可，需要使用bitset优化。

对于每个节点 u，构造一个布尔数组 $f [u] [x]$ ， $f [u] [x] = t r u e$ 表示在节点 u 被保留的情况下，通过对其子树的合理保留或删除，可以使得从 u 的所有子树传上来的材料总量达到 x， x≤w[u] 。
具体的状态转移为：

叶节点：只有两种选择

删除该节点，贡献 0（即 $f [u] [0] = t r u e$ ）
保留该节点，则其实际“产出”就是 w[u] 。

内部节点：初始时没有选择任何子树，状态为 0；
遍历每个子节点 v，其返回的状态集合 g 表示了子树可能传上的材料量，利用类似于背包的思路将不同子节点的贡献累加，但总和不能超过该节点的 w[u] 。

最终，在根节点处， f[1] 为打包能力，答案即为根节点的状态数组中能达到的最大流量值

#include <bits/stdc++.h>using namespace std;
void solve()
{int n;cin >> n;vector<int> w(n + 1);for (int i = 1; i <= n; i++){cin >> w[i];}vector<vector<int>> adj(n + 1);for (int i = 1; i <= n - 1; i++){int u, v;cin >> u >> v;adj[u].push_back(v);adj[v].push_back(u);}adj[1].push_back(0);function<vector<bool>(int, int)> dfs = [&](int u, int fa) -> vector<bool>{vector<bool> f(w[u] + 1);if (adj[u].size() == 1){f[0] = true;if (w[u] <= w[u])f[w[u]] = true;return f;}f[0] = true;for (auto &v : adj[u]){if (v == fa)continue;vector<bool> g = dfs(v, u);vector<bool> h(w[u] + 1);for (int i = 0; i <= w[u]; i++){if (!f[i])continue;for (int j = 0; j < g.size(); j++){if (g[j] && i + j <= w[u])h[i + j] = true;}}f.swap(h);}return f;};vector<bool> res = dfs(1, 0);int ans = 0;for (int i = 0; i <= w[1]; i++){if (res[i])ans = max(ans, i);}cout << ans << "\n";
}int main()
{ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int _ = 1;// std::cin >> _;while (_--){solve();}return 0;
}

H: 装修报价（1600）

问题描述

老王计划装修房子，于是联系了一家装修公司。该公司有一套自动报价系统，只需用户提供 N 项装修相关费用 A1,A2,…,AN，系统便会根据这些费用生成最终的报价。

然而，当老王提交数据后，他发现这套系统的运作方式并不透明：系统只会给出一个最终报价，而不会公开任何运算过程或中间步骤。公司对此解释称，这套系统会依据某种内部算法，在每对相邻数字之间插入 +（加法）、−（减法）或 ⊕（异或）运算符，并按照特定优先级规则计算结果：异或运算优先级最高，其次是加减。

为了验证系统报价是否合理，老王决定模拟其运作方式，尝试每种可能的运算符组合，计算出所有可能出现的结果的总和。如果最终报价明显超出这个范围，他就有理由怀疑系统存在异常或误差。

现在，请你帮老王算出所有可能的结果的总和。由于该总和可能很大，你只需提供其对 109+7 取余后的结果即可。

输入格式

第一行输入一个整数 N，表示装修相关费用的项数。
第二行输入 N 个非负整数 A1,A2,…,AN，表示各项费用。

输出格式

输出一个整数，表示所有可能的总和对 109+7 取余后的结果。

示例输入

3
0 2 5

示例输出

示例说明

对于输入样例中的三个数 A=[0,2,5]，所有可能的运算符组合共有 9 种。计算结果如下：

0⊕2⊕5=7
0⊕2+5=7
0⊕2−5=−3
0+2⊕5=7
0+2+5=7
0+2−5=−3
0−2⊕5=−7
0−2+5=3
0−2−5=−7

所有结果的总和为：

7+7+(−3)+7+7+(−3)+(−7)+3+(−7)=11

11 对 109+7 取余后的值依然为 11，因此，输出结果为 11。

评测用例规模

$1≤N≤10^5,1≤A_i≤10^9$

题解

注意到：

在所有 ⊕ 连续的段内，其结果就是该段内所有数的异或值；
在相邻段之间的运算符为加或减，由于加减具有线性性质（先计算异或段，后做加减运算）可以发现，最终结果实际上为各“段”值的加权和，其中只有最左边那一段的符号“固定为 +”，而后续各段由于加减符号正负会相互抵消后求和。

具体看“分段”：

定义：设在相邻位置处如果选用非 ⊕ 运算符，则视为“断开”，形成新段。
因为每个位置独立选运算符，所以可以将所有可能的运算符组合看成对 N−1 个空位的选择，每个位置可以“接续”（即选 ⊕）或“断开”（即选加或减），而“断开”时又有 2 种符号选择。

观察发现：

若整个序列中没有断开，则只有一段，其结果为
G=A1⊕A2⊕⋯⊕AN
若第一个断开出现在位置 j（也就是说从 A1 到 Aj 连续使用 ⊕），则第一段的“段值”为
G1=A1⊕A2⊕⋯⊕Aj

而后面不论如何选择（剩余位置随意），在加减阶段由于正负相互抵消，其对总和的贡献在对所有符号取和时，只有第一段的值会“留下”。具体地：

固定第一断开出现在 j 的情况下，对于前 j−1 个间隙，必须全选 ⊕（1 种方式）；
第 j 个空位选断开，有 2 种符号选择；
对于位置 $j + 1, \dots, N - 1$ 每个空位可任意选（3 种方式），总数为 $3^{N−1−j}$ .

故满足“第一断开位置为 j "的方案数为 $2⋅3^{N−1−j}$

对于这些方案，最终计算（加减累加时）会固定地把第一段 G1 加入结果中（其他段各自正负总和为 0）。

于是，把所有方案按照是否出现断开以及第一断开的位次分情况讨论，最后所有可能最终结果的总和 S 为

无断开 $S=G_{无断开}+∑^{j=1}_{N−1}(2⋅3^{N−1−j})⋅(A_1⊕A_2⊕⋯⊕A_j)$ .

这里 $G=A_1⊕A_2⊕⋯⊕A_N$ 。

#include <bits/stdc++.h>using namespace std;using ll = long long;const ll mod = 1000000007;
ll qmi(ll x, ll k, ll p = mod)
{x %= p;ll res = 1;while (k > 0){if (k & 1)res = (res * x) % p;x = (x * x) % p;k >>= 1;}return res;
}
void solve()
{int n;cin >> n;vector<ll> a(n + 1);vector<ll> preXor(n + 1, 0);for (int i = 1; i <= n; i++){cin >> a[i];preXor[i] = preXor[i - 1] ^ a[i];}vector<ll> p3(n);p3[0] = 1;for (int i = 1; i < n; i++){p3[i] = (p3[i - 1] * 3) % mod;}ll ans = preXor[n] % mod;for (int i = 1; i < n; i++){ll t = ((2ll * p3[n - 1 - i]) % mod * preXor[i]) % mod;ans = (ans + t) % mod;}cout << (ans % mod + mod) % mod << "\n";
}
int main()
{ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int _ = 1;// std::cin >> _;while (_--){solve();}return 0;
}

2025 蓝桥杯省赛c++B组个人题解

声明本题解为退役蒻苟所写，不保证正确性，仅供参考。花了大概2个半小时写完，感觉比去年省赛简单，难度大概等价于 codeforces dv4.5 吧菜鸡不熟悉树上背包，调了一个多小时题目旁边的是 cf 预测分所有代码均以通…...

编程日记 2025/9/13 7:05:55

2025蓝桥杯算法竞赛深度突破：创新题型与高阶策略全解析

一、新型算法范式实战 1.1 元启发式算法应用（预测难度：★★★★） 题目场景：星际货物装载需在飞船载重限制下选择最优货物组合，引入遗传算法解决NP-Hard问题： 染色体编码：二进制串表示货物选择…...

编程日记 2025/9/13 7:04:03

网络流量管理-流（Flow）

1. 传统网络的问题：快递员送信模式想象你每天要寄100封信给同一个朋友，传统网络的处理方式就像一个固执的快递员： 每封信都单独处理：检查地址、规划路线、盖章、装车…即使所有信的目的地、收件人都相同，也要重复100…...

编程日记 2025/9/7 13:27:48

Spring Boot对接马来西亚股票数据源API

随着对东南亚市场的兴趣日益增长，获取马来西亚股票市场的实时和历史数据变得尤为重要。本文将指导您如何使用Spring Boot框架对接一个假定的马来西亚股票数据源API（例如，StockTV API），以便开发者能够轻松访问和处理这些…...

编程日记 2025/9/8 1:28:48

MySQL 面经

1、什么是 MySQL？ MySQL 是一个开源的关系型数据库，现在隶属于 Oracle 公司。是我们国内使用频率最高的一种数据库，我本地安装的是比较新的 8.0 版本。 1.1 怎么删除/创建一张表？ 可以使用 DROP TABLE 来删除表，使用…...

编程日记 2025/9/12 17:58:37

【Flink运行时架构】作业提交流程

本文介绍在单作业模式下Flink提交作业的具体流程，如下图所示。客户端将作业提交给YARN的RM；YARN的RM启动Flink JobManager，并将作业提交给JobMaster；JobMaster向Flink内置的RM请求slots；Flink内置的RM向YARN RM请求…...

编程日记 2025/9/13 7:04:04

【AutoTest】自动化测试工具大全（Java）

😊 如果您觉得这篇文章有用 ✔️ 的话，请给博主一个一键三连 🚀🚀🚀 吧 （点赞 🧡、关注 💛、收藏 💚）！！！您的支持 &#x…...

编程日记 2025/9/10 19:54:37

当DRAM邂逅SSD：新型“DRAM+”存储技术来了！

在当今快速发展的科技领域，数据存储的需求日益增长，对存储设备的性能和可靠性提出了更高的要求。传统DRAM以其高速度著称，但其易失性限制了应用范围；而固态硬盘SSD虽然提供非易失性存储，但在速度上远不及DRAM。为了解…...

编程日记 2025/9/11 11:05:01

【算法】快速排序

算法系列六：快速排序一、快速排序的递归探寻 1.思路 2.书写 3.搭建 3.1设计过掉不符情况（在最底层时） 3.2查验能实现基础结果（在最底层往上点时） 3.3跳转结果继续往上回搭 4.实质二、快速排序里的基准排序 …...

编程日记 2025/9/11 16:05:37

Python快速入门指南：从零开始掌握Python编程

文章目录前言一、Python环境搭建🥏1.1 安装Python1.2 验证安装1.3 选择开发工具二、Python基础语法📖2.1 第一个Python程序2.2 变量与数据类型2.3 基本运算三、Python流程控制🌈3.1 条件语句3.2 循环结构四、Python数据结构🎋…...

编程日记 2025/9/11 11:52:58

机器学习中的数学（PartⅡ）——线性代数：2.1线性方程组

概述： 现实中很多问题都可被建模为线性方程组问题，而线性代数为我们提供了解决这类问题的工具。先看两个例子： 例子1： 一家公司有n个产品，分别是，生产上述产品需要m种原料，每个产品需要其中一…...

编程日记 2025/9/9 15:56:13

检测到目标URL存在http host头攻击漏洞

漏洞描述修复措施方法一： nginx 的 default_server 指令可以定义默认的 server 去处理一些没有匹配到 server_name 的请求，如果没有显式定义，则会选取第一个定义的 server 作为 default_server。 server {listen 80 default_server; …...

编程日记 2025/9/6 18:04:38

【 Beautiful Soup (bs4) 详解】

引言 Beautiful Soup 是 Python 最流行的 HTML/XML 解析库，能够从复杂的网页文档中高效提取数据。以下是其核心知识点及示例代码。一、库简介 1. 核心模块 BeautifulSoup：主类，用于构建文档树结构Tag：表示 HTML/XML 标签的对象…...

编程日记 2025/9/12 20:38:40

Cuto壁纸 2.6.9 | 解锁所有高清精选壁纸，无广告干扰

Cuto壁纸 App 提供丰富多样的壁纸选择，涵盖动物、风景、创意及游戏动漫等类型。支持分类查找与下载，用户可轻松将心仪壁纸设为手机背景，并享受软件内置的编辑功能调整尺寸。每天更新，确保用户总能找到新鲜、满意的壁纸。大小&am…...

编程日记 2025/9/13 7:04:04

人工智能之数学基础：复矩阵

本文重点复矩阵是线性代数中以复数为元素的矩阵，是实矩阵在复数域上的自然推广。与实矩阵相比，复矩阵在数学性质、运算规则和应用场景上具有独特性，尤其在量子力学、信号处理、控制理论等领域发挥关键作用。复矩阵的定义与表示定义：复矩阵指的是元素含有复数的矩阵。…...

编程日记 2025/9/9 12:00:54

numpy初步掌握

文章目录一、前言二、概述2.1 安装2.2 基础三、数组3.1 数组创建3.1.1 从已有数据创建3.1.2 创建特殊值数组3.1.3 创建数值范围数组3.1.4 随机数组生成3.1.5 其他 3.2 数组属性四、数组操作4.1 索引/切片4.2 数组遍历4.3 修改形状4.4 更多五、数组运算5.1 常规运算5.2 广播…...

编程日记 2025/9/13 3:58:48

b站教程 using UnityEngine; using System.Collections;public class BallLauncher : MonoBehaviour {public float m_R;public NewBullet m_BulletPre;public Transform m_Target;private void Start(){StartCoroutine(Attack());}private void OnDestroy(){StopAllCoroutine…...

编程日记 2025/9/12 21:03:32

声明

A题

B题

C: 可分解的正整数 （1000）

题解

D: 产值调整 (1000)

题解

E: 画展布置 (1200)

题解

F: 水质检测 (1600)

题解

G: 生产车间 (1800)

题解

H: 装修报价 （1600）

题解

相关文章：

C: 可分解的正整数（1000）

H: 装修报价（1600）