第十六届蓝桥杯大赛软件赛省赛 C/C++ 大学B组

由于官方没有公布题目的数据, 所以代码仅供参考

1. 移动距离  

题目链接：P12130 [蓝桥杯 2025 省 B] 移动距离 - 洛谷

 

【问题描述】
小明初始在二维平面的原点，他想前往坐标 (233, 666)。在移动过程中，他
只能采用以下两种移动方式，并且这两种移动方式可以交替、不限次数地使用：
1. 水平向右移动，即沿着 x 轴正方向移动一定的距离。
2. 沿着一个圆心在原点 (0, 0)、以他当前位置到原点的距离为半径的圆的圆
周移动，移动方向不限（即顺时针或逆时针移动不限）。
在这种条件下，他到达目的地最少移动多少单位距离？
你只需要输出答案四舍五入到整数的结果。
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一
个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

解题思路：

1.目标点(233,666) tan a=666/233, a=arctan(666/233)=70.67, r=sqrt(233^2+666^2)=705.05

2.题目中说到只能沿x轴方向移动和沿r进行顺/逆时针旋转, 沿x轴方向移动改变r/角度a, 沿r进行顺/逆时针旋转只改变角度a

3.先沿x轴直线移动, 将r增加到目标r=705.05 ->(移动到点(705.05,0)), 沿半径为705.05的逆时针转动, 角度a变为70.67

4. 直线移动距离 x=705.05, 弧度y=r*a=705.05*70.67*(π/180)=705.05*1.233=869.67

     所以总距离为 x+y=705.05+869.67=1574,72, 四舍五入为1575, 有误差, 代码跑的话是1576

代码如下： 

#include <bits/stdc++.h>
using namespace std;
int main() {double x = 233, y = 666;double r = sqrt(x * x + y * y);double t = atan2(y, x); double d= r + r * t;cout  << round(d) << endl;return 0;
}

2. 客流量上限 

 题目链接：P12131 [蓝桥杯 2025 省 B] 客流量上限 - 洛谷

【问题描述】
一家连锁旅馆在全国拥有 2025 个分店，分别编号为 1 至 2025。随着节日
临近，总部决定为每家分店设定每日客流量的上限，分别记作 A1, A2,. . . , A2025。
这些上限并非随意分配，而是需要满足以下约束条件：
1. A1, A2,. . . , A2025 必须是 1 至 2025 的一个排列，即每个 Ai 均是 1 至 2025
之间的整数，且所有 Ai 互不相同。
2. 对于任意分店 i 和 j（1 ≤ i, j ≤ 2025，i 可等于 j），它们的客流量上限 Ai
和 Aj 的乘积不得超过 i × j +2025。
这些约束旨在平衡各分店客流压力，确保服务质量和运营稳定性。
现在，请你计算这样的分配方案究竟有多少种。由于答案可能很大，你只
需输出其对 109 +7 取余后的结果即可。
【答案提交】
这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个
整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。 

暂时没有啥思路, 我用全排列写, n一超过10/11就超时, 代码如下  

#include <bits/stdc++.h>
using namespace std;int main() {int n;cin >> n;vector<int> p(n);iota(p.begin(), p.end(), 1); //生成1-n的数int count = 0;do {bool f = true;for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (p[i] * p[j] > (i + 1) * (j + 1) + n) {f= false;break;}}if (!f) break;}if (f) count++;} while (next_permutation(p.begin(), p.end()));cout << count << endl;return 0;
}

3.  可分解的正整数

 题目链接：P12132 [蓝桥杯 2025 省 B] 可分解的正整数 - 洛谷

【问题描述】
定义一种特殊的整数序列，这种序列由连续递增的整数组成，并满足以下
条件：
1. 序列长度至少为 3。
2. 序列中的数字是连续递增的整数（即相邻元素之差为 1），可以包括正整
数、负整数或 0。
例如，[1, 2, 3]、[4, 5, 6, 7] 和 [−1, 0, 1] 是符合条件的序列，而 [1, 2]（长度不
足）和 [1, 2, 4]（不连续）不符合要求。
现给定一组包含 N 个正整数的数据 A1, A2,. . . , AN。如果某个 Ai 能够表示
为符合上述条件的连续整数序列中所有元素的和，则称 Ai 是可分解的。
请你统计这组数据中可分解的正整数的数量。

【输入格式】
输入的第一行包含一个正整数 N，表示数据的个数。
第二行包含 N 个正整数 A1, A2,. . . , AN，表示需要判断是否可分解的正整数
序列。
【输出格式】
输出一个整数，表示给定数据中可分解的正整数的数量。 

 

数据范围：

对于 30% 的评测用例，1 ≤ N ≤ 100，1 ≤ Ai ≤ 100。
对于 100% 的评测用例，1 ≤ N ≤ 105，1 ≤ Ai ≤ 109。

解题思路：举个例子, A1=3 -> 可以分解成0+1+2; A2=6 -> 可以分解成1+2+3 A3=2 -> 可以分解成-1+0+1+2....

通解：就是任意一个数x, 都可以写成-2+-1+0+1+2+x... 这个排列, 除了1是不行, 其他>=1数都可以

代码如下：

#include <bits/stdc++.h>
using namespace std;
int main() {int n, count = 0;cin >> n;for (int i = 0; i < n; ++i) {int x;cin >> x;if (x!=1) count++;}cout << count << endl;return 0;
}
//3 -> 0 1 2
//6 -> 1 2 3
//15 -> 4 5 6
//2 -> -1 0 1 2
//1 -> -1 0 1 不可以
//0 -> Ai>=1

4. 产值调整

 题目链接：P12133 [蓝桥杯 2025 省 B] 产值调整 - 洛谷

【问题描述】
偏远的小镇上，三兄弟共同经营着一家小型矿业公司 “兄弟矿业”。公司旗
下有三座矿山：金矿、银矿和铜矿，它们的初始产值分别用非负整数 A、B 和
C 表示。这些矿山的产出是小镇经济的核心，支撑着三兄弟和许多矿工家庭的
生计。
然而，各矿山的产值波动剧烈，有时金矿收益高而银矿、铜矿低迷，有时
则相反。这种不稳定性让公司收入难以预测，也常引发兄弟间的争执。为了稳
定经营，三兄弟设计了一个公平的产值调整策略，每年执行一次，每次调整时，
将根据当前的产值 A、B、C，计算新产值：
1. 金矿新产值 A′ = ⌊ B+2C ⌋；
2. 银矿新产值 B′ = ⌊A+2C ⌋；
3. 铜矿新产值 C′ = ⌊A+2 B ⌋。
其中，⌊⌋ 表示向下取整。例如，⌊3.7⌋ =3，⌊5.2⌋ =5。
计算出 A′、B′、C′ 后，同时更新：A 变为 A′，B 变为 B′，C 变为 C′，作
为下一年调整的基础。
三兄弟认为这个方法能平衡产值波动，于是计划连续执行 K 次调整。现
在，请你帮他们计算，经过 K 次调整后，金矿、银矿和铜矿的产值分别是多
少。

【输入格式】
输入的第一行包含一个整数 T ，表示测试用例的数量。
接下来的 T 行，每行包含四个整数 A，B，C，K，分别表示金矿、银矿和
铜矿的初始产值，以及需要执行的调整次数。

【输出格式】
对于每个测试用例，输出一行，包含三个整数，表示经过 K 次调整后金
矿、银矿和铜矿的产值，用空格分隔。

 

【评测用例规模与约定】
对于 30% 的评测用例，1 ≤ T ≤ 100，1 ≤ A, B, C, K ≤ 105。
对于 100% 的评测用例，1 ≤ T ≤ 105，1 ≤ A, B, C, K ≤ 109。

 解题思路：题目中让你怎么调整, 你就怎么调整，eg: A1->(B+2*C)/2

代码如下：

#include <bits/stdc++.h>
using namespace std;
int main() {int T;cin >> T;while (T--) {int a, b, c;long long k;cin >> a >> b >> c >> k;for (long long i = 0; i < k; ++i) {int na = (b + c) / 2;int nb = (a + c) / 2;int nc = (a + b) / 2;if (na == a && nb == b && nc == c) {break;}a = na;b = nb;c = nc;}cout << a << " " << b << " " << c << endl;}return 0;
}

 5.画展布置

 题目链接：P12134 [蓝桥杯 2025 省 B] 画展布置 - 洛谷

画展策展人小蓝和助理小桥为即将举办的画展准备了 N 幅画作，其艺术价
值分别为 A1, A2,. . . , AN。他们需要从这 N 幅画中挑选 M 幅，并按照一定顺序
布置在展厅的 M 个位置上。如果随意挑选和排列，艺术价值的变化可能会过于
突兀，导致观众的观展体验不够流畅。
为了优化布置，他们查阅了《画展布置指南》。指南指出，理想的画展应使
观众在欣赏画作时，艺术价值的过渡尽量平缓。指南建议，选择并排列 M 幅
画，应使艺术价值的变化程度通过一个数值 L 来衡量，且该值越小越好。数值
L 的定义为：
L =M∑−1i=1|B2i+1 − B2i |
其中 Bi 表示展厅第 i 个位置上画作的艺术价值。
现在，他们希望通过精心挑选和排列这 M 幅画作，使 L 达到最小值，以
提升画展的整体协调性。请你帮他们计算出这个最小值是多少。
【输入格式】
输入共两行。
第一行包含两个正整数 N 和 M，分别表示画作的总数和需要挑选的画作数
量。
第二行包含 N 个正整数 A1, A2,. . . , AN，表示每幅画作的艺术价值。
【输出格式】
输出一个整数，表示 L 的最小值。

数据范围：

对于 40% 的评测用例，2 ≤ M ≤ N ≤ 103，1 ≤ Ai ≤ 103。
对于 100% 的评测用例，2 ≤ M ≤ N ≤ 105，1 ≤ Ai ≤ 105。

 1.题意解释从N副画中选出M副画, 然后计算出M对应的L, 输出L的最小值

题目中说的是尽量让M个数的平方差的绝对值之和的最小值

2. 先排序不就得了, 例如, 1 7 8 9比1 9 8 7更平滑啊

3. 平方后选连续的元素更优, 

所以我们只需要在[平方 + 排序]后的序列上找一段长度为 M 的子序列，使得相邻差的绝对值之和最小，这不就是滑窗吗, 去除最left侧的元素， 增加下一个元素，同时维护一个和最小值

代码如下： 

#include <bits/stdc++.h>
using namespace std;
int main() {int N, M;cin >> N >> M;vector<long long> A(N);for (int i = 0; i < N; ++i) {int x;cin >> x;A[i] = 1LL * x * x;  }sort(A.begin(), A.end());vector<long long> diff(N - 1); for (int i = 0; i < N - 1; i++) {diff[i] = abs(A[i + 1] - A[i]);}long long L = 0;for (int i = 0; i < M - 1; i++) {L += diff[i];}long long minL = L;for (int i = 1; i <= N - M; i++) {L = L - diff[i - 1] + diff[i + M - 2];minL = min(minL, L);}cout << minL << endl;return 0;
}

6. 水质检测

题目链接：P12135 [蓝桥杯 2025 省 B] 水质检测 - 洛谷

【问题描述】
小明需要在一条 2 × n 的河床上铺设水质检测器。在他铺设之前，河床上已
经存在一些检测器。如果两个检测器上下或者左右相邻，那么这两个检测器就
是互相连通的。连通具有传递性，即如果 A 和 B 连通，B 和 C 连通，那么 A
和 C 也连通。现在他需要在河床上增加铺设一些检测器使得所有的检测器都互
相连通。他想知道最少需要增加铺设多少个检测器？
【输入格式】
输入共两行，表示一个 2 × n 的河床。
每行一个长度为 n 的字符串，仅包含 ‘#’ 和 ‘.’，其中 ‘#’ 表示已经存在的
检测器，‘.’ 表示空白。
【输出格式】
输出共 1 行，一个整数表示答案。

 让字符串a和字符串b进行连通

#include <bits/stdc++.h>
using namespace std;
int main(){string a, b;cin >> a >> b;int ans = 0;int c = -1, d = -1;for(int i = 0; i < a.size(); i++) {if(a[i] == '.' && b[i] == '.') continue;if(c != -1) {ans += i - c - 1;}if(a[i] == '#' && b[i] == '#') {d = 3;} else if(a[i] == '#' && b[i] == '.') {if(d == 2) {ans++;d = 3;} else {d = 1;}} else if(a[i] == '.' && b[i] == '#') {if(d == 1) {ans++;d = 3;} else {d = 2;}}c = i;}cout << ans << endl;
}

7. 生产车间

 题目链接：P12136 [蓝桥杯 2025 省 B] 生产车间 - 洛谷

【问题描述】
小明正在改造一个生产车间的生产流水线。这个车间共有 n 台设备，构成
以 1 为根结点的一棵树，结点 i 有权值 wi。其中叶节点的权值 wi 表示每单位时
间将产出 wi 单位的材料并送往父结点，根结点的权值 wi 表示每单位时间内能
打包多少单位成品，其他结点的权值 wi 表示每单位时间最多能加工 wi 单位的
材料并送往父结点。
由于当前生产线中某些结点存在产能不够的问题导致生产线无法正常运行，
即存在某些结点每单位时间收到的材料超过了当前结点的加工能力上限。小明
计划删除一些结点使得所有结点都能正常运行。他想知道删除一些结点后根结
点每单位时间内最多能打包多少单位的成品？
【输入格式】
输入共 n +1 行。
第一行为一个正整数 n。
第二行为 n 个由空格分开的正整数 w1, w2,..., wn。
后面 n − 1 行，每行两个整数表示树上的一条边连接的两个结点。
【输出格式】
输出共一行，一个整数代表答案。

如果你直接暴力dfs的话, 应该是能过掉不少的样例的, 但是要, 贪心选择能贡献最大但不超容量的子节点，我在洛谷测的时候过了百分70, 比赛的时候你写这个没问题, 尽量cheat更多的分,。下面我提供的是树形DP的优化代码。

#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> w;
vector<vector<int>> tree;
bitset<1001> dfs(int u, int parent) {bool isLeaf = true;for (int v : tree[u]) {if (v != parent) { isLeaf = false; break; }}if (isLeaf) {bitset<1001> B;B.reset();B[0] = 1;B[w[u]] = 1;return B;}int cap = w[u];bitset<1001> dp_child;dp_child.reset();dp_child[0] = 1;for (int v : tree[u]) {if (v == parent) continue;auto Bv = dfs(v, u);bitset<1001> next;next.reset();for (int x = Bv._Find_first(); x <= cap; x = Bv._Find_next(x)) {next |= (dp_child << x);}dp_child = next;}bitset<1001> Bu;Bu.reset();Bu[0] = 1;for (int x = dp_child._Find_first(); x <= cap; x = dp_child._Find_next(x)) {Bu[x] = 1; }return Bu;
}int main(){cin >> n;w.resize(n+1);for (int i = 1; i <= n; ++i) {cin >> w[i];}tree.resize(n+1, {});for (int i = 0; i < n-1; ++i) {int u,v;cin >> u >> v;tree[u].push_back(v);tree[v].push_back(u);}auto Broot = dfs(1, 0);int ans = 0;for (int x = Broot._Find_first(); x <= w[1]; x = Broot._Find_next(x)) {ans = x;  }cout << ans << endl;return 0;
}

8. 装修报价

 题目链接：P12137 [蓝桥杯 2025 省 B] 装修报价 - 洛谷

【问题描述】
老王计划装修房子，于是联系了一家装修公司。该公司有一套自动报价系
统，只需用户提供 N 项装修相关费用 A1, A2,. . . , AN，系统便会根据这些费用生
成最终的报价。
然而，当老王提交数据后，他发现这套系统的运作方式并不透明：系统只
会给出一个最终报价，而不会公开任何运算过程或中间步骤。
公司对此解释称，这套系统会依据某种内部算法，在每对相邻数字之间插
入 +（加法）、−（减法）或 ⊕（异或）运算符，并按照特定优先级规则计算结
果：异或运算优先级最高，其次是加减。但由于保密性，具体的运算符组合以
及中间过程都不会对外公开。
为了验证系统报价是否合理，老王决定模拟其运作方式，尝试每种可能的
运算符组合，计算出所有可能出现的结果的总和。如果最终报价明显超出这个
范围，他就有理由怀疑系统存在异常或误差。只是老王年事已高，手动计算颇
为吃力，便向你求助。
现在，请你帮老王算出所有可能的结果的总和。由于该总和可能很大，你
只需提供其对 10^9 +7 取余后的结果即可。
【输入格式】
第一行输入一个整数 N，表示装修相关费用的项数。
第二行输入 N 个非负整数 A1, A2,. . . , AN，表示各项费用。
【输出格式】
输出一个整数，表示所有可能的总和对 10^9 +7 取余后的结果。

 异或和的优先级最高, 异或和在后面的, 有+AxorB/-AxorB 直接抵消了，所以对答案产生贡献的，只有一段前缀的异或, 因此我们枚举前缀异或的长度 i， 具体的代码如下。

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
long long qPow(long long a, long long b, long long p) {long long ans = 1;a %= p;while(b) {if(b & 1) ans = (ans * a) % p;b >>= 1;a = (a * a) % p;}return ans % p;
}
int main(){int n;cin >> n;int S = 0;int ans = 0;for(int i = 1, x; i <= n; i++) {cin >> x;S ^= x;if(i < n) {ans += S * 2 * qPow(3LL, n - i - 1, mod) % mod;} else {ans += S;}ans %= mod;}cout << ans << endl;return 0;
}

填空好难, 如果这篇文章流量大的话, 我会继续补充更详细的实现思路。

感谢大家的点赞和关注，你们的支持是我创作的动力！