2025年第十六届蓝桥杯大赛软件赛C/C++大学B组题解

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



试题A: 移动间隔

问题描述

小明初始在二维平面的原点，他想前往坐标(233,666)。在移动过程中，他只能采用以下两种移动方式，并且这两种移动方式可以瓜代、不限次数地使用：

• 水平向右移动，即沿着x轴正方向移动肯定的间隔。
  
• 沿着一个圆心在原点(0,0)、以他当前位置到原点的间隔为半径的圆的圆周移动，移动方向不限（即顺时针或逆时针移动不限）。
  

在这种条件下，他到达目的地最少移动多少单元间隔？你只需要输出答案四舍五入到整数的效果。
解题思路

这个问题可以转化为：如何从原点到达目标点，使得路径长度最小。
首先，我们可以观察到，如果目标点在x轴上，那么直接水平向右移动是最优的。
对于一样寻常情况，我们可以分两步走：

• 先沿着x轴正方向移动到点(r,0)，其中r是目标点到原点的间隔
  
• 然后沿着半径为r的圆弧移动到目标点
  

目标点(233,666)到原点的间隔为：
r = √(233² + 666²) = √(54289 + 443556) = √497845 ≈ 705.58
第一步移动间隔为r = 705.58
第二步需要盘算圆弧长度。目标点与x轴正方向的夹角为θ：
有sinθ = 666 / r 故θ = arcsin(666 / r) ≈ 1.23426;
圆弧长度 = r·θ = 705.58 × 1.23426 ≈ 870.87
总移动间隔 = 705.58 + 870.87 = 1576.45
四舍五入到整数为1576。

1. asin(666 / 705.58) * 705.58 + 705.58

复制代码

答案

1576
试题B: 客流量上限

问题描述

一家连锁旅店在天下拥有2025个分店，分别编号为1至2025。随着节日相近，总部决定为每家分店设定逐日客流量的上限，分别记作A₁,A₂,…,A₂₀₂₅。这些上限并非随意分配，而是需要满足以下约束条件：

• A₁,A₂,…,A₂₀₂₅必须是1至2025的一个排列，即每个A_i均是1至2025之间的整数，且所有A_i互不雷同。
  
• 对于恣意分店i和j（1≤i,j≤2025，i可即是j），它们的客流量上限A_i和A_j的乘积不得超过i×j+2025。
  

现在，请你盘算这样的分配方案究竟有多少种。由于答案大概很大，你只需输出其对10^9+7取余后的效果即可。
解题思路

这个问题要求我们盘算满足特定约束条件的排列数量。让我们渐渐分析这个问题：
约束条件分析

• A₁, A₂, …, A₂₀₂₅ 必须是 1 到 2025 的一个排列
  
• 对于恣意 i 和 j (1 ≤ i,j ≤ 2025)，必须满足 Aᵢ × Aⱼ ≤ i × j + 2025
  

关键观察
首先，我们思量当 i = j 时的特殊情况：

• 此时约束条件变为：Aᵢ × Aᵢ ≤ i × i + 2025
  
• 即：Aᵢ² ≤ i² + 2025
  
• 因此：Aᵢ ≤ √(i² + 2025)
  

通过盘算和分析，我们可以得出以下结论：

• 对于 1014 ≤ i ≤ 2025 的情况：
  
  
  
  • 约束条件要求 Aᵢ ≤ i
    
  • 由于 Aᵢ 必须是 1 到 2025 之间的整数，且所有 Aᵢ 互不雷同
    
  • 最优解是 Aᵢ = i（这样可以最大化其他位置的选择空间）
    
  
  
• 对于 1 ≤ i ≤ 1012 的情况：
  
  
  
  • 约束条件允许 Aᵢ ≤ i + 1
    
  • 对于这些位置，我们有两种选择：Aᵢ = i 或 Aᵢ = i + 1
    
  
  
• 对于 1013 ≤ i ≤ 1013 的情况：
  
  
  
  • 这个位置的值已经被前面的分析确定
    
  
  

组合盘算
根据上述分析：

• 对于位置 1014 到 2025（共 1012 个位置），每个位置的值唯一确定为 Aᵢ = i
  
• 对于位置 1 到 1012（共 1012 个位置），每个位置有两种大概的选择
  
• 因此，总的方案数为 2¹⁰¹²
  

由于答案大概很大，我们需要对 10⁹ + 7 取模。终极答案为：
2¹⁰¹² mod (10⁹ + 7) = 781448427
代码实现

1. #include <bits/stdc++.h>
2. using namespace std;
4. const int MOD = 1e9 + 7;
5. const int N = 2025;
7. // 计算2的幂次取模
8. long long pow_mod(long long base, long long exp, long long mod) {
9.         long long result = 1;
10.         base %= mod;
11.         while (exp > 0) {
12.                 if (exp & 1) {
13.                         result = (result * base) % mod;
14.                 }
15.                 base = (base * base) % mod;
16.                 exp >>= 1;
17.         }
18.         return result;
19. }
21. int main() {
22.         // 根据分析，答案为2^1012 mod (10^9 + 7)
23.         long long ans = pow_mod(2, 1012, MOD);
24.         cout << ans << endl;
25.         return 0;
26. }

复制代码

答案：

781448427
试题C: 可分解的正整数

问题描述

定义一种特殊的整数序列，这种序列由连续递增的整数组成，并满足以下条件：

• 序列长度至少为3。
  
• 序列中的数字是连续递增的整数（即相邻元素之差为1），可以包括正整数、负整数或0。
  

例如，[1,2,3]、[4,5,6,7]和[-1,0,1]是符合条件的序列，而[1,2]（长度不敷）和[1,2,4]（不连续）不符合要求。
现给定一组包含N个正整数的数据A₁,A₂,…,A_N。如果某个A_i可以或许表现为符合上述条件的连续整数序列中所有元素的和，则称A_i是可分解的。请你统计这组数据中可分解的正整数的数量。
解题思路

代码实现

1. #include<bits/stdc++.h>
2. using namespace std;
4. int main(){
5.         int n;
6.         int t;
7.         int ans = 0;
8.         cin>>n;
9.         for(int i = 0;i < n;i++){
10.                 cin>>t;
11.                 if(t != 1){
12.                         ans++;
13.                 }
14.         }
15.         cout<<ans<<endl;
16.         return 0;
17. }

复制代码

试题D: 产值调解

问题描述

偏远的小镇上，三兄弟共同谋划着一家小型矿业公司"兄弟矿业"。公司旗下有三座矿山：金矿、银矿和铜矿，它们的初始产值分别用非负整数A、B和C表现。
为了稳定谋划，三兄弟计划了一个产值调解计谋，每年实行一次，每次调解时，将根据当前的产值A、B、C，盘算新产值：

• 金矿新产值A′=⌊(B+C)/2⌋；
  
• 银矿新产值B′=⌊(A+C)/2⌋；
  
• 铜矿新产值C′=⌊(A+B)/2⌋。
  

其中，⌊⌋表现向下取整。盘算出A′、B′、C′后，同时更新：A变为A′，B变为B′，C变为C′，作为下一年调解的底子。
三兄弟计划连续实行K次调解。现在，请你帮他们盘算，经过K次调解后，金矿、银矿和铜矿的产值分别是多少。
解题思路

我们可以直接模拟这个过程，但由于K大概很大（最大10^9），直接模拟会超时。
观察调解规则，我们可以发现：

• 如果A=B=C，那么调解后仍旧是A=B=C
  
• 如果不相等，每次调解后的值会趋向于均匀值
  

现实上，经过充足多次调解后，三个值会变得相等或者在一个很小的范围内循环。
通过数学分析和实行，我们可以发现：

• 如果初始值全部相等，那么调解后仍旧相等
  
• 如果不全相等，经过最多6次调解，三个值要么全部相等，要么会进入一个长度不超过3的循环
  

因此，我们可以先模拟前几次调解，然后根据情况决定终极效果。
代码实现

1. #include <bits/stdc++.h>
2. using namespace std;
4. void adjust(long long& a, long long& b, long long& c) {
5.         long long new_a = (b + c) / 2;
6.         long long new_b = (a + c) / 2;
7.         long long new_c = (a + b) / 2;
8.         a = new_a;
9.         b = new_b;
10.         c = new_c;
11. }
13. int main() {
14.         int T;
15.         cin >> T;
16.        
17.         while (T--) {
18.                 long long A, B, C, K;
19.                 cin >> A >> B >> C >> K;
20.                
21.                 // 如果已经相等，不需要调整
22.                 if (A == B && B == C) {
23.                         cout << A << " " << B << " " << C << endl;
24.                         continue;
25.                 }
26.                 while(K--){
27.                         adjust(A,B,C);
28.                         // 如果已经相等，不需要调整
29.                         if (A == B && B == C) {
30.                                 break;
31.                         }
32.                 }
33.                
34.                 cout << A << " " << B << " " << C << endl;
35.         }
36.        
37.         return 0;
38. }

复制代码

答案

对于样例输入：

• A=10, B=20, C=30, K=1
  
• 一次调解后：A′=25, B′=20, C′=15
  
• A=5, B=5, C=5, K=3
  
• 初始值已经相等，调解后仍旧是A=5, B=5, C=5
  

试题E: 画展布置

问题描述

画展策展人小蓝和助理小桥为即将举办的画展准备了N幅画作，其艺术代价分别为A₁,A₂,…,A_N。他们需要从这N幅画中挑选M幅，并按照肯定顺序布置在展厅的M个位置上。
为了优化布置，他们希望使艺术代价的变革水平通过一个数值L来权衡，且该值越小越好。数值L的定义为：
L = Σ(i=1 to M-1) |B²ᵢ₊₁ - B²ᵢ|
其中B_i表现展厅第i个位置上画作的艺术代价。
现在，他们希望通过经心挑选和排列这M幅画作，使L到达最小值。请你帮他们盘算出这个最小值是多少。
解题思路

这个问题要求我们从N幅画中选择M幅，并排列它们，使得相邻画作艺术代价平方的差的绝对值之和最小。
首先，我们可以观察到，对于恣意两幅画的艺术代价a和b，|a² - b²| = |a-b|·|a+b|。这意味着，如果我们想要最小化|a² - b²|，我们应该选择艺术代价接近的画作放在相邻位置。
一个直观的计谋是：

• 对所有画作的艺术代价举行排序
  
• 选择M幅连续的画作（因为连续的画作艺术代价差别最小）
  
• 按照特定顺序排列这M幅画作，使得L最小
  

对于排列顺序，我们可以证实，最优的排列方式是按照艺术代价从小到大或从大到小排列。
代码实现

1. #include <bits/stdc++.h>
2. using namespace std;
4. int main() {
5.         int N, M;
6.         cin >> N >> M;
7.        
8.         vector<int> values(N);
9.         for (int i = 0; i < N; i++) {
10.                 cin >> values[i];
11.         }
12.        
13.         // 排序
14.         sort(values.begin(), values.end());
15.        
16.         // 计算所有可能的连续M幅画作的L值
17.         long long min_L = LLONG_MAX;
18.        
19.         for (int i = 0; i <= N - M; i++) {
20.                 vector<int> selected(values.begin() + i, values.begin() + i + M);
21.                
22.                 // 计算按照从小到大排列的L值
23.                 long long L1 = 0;
24.                 for (int j = 0; j < M - 1; j++) {
25.                         long long diff = (long long)selected[j+1] * selected[j+1] - (long long)selected[j] * selected[j];
26.                         L1 += abs(diff);
27.                 }
28.                
29.                 // 计算按照从大到小排列的L值
30.                 long long L2 = 0;
31.                 for (int j = 0; j < M - 1; j++) {
32.                         long long diff = (long long)selected[M-j-2] * selected[M-j-2] - (long long)selected[M-j-1] * selected[M-j-1];
33.                         L2 += abs(diff);
34.                 }
35.                
36.                 min_L = min(min_L, min(L1, L2));
37.         }
38.        
39.         cout << min_L << endl;
40.         return 0;
41. }

复制代码

答案

对于样例输入：
N=4, M=2, 艺术代价为[1, 5, 2, 4]
排序后为[1, 2, 4, 5]
大概的连续2幅画作为：[1,2], [2,4], [4,5]
盘算L值：

• [1,2]: |2² - 1²| = |4 - 1| = 3
  
• [2,4]: |4² - 2²| = |16 - 4| = 12
  
• [4,5]: |5² - 4²| = |25 - 16| = 9
  

最小的L值为3。
试题F: 水质检测

解题思路

题目要求在一个2×n的河床上增加最少的检测器，使得所有检测器互相连通。河床用一个2×n的字符矩阵表现，其中’#‘表现已有检测器，’.'表现空白位置。如果两个检测器上下或左右相邻，则它们互相连通，且连通具有转达性。
这道题目可以使用动态规划来办理。我们需要思量如何让所有检测器连通，并且使新增的检测器数量最少。
状态定义
我们定义状态dp[j]表现：当处置惩罚到第i列，且第i列的第j举动’#'（无论是原有的还是新放置的），并且前i列的所有检测器都连通时，需要新增的最少检测器数量。
其中：

• i表现列号，范围是[st, en]，st是最左边有检测器的列，en是最右边有检测器的列
  
• j表现行号，取值为0或1，分别表现第一行和第二行
  

状态转移
对于位置(i,j)，我们有两种大概的转移来源：

• 从(i-1,j)转移：即上一列同一行的位置
  
• 从(i-1,1-j)转移：即上一列不偕行的位置，但这需要通过当前线的另一行(i,1-j)毗连
  

下面用图示来说明状态转移：

1. 列i-1    列i
2.   □ ---- □  (行0)
3.   |      |
4.   □ ---- □  (行1)

复制代码

假设我们当前要盘算dp[0]（即列i 行0的状态）：

• 从dp[i-1][0]转移：
  

1. 列i-1    列i
2.   # ---- #  (行0)
3.   |      |
4.   □      □  (行1)

复制代码

• 如果(i,0)是’#‘，且(i-1,0)也是’#'，它们自然连通。
  
• 如果(i,0)不是’#'，需要放置一个检测器，花费+1。
  

• 从dp[i-1][1]转移：
  

1. 列i-1    列i
2.   □      #  (行0)
3.   |      |
4.   # ---- □  (行1)

复制代码

• 如果(i,0)是’#‘，且(i-1,1)也是’#‘，要与(i,0)连通，需要通过(i,1),当(i,1)不是’#'时，就需要放置一个检测器，故花费+(s[1] == ‘#’ ? 0 : 1)。
  
• 如果(i,0)不是’#'，那么(i,0)需要放置一个检测器，花费+(s[0] == ‘#’ ? 0 : 1)。
  

状态转移方程如下：

• 如果s[j]已经是’#'（已有检测器）：
  

1. dp[i][j] = min(dp[i-1][j], dp[i-1][1-j] + (s[i][1-j]=='#'?0:1))

复制代码

• 如果s[j]是’.'（需要放置检测器）：
  

1. dp[i][j] = min(dp[i-1][j], dp[i-1][1-j] + (s[i][1-j]=='#'?0:1))
2. + 1

复制代码

边界条件
对于起始位置st（最左边有检测器的位置）：

• 如果s[st][0]是’#'，则dp[st][0]=0
  
• 如果s[st][0]是’.'，则dp[st][0]=1（需要放置一个检测器）
  
• 同理处置惩罚dp[st][1]
  

如果起始位置两行都有检测器，需要确保它们连通，此时dp[st][0]=dp[st][1]=0。
终极效果
终极答案是min(dp[en][0], dp[en][1])，表现在最右边有检测器的位置en，使得所有检测器连通的最小花费。
代码实现

1. #include <bits/stdc++.h>
2. using namespace std;
3. const int N = 1e6+30;
5. char s[N][2];
6. int dp[N][2]; // dp[i][j]表示当前第i列第j行为'#'且与前面的检测器连通时的最小花费
8. void way(){
9.     string t;
10.     int n;
11.     // 数据输入
12.     for(int j=0;j<2;j++){
13.         cin>>t;// 读入一个字符串
14.         n = t.size();
15.         for(int i=1;i<=n;i++)s[i][j] = t[i-1];
16.     }
18.     int st = n+1,en = 0; // 找到左右两边的起始位置（最左边有检测器的位置）和（最右边有检测器的位置）。
19.     for(int i=1;i<=n;i++){
20.         if(s[i][0]=='#'||s[i][1]=='#'){
21.             st = min(i,st);
22.             en = max(en,i);
23.         }
24.     }
25.      
26.     //如果没有检测器直接输出0
27.     if(st == n + 1){
28.         cout<<0<<endl;
29.         return;
30.     }
31.      
32.     // 初始化dp数组
33.     memset(dp, 0x3f, sizeof(dp)); // 初始化为一个很大的值
34.      
35.     // 处理起始位置
36.     if(s[st][0]=='#') dp[st][0]=0; // 如果已经有检测器，花费为0
37.     else dp[st][0]=1; // 否则需要放置一个检测器，花费为1
38.      
39.     if(s[st][1]=='#') dp[st][1]=0; // 如果已经有检测器，花费为0
40.     else dp[st][1]=1; // 否则需要放置一个检测器，花费为1
41.      
42.     // 如果起始位置两行都有检测器，需要确保它们连通
43.     if(s[st][0]=='#' && s[st][1]=='#') {
44.         dp[st][0] = dp[st][1] = 0; // 两个位置都已有检测器，花费为0
45.     }
46.      
47.     for(int i=st+1;i<=en;i++){
48.         // 计算dp[i][0]
49.         if(s[i][0]=='#') { // 如果当前位置已有检测器
50.             // 从上一列转移
51.             dp[i][0] = min(dp[i-1][0], dp[i-1][1] + (s[i][1]=='#'?0:1));
52.         } else { // 如果当前位置需要放置检测器
53.             dp[i][0] = min(dp[i-1][0], dp[i-1][1] + (s[i][1]=='#'?0:1)) + 1;
54.         }
55.          
56.         // 计算dp[i][1]
57.         if(s[i][1]=='#') { // 如果当前位置已有检测器
58.             // 从上一列转移
59.             dp[i][1] = min(dp[i-1][1], dp[i-1][0] + (s[i][0]=='#'?0:1));
60.         } else { // 如果当前位置需要放置检测器
61.             dp[i][1] = min(dp[i-1][1], dp[i-1][0] + (s[i][0]=='#'?0:1)) + 1;
62.         }
63.     }
64.      
65.     cout<<min(dp[en][0],dp[en][1])<<endl;
66. }
68. int main(){
69.     way();
70.     return 0;
71. }

复制代码

示例分析

让我们以样例为例，详细分析算法的实行过程：
输入：

1. .##.....#
2. .#.#.#...

复制代码

我们可以将其表现为一个2×9的矩阵（为了方便，列号从1开始）：

1. 列号: 1 2 3 4 5 6 7 8 9
2. 行0:  . # # . . . . . #
3. 行1:  . # . # . # . . .

复制代码

1. 确定盘算范围
首先找到st=2（最左边有检测器的位置）和en=9（最右边有检测器的位置）。
2. 初始化dp数组
初始化dp数组为一个很大的值（表现无法到达的状态）。
对于起始位置st=2：

• s[2] [0]=‘#’，以是dp[2] [0]=0（已有检测器，不需要额外花费）
  
• s[2] [1]=‘#’，以是dp[2] [1]=0（已有检测器，不需要额外花费）
  

由于第2列的两行都有检测器，它们已经连通，以是dp[2] [0]=dp[2] [1]=0。
3. 逐列盘算dp值
对于i=3（第3列）：
盘算dp[3] [0]：

• s[3] [0]=‘#’（已有检测器）
  
  
  
  • 从dp[2] [0]转移：dp[2] [0]=0
    
  • 从dp[2] [1]转移：dp[2] [1]=0，但需要通过(3,1)毗连，s[3] [1]=‘.’，需要额外放置一个检测器，以是花费为0+1=1
    
  
  
• 取最小值：dp[3] [0]=min(0,1)=0
  

盘算dp[3] [1]：

• s[3] [1]=‘.’（需要放置检测器）
  
  
  
  • 从dp[2] [1]转移：dp[2] [1]=0
    
  • 从dp[2] [0]转移：dp[2] [0]=0，但需要通过(3,0)毗连，s[3] [0]=‘#’，不需要额外放置检测器，以是花费为0+0=0
    
  
  
• 由于(3,1)需要放置检测器，额外花费1，以是dp[3] [1]=min(0,0)+1=1
  

对于i=4（第4列）：
盘算dp[4] [0]：

• s[4] [0]=‘.’（需要放置检测器）
  
  
  
  • 从dp[3] [0]转移：dp[3] [0]=0
    
  • 从dp[3] [1]转移：dp[3] [1]=1，但需要通过(4,1)毗连，s[4] [1]=‘#’，不需要额外放置检测器，以是花费为1+0=1
    
  
  
• 由于(4,0)需要放置检测器，额外花费1，以是dp[4] [0]=min(0,1)+1=1
  

盘算dp[4] [1]：

• s[4] [1]=‘#’（已有检测器）
  
  
  
  • 从dp[3] [1]转移：dp[3] [1]=1
    
  • 从dp[3] [0]转移：dp[3] [0]=0，但需要通过(4,0)毗连，s[4] [0]=‘.’，需要额外放置一个检测器，以是花费为0+1=1
    
  
  
• 取最小值：dp[4] [1]=min(1,1)=1
  

对于i=5（第5列）：
盘算dp[5] [0]：

• s[5] [0]=‘.’（需要放置检测器）
  
  
  
  • 从dp[4] [0]转移：dp[4] [0]=1
    
  • 从dp[4] [1]转移：dp[4] [1]=1，但需要通过(5,1)毗连，s[5] [1]=‘.’，需要额外放置一个检测器，以是花费为1+1=2
    
  
  
• 由于(5,0)需要放置检测器，额外花费1，以是dp[5] [0]=min(1,2)+1=2
  

盘算dp[5] [1]：

• s[5] [1]=‘.’（需要放置检测器）
  
  
  
  • 从dp[4] [1]转移：dp[4] [1]=1
    
  • 从dp[4] [0]转移：dp[4] [0]=1，但需要通过(5,0)毗连，s[5] [0]=‘.’，需要额外放置一个检测器，以是花费为1+1=2
    
  
  
• 由于(5,1)需要放置检测器，额外花费1，以是dp[5] [1]=min(1,2)+1=2
  

对于i=6（第6列）：
盘算dp[6] [0]：

• s[6] [0]=‘.’（需要放置检测器）
  
  
  
  • 从dp[5] [0]转移：dp[5] [0]=2
    
  • 从dp[5] [1]转移：dp[5] [1]=2，但需要通过(6,1)毗连，s[6] [1]=‘#’，不需要额外放置检测器，以是花费为2+0=2
    
  
  
• 由于(6,0)需要放置检测器，额外花费1，以是dp[6] [0]=min(2,2)+1=3
  

盘算dp[6] [1]：

• s[6] [1]=‘#’（已有检测器）
  
  
  
  • 从dp[5] [1]转移：dp[5] [1]=2
    
  • 从dp[5] [0]转移：dp[5] [0]=2，但需要通过(6,0)毗连，s[6] [0]=‘.’，需要额外放置一个检测器，以是花费为2+1=3
    
  
  
• 取最小值：dp[6] [1]=min(2,3)=2
  

对于i=7（第7列）：
盘算dp[7] [0]：

• s[7] [0]=‘.’（需要放置检测器）
  
  
  
  • 从dp[6] [0]转移：dp[6] [0]=3
    
  • 从dp[6] [1]转移：dp[6] [1]=2，但需要通过(7,1)毗连，s[7] [1]=‘.’，需要额外放置一个检测器，以是花费为2+1=3
    
  
  
• 由于(7,0)需要放置检测器，额外花费1，以是dp[7] [0]=min(3,3)+1=4
  

盘算dp[7] [1]：

• s[7] [1]=‘.’（需要放置检测器）
  
  
  
  • 从dp[6] [1]转移：dp[6] [1]=2
    
  • 从dp[6] [0]转移：dp[6] [0]=3，但需要通过(7,0)毗连，s[7] [0]=‘.’，需要额外放置一个检测器，以是花费为3+1=4
    
  
  
• 由于(7,1)需要放置检测器，额外花费1，以是dp[7] [1]=min(2,4)+1=3
  

对于i=8（第8列）：
盘算dp[8] [0]：

• s[8] [0]=‘.’（需要放置检测器）
  
  
  
  • 从dp[7] [0]转移：dp[7] [0]=4
    
  • 从dp[7] [1]转移：dp[7 ] [1]=3，但需要通过(8,1)毗连，s[8] [1]=‘.’，需要额外放置一个检测器，以是花费为3+1=4
    
  
  
• 由于(8,0)需要放置检测器，额外花费1，以是dp[8] [0]=min(4,4)+1=5
  

盘算dp[8] [1]：

• s[8] [1]=‘.’（需要放置检测器）
  
  
  
  • 从dp[7] [1]转移：dp[7] [1]=3
    
  • 从dp[7] [0]转移：dp[7] [0]=4，但需要通过(8,0)毗连，s[8] [0]=‘.’，需要额外放置一个检测器，以是花费为4+1=5
    
  
  
• 由于(8,1)需要放置检测器，额外花费1，以是dp[8] [1]=min(3,5)+1=4
  

对于i=9（第9列）：
盘算dp[9] [0]：

• s[9] [0]=‘#’（已有检测器）
  
  
  
  • 从dp[8] [0]转移：dp[8] [0]=5
    
  • 从dp[8] [1]转移：dp[8] [1]=4，但需要通过(9,1)毗连，s[9] [1]=‘.’，需要额外放置一个检测器，以是花费为4+1=5
    
  
  
• 取最小值：dp[9] [0]=min(5,5)=5
  

盘算dp[9] [1]：

• s[9] [1]=‘.’（需要放置检测器）
  
  
  
  • 从dp[8] [1]转移：dp[8] [1]=4
    
  • 从dp[8] [0]转移：dp[8] [0]=5，但需要通过(9,0)毗连，s[9] [0]=‘#’，不需要额外放置检测器，以是花费为5+0=5
    
  
  
• 由于(9,1)需要放置检测器，额外花费1，以是dp[9] [1]=min(4,5)+1=5
  

4. 盘算终极效果
终极答案是min(dp[9] [0], dp[9] [1])=min(5, 5)=5，表现需要增加5个检测器使所有检测器连通。
可视化终极方案
一种大概的终极方案（'+'表现新增的检测器）：

1. 列号: 1 2 3 4 5 6 7 8 9
2. 行0:  . # # + + . . . #
3. 行1:  . # . # . # + + .

复制代码

或者：

1. 列号: 1 2 3 4 5 6 7 8 9
2. 行0:  . # # . . . . + #
3. 行1:  . # + # + # + + .

复制代码

这两种方案都需要增加5个检测器，使所有检测器连通。
试题G: 生产车间

问题描述

小明正在改造一个生产车间的生产流水线。这个车间共有n台装备，构成以1为根结点的一棵树，结点i有权值w_i。其中叶节点的权值w_i表现每单元时间将产出w_i单元的质料并送往父结点，根结点的权值w_i表现每单元时间内能打包多少单元成品，其他结点的权值w_i表现每单元时间最多能加工w_i单元的质料并送往父结点。
由于当前生产线中某些结点存在产能不敷的问题导致生产线无法正常运行，即存在某些结点每单元时间收到的质料超过了当前结点的加工本领上限。小明计划删除一些结点使得所有结点都能正常运行。他想知道删除一些结点后根结点每单元时间内最多能打包多少单元的成品？
解题思路

这个问题描述了一个生产流水线优化场景：

• 有n台装备构成一棵以1为根的树
  
• 每个节点有权值w_i，表现其加工本领
  
• 叶节点产生质料，非叶节点加工质料，根节点打包成品
  
• 如果节点吸收的质料超过其加工本领，生产线无法正常运行
  
• 可以删除一些节点（及其子树）使所有节点正常运行
  
• 目标是最大化根节点的产出
  

关键洞察：这是一个树形结构上的优化问题，我们需要决定保存或删除每个节点，以使根节点的产出最大化。要留意并不是每个节点的最大值组合起来并就肯定是所求的最优解，好比样例数据，样例解释见代码后
我们采用自底向上的方法，从叶子节点开始，盘算每个节点在差别情况下大概的产出值：

• 对于每个节点，我们有两个基本选择：
  
  
  
  • 保存节点：节点产生其权值的产出（对于叶子节点）或处置惩罚子节点的质料（对于非叶子节点）
    
  • 删除节点：节点产出为0
    
  
  
• 对于非叶子节点，我们需要：
  
  
  
  • 收集所有子节点的大概产出值
    
  • 组合这些产出值，确保总和不超过当前节点的加工本领
    
  • 盘算当前节点所有大概的产出值
    
  
  
• 终极，根节点的最大大概产出值就是答案
  

代码实现

1. #include <bits/stdc++.h>
2. using namespace std;
4. const int MAX_NODES = 1005;
5. vector<int> g[MAX_NODES]; // 树结构的邻接表
6. int n, capacity[MAX_NODES]; // 节点数和各节点容量
8. /**
9. * 计算以current_node为根的子树能提供的合法材料数值集合
10. * @param current_node 当前处理的节点
11. * @param parent_node 父节点（防止回溯）
12. * @return 包含所有可能值的有序集合
13. */
14. set<int> dfs(int current_node, int parent_node) {
15.         // g[current_node].size() == 1 表示无向图的叶子节点
16.         //parent_node != 0 避免出现链状
17.         if (g[current_node].size() == 1 && parent_node != 0) {
18.                 return {capacity[current_node], 0}; // 保留或关闭该节点
19.         }
20.        
21.         set<int> valid_sums = {0}; // 初始化，包含0（全关闭情况）
22.        
23.         // 使用范围for循环遍历邻接节点
24.         for (int child_node : g[current_node]) {
25.                 if (child_node == parent_node) continue; // 跳过父节点
26.                
27.                 auto child_outputs = dfs(child_node, current_node);//深入遍历子节点
28.                 set<int> current_sums = valid_sums; // 当前状态的副本
29.                
30.                 //依次将任意两个子节点的所有取值进行组合
31.                 for (int parent_sum : current_sums) {
32.                         for (int child_contribution : child_outputs) {
33.                                 int total = parent_sum + child_contribution;
34.                                 if (total <= capacity[current_node]) {
35.                                         valid_sums.insert(total);
36.                                 }
37.                         }
38.                 }
39.         }
40.         return valid_sums;//返回该节点的所有取值情况
41. }
43. int main() {
44.         // 输入处理
45.         cin >> n;
46.         for (int i = 1; i <= n; ++i) {
47.                 cin >> capacity[i];
48.         }
49.        
50.         // 构建树结构
51.         for (int i = 1; i < n; ++i) {
52.                 int node_a, node_b;
53.                 cin >> node_a >> node_b;
54.                 g[node_a].push_back(node_b);
55.                 g[node_b].push_back(node_a);
56.         }
57.        
58.         // 计算并输出最大打包量
59.         cout << *dfs(1, 0).rbegin() << endl;
60.        
61.         return 0;
62. }

复制代码

留意：这份代码在部分网站测试会有极少量测试集超时，对此可以使用使用位运算bitset代替集合：

1. #include <bits/stdc++.h>
2. using namespace std;
4. const int MAXN = 1005;
5. const int MAXW = 1001;  // 最大权值+1
7. int n;                          // 节点数量
8. int w[MAXN];                    // 每个节点的权值（容量）
9. vector<int> graph[MAXN];        // 无向图邻接表
11. /**
12. * 计算以u为根的子树能提供的合法材料数值集合
13. * 使用bitset优化状态表示和组合操作
14. * @param u 当前处理的节点
15. * @param parent 父节点（防止回溯）
16. * @return 包含所有可能值的位向量
17. */
18. bitset<MAXW> dfs(int u, int parent) {
19.     // 判断是否为叶子节点
20.     if (graph[u].size() == 1 && parent != 0) {
21.         bitset<MAXW> result;
22.         result[0] = 1;          // 可以产出0（删除节点）
23.         result[w[u]] = 1;       // 可以产出w[u]（保留节点）
24.         return result;
25.     }
26.    
27.     // 初始化结果位向量，只有0位为1（表示所有子节点都关闭的情况）
28.     bitset<MAXW> result;
29.     result[0] = 1;
30.    
31.     // 遍历所有子节点
32.     for (int v : graph[u]) {
33.         if (v == parent) continue;  // 跳过父节点
34.         
35.         // 递归计算子节点的所有可能产出
36.         bitset<MAXW> child_outputs = dfs(v, u);
37.         
38.         // 保存当前结果的副本
39.         bitset<MAXW> current = result;
40.         result.reset();  // 清空结果
41.         
42.         // 优化的组合操作
43.         for (int i = 0; i <= w[u]; i++) {
44.             if (current[i]) {
45.                 // 对于当前值i，与子节点的每个可能产出组合
46.                 for (int j = 0; j <= w[u] - i; j++) {
47.                     if (child_outputs[j]) {
48.                         result[i + j] = 1;
49.                     }
50.                 }
51.             }
52.         }
53.     }
54.    
55.     return result;  // 返回所有可能的产出值
56. }
58. int main() {
59.     ios_base::sync_with_stdio(false);  // 优化输入输出
60.     cin.tie(nullptr);
61.    
62.     cin >> n;
63.    
64.     // 读取每个节点的权值
65.     for (int i = 1; i <= n; i++) {
66.         cin >> w[i];
67.     }
68.    
69.     // 读取树的边
70.     for (int i = 0; i < n - 1; i++) {
71.         int u, v;
72.         cin >> u >> v;
73.         graph[u].push_back(v);
74.         graph[v].push_back(u);
75.     }
76.    
77.     // 计算根节点的所有可能产出
78.     bitset<MAXW> root_outputs = dfs(1, 0);
79.    
80.     // 找出最大可能产出
81.     int ans = 0;
82.     for (int i = MAXW - 1; i >= 0; i--) {
83.         if (root_outputs[i]) {
84.             ans = i;
85.             break;
86.         }
87.     }
88.    
89.     cout << ans << endl;
90.    
91.     return 0;
92. }

复制代码

样例详细阐述

让我们以给定的样例来详细说明算法的实行过程：

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

复制代码

树的结构如下：

1.     1
2.    / \
3.   2   3
4. /|\
5. 4 5 6
6.    /|\
7.   7 8 9

复制代码

节点权值：w = [9, 7, 3, 7, 1, 6, 2, 2, 7]（索引从1开始）
实行DFS过程：

• 叶子节点：
  
  
  
  • 节点3：返回3, 0
    
  • 节点4：返回7, 0
    
  • 节点5：返回1, 0
    
  • 节点7：返回2, 0
    
  • 节点8：返回2, 0
    
  • 节点9：返回7, 0
    
  
  
• 节点6（容量为6）：
  
  
  
  • 初始效果集：0
    
  • 处置惩罚子节点7（2, 0）：效果集变为0, 2
    
  • 处置惩罚子节点8（2, 0）：效果集变为0, 2, 4
    
  • 处置惩罚子节点9（7, 0）：
    
  • 0 + 0 = 0，已在效果集中
    
  • 0 + 7 = 7 > 6，超过容量，不添加
    
  • 2 + 0 = 2，已在效果集中
    
  • 2 + 7 = 9 > 6，超过容量，不添加
    
  • 4 + 0 = 4，添加到效果集
    
  • 4 + 7 = 11 > 6，超过容量，不添加
    
  终极效果集：0, 2, 4
  
  
• 节点2（容量为7）：
  
  
  
  • 初始效果集：0
    
  • 处置惩罚子节点4（7, 0）：效果集变为0, 7
    
  • 处置惩罚子节点5（1, 0）：效果集变为0, 1, 7, 8，但8 > 7，以是现实为0, 1, 7
    
  • 处置惩罚子节点6（0, 2, 4）：
    
  • 组合后得到0, 1, 2, 4, 7, 3 (2 + 1), 9 (2 + 7 应舍去), 5(4 + 1), 11(4 + 7 应舍去)
    
  
  

终极效果集：0, 1, 2, 3, 4, 5, 7

• 根节点1（容量为9）：
  
  
  
  • 初始效果集：0
    
  • 处置惩罚子节点2（0, 1, 2, 3, 4, 5, 7）：效果集变为0, 1, 2, 3, 4, 5, 7
    
  • 处置惩罚子节点3（3, 0）：
    
  • 组合后得到0, 1, 2, 3, 4, 5, 6 (3 + 3), 7 (4 + 3), 8 (5 + 3),10 (7 + 1)，但10 > 9，以是现实为0, 1, 2, 3, 4, 5, 6, 7, 8
    
  
  

终极效果集：0, 1, 2, 3, 4, 5, 6, 7, 8

• 终极答案：根节点1的效果集中的最大值为8
  

试题H: 装修报价

问题描述

老王计划装修房子，接洽了一家装修公司。该公司有一套主动报价系统，只需用户提供N项装修相关费用A₁,A₂,…,A_N，系统便会根据这些费用生成终极的报价。
系统会依据某种内部算法，在每对相邻数字之间插入+（加法）、−（减法）或⊕（异或）运算符，并按照特定优先级规则盘算效果：异或运算优先级最高，其次是加减。
老王决定模拟其运作方式，实验每种大概的运算符组合，盘算出所有大概出现的效果的总和。请你帮老王算出所有大概的效果的总和。由于该总和大概很大，你只需提供其对10^9+7取余后的效果即可。
方法一：前缀异或罗列法

解题思路

核心思想是罗列前缀异或的长度，盘算每个前缀异或在所有大概组合中的贡献，然后求和。
关键洞察：

• 思量给表达式的第一个值前面也补上+号，例如：2−3⊕4 现实上是 +2−3⊕4
  
• 由于异或运算的优先级高于加减法，连续的异或运算效果可以合并成一个数字，使表达式酿成只包含+和-的情势
  
• 所有的"+XXX"和"-XXX"在差别的式子中会同时出现，它们的贡献会相互抵消,也就是：对组合的式子分割为A+B，那么肯定存在A-B的组合情况，这两者相加就会使得B相互抵消了，仅有A有贡献值
  
• 对终极效果有贡献的只有前缀异或
  

对于长度为i的前缀异或S（即A[1] ⊕ A[2] ⊕ … ⊕ A），其贡献盘算方式为：

• 第i+1个位置的运算符必须是+或-（2种选择，即把前面i个运算符的效果看作是一个数字A，背面的运算看作一个数字B），不能是异或（A + B / A - B）
  
• 其中，第i+2到第n个位置的运算符可以是恣意三种（3^(n-i-1)种选择，无论是哪一种都有对应的组合将其抵消掉）
  
• 因此，贡献为：S * 2 * 3^(n-i-1)
  

**特殊情况：**当i=n时（即所有数字都异或），贡献为S。
最后的总效果就是所有前缀异或的加权和：

1. 结果 = S_1 * 2 * 3^(n-2) + S_2 * 2 * 3^(n-3) + ... + S_(n-1) * 2 * 3^0 + S_n * 1

复制代码

代码实现

1. #include <bits/stdc++.h>
2. using namespace std;
4. typedef long long ll;
5. const int MOD = 1e9 + 7;
6. vector<int> a;
8. // 优化计算a^b % MOD
9. ll cal(ll a, ll b) {
10.         ll res = 1;
11.         while (b > 0) {
12.                 //b是奇数，先乘掉一个a
13.                 if (b % 2 == 1) res = (res * a) % MOD;
14.                 //a^10 = (a ^ 2) ^ 5从而降低循环次数
15.                 a = (a * a) % MOD;
16.                 //指数b /= 2
17.                 b /= 2;
18.         }
19.         return res;
20. }
22. int main() {
23.         int n;
24.         cin >> n;
25.         // 只有一个数字
26.         if (n == 1) {
27.                 int x;
28.                 cin >> x;
29.                 cout << x << endl;//直接输出
30.                 return 0;
31.         }
32.        
33.         a.resize(n + 1);//存储n个数字
34.         for (int i = 1; i <= n; i++) {
35.                 cin >> a[i];
36.         }
37.        
38.         ll ans = 0;
39.         ll s = 0;//存储异或值（即a[1] ⊕ a[2] ⊕ ... ⊕ a[i]）
40.        
41.         for (int i = 1; i <= n; i++) {
42.                 s ^= a[i];
43.                
44.                 if (i < n) {
45.                         // 不是最后一个数字：贡献为 s * 2 * 3^(n-i-1)
46.                         ll cnt = (s * 2) % MOD;
47.                         cnt = (cnt * cal(3, n - i - 1)) % MOD;
48.                         ans = (ans + cnt) % MOD;
49.                 } else {
50.                         // 是最后一个数字：贡献为 s
51.                         ans = (ans + s) % MOD;
52.                 }
53.         }
54.        
55.         cout << ans << endl;
56.         return 0;
57. }

复制代码

样例分析

以样例 [0, 2, 5] 为例，详细演示算法实行过程：
初始状态：

• n = 3
  
• A = [0, 0, 2, 5]（代码实行时索引从1开始）
  
• ans = 0
  
• s= 0
  

第1次迭代 (i=1, A[1]=0)：

• s= 0 ^ 0 = 0
  
• i < n，盘算贡献：
  
• cnt = 0 * 2 * 3^(3-1-1) = 0 * 2 * 3^1 = 0 * 2 * 3 = 0
  
• ans = 0 + 0 = 0
  

第2次迭代 (i=2, A[2]=2)：

• s = 0 ^ 2 = 2
  
• i < n，盘算贡献：
  
• cnt = 2 * 2 * 3^(3-2-1) = 2 * 2 * 3^0 = 2 * 2 * 1 = 4
  
• ans = 0 + 4 = 4
  

第3次迭代 (i=3, A[3]=5)：

• s = 2 ^ 5 = 7
  
• i = n，盘算贡献：
  
• cnt = 7
  
• ans = 4 + 7 = 11
  

终极答案为11，与样例一致。
方法二：递推关系法

解题思路

核心思想是根据方法一原理，利用递推关系直接盘算所有大概效果的总和，避免罗列所有3^(N-1)种组合。
关键洞察：

• 对于除第一项外的每一项，其贡献总和为0。这是因为对于恣意非第一项的数字A，如果我们将其前面的+改为-（或将-改为+），而保持其他运算符不变，这两种情况的效果会互为相反数，在总和中相互抵消。
  
  
  
  • 例如数据a,b,c : a + b + c; a + b - c; a + b ⊕ c 我们可以用a - b + c; a - b - c; a - b ⊕ c 完全消去b的贡献
    
  
  
• 唯一有贡献的是从第一项开始的连续异或序列（前缀异或）。
  

基于这一洞察，我们可以推导出递推关系：

• 设S[k]表现前k个数的异或和：S[k] = A[1] ⊕ A[2] ⊕ … ⊕ A[k]
  
• 设Ans[k]表现思量前k个数字时所有大概效果的总和
  

递推关系为：

1. Ans[k] = 3 * Ans[k-1] - S[k-1] + S[k]

复制代码

这个递推关系可以这样理解：

• 当思量第k个数字时，该数字前的符号有3种大概（添加+、-或⊕），以是乘以3
  
• 需要减去前k-1个数字的异或和S[k-1]的贡献，因为在盘算3*Ans[k-1]时重复盘算了
  
• 需要加上包含第k个数字的新异或和,S[k]的贡献
  

代码解释

1. #include <bits/stdc++.h>
2. using namespace std;
4. typedef long long ll;
5. const int MOD = 1e9 + 7;
7. int main() {
8.         int n;
9.         cin >> n;
10.        
11.         ll ans = 0;  // 总答案
12.         ll s = 0;  // 当前前缀异或和
13.        
14.         for (int i = 1; i <= n; i++) {
15.                 int x;
16.                 cin >> x;
17.                
18.                 // 更新答案：ans = ans * 3 - s + (s ^ x)
19.                 ans = (ans * 3 - s + (s ^ x) + MOD) % MOD;
20.                
21.                 // 更新前缀异或和
22.                 s ^= x;
23.         }
24.        
25.         cout << ans << endl;
26.         return 0;
27. }

复制代码