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

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

试题A: 移动距离

问题描述

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

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

在这种条件下，他到达目的地最少移动多少单位距离？你只需要输出答案四舍五入到整数的结果。

解题思路

这个问题可以转化为：如何从原点到达目标点，使得路径长度最小。

首先，我们可以观察到，如果目标点在x轴上，那么直接水平向右移动是最优的。

对于一般情况，我们可以分两步走：

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

目标点(233,666)到原点的距离为：
r = √(233² + 666²) = √(54289 + 443556) = √497845 ≈ 705.58

第一步移动距离为r = 705.58
第二步需要计算圆弧长度。目标点与x轴正方向的夹角为：
θ = arctan(666/233) ≈ 1.2323弧度

圆弧长度 = r·θ = 705.58 × 1.2323 ≈ 869.49

总移动距离 = 705.58 + 869.49 = 1575.07

四舍五入到整数为1575。

答案

1575

试题C: 可分解的正整数

问题描述

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

1. 序列长度至少为3。
2. 序列中的数字是连续递增的整数（即相邻元素之差为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是可分解的。请你统计这组数据中可分解的正整数的数量。

解题思路

代码实现

#include<bits/stdc++.h>
using namespace std;

int main(){
	int n;
	int t;
	int ans = 0;
	cin>>n;
	for(int i = 0;i < n;i++){
		cin>>t;
		if(t != 1){
			ans++;
		}
	}
	cout<<ans<<endl;
	return 0;
}

试题D: 产值调整

问题描述

偏远的小镇上，三兄弟共同经营着一家小型矿业公司"兄弟矿业"。公司旗下有三座矿山：金矿、银矿和铜矿，它们的初始产值分别用非负整数A、B和C表示。

为了稳定经营，三兄弟设计了一个产值调整策略，每年执行一次，每次调整时，将根据当前的产值A、B、C，计算新产值：

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

其中，⌊⌋表示向下取整。计算出A′、B′、C′后，同时更新：A变为A′，B变为B′，C变为C′，作为下一年调整的基础。

三兄弟计划连续执行K次调整。现在，请你帮他们计算，经过K次调整后，金矿、银矿和铜矿的产值分别是多少。

解题思路

我们可以直接模拟这个过程，但由于K可能很大（最大10^9），直接模拟会超时。

观察调整规则，我们可以发现：

1. 如果A=B=C，那么调整后仍然是A=B=C
2. 如果不相等，每次调整后的值会趋向于平均值

实际上，经过足够多次调整后，三个值会变得相等或者在一个很小的范围内循环。

通过数学分析和实验，我们可以发现：

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

因此，我们可以先模拟前几次调整，然后根据情况决定最终结果。

代码实现

#include <bits/stdc++.h>
using namespace std;

void adjust(long long& a, long long& b, long long& c) {
	long long new_a = (b + c) / 2;
	long long new_b = (a + c) / 2;
	long long new_c = (a + b) / 2;
	a = new_a;
	b = new_b;
	c = new_c;
}

int main() {
	int T;
	cin >> T;
	
	while (T--) {
		long long A, B, C, K;
		cin >> A >> B >> C >> K;
		
		// 如果已经相等，不需要调整
		if (A == B && B == C) {
			cout << A << " " << B << " " << C << endl;
			continue;
		}
		while(K--){
			adjust(A,B,C);
			// 如果已经相等，不需要调整
			if (A == B && B == C) {
				break;
			}
		}
		
		cout << A << " " << B << " " << C << endl;
	}
	
	return 0;
}

对于样例输入：

1. A=10, B=20, C=30, K=1

2. 一次调整后：A′=25, B′=20, C′=15

3. A=5, B=5, C=5, K=3

4. 初始值已经相等，调整后仍然是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²|，我们应该选择艺术价值接近的画作放在相邻位置。

一个直观的策略是：

1. 对所有画作的艺术价值进行排序
2. 选择M幅连续的画作（因为连续的画作艺术价值差异最小）
3. 按照特定顺序排列这M幅画作，使得L最小

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

代码实现

#include <bits/stdc++.h>
using namespace std;

int main() {
	int N, M;
	cin >> N >> M;
	
	vector<int> values(N);
	for (int i = 0; i < N; i++) {
		cin >> values[i];
	}
	
	// 排序
	sort(values.begin(), values.end());
	
	// 计算所有可能的连续M幅画作的L值
	long long min_L = LLONG_MAX;
	
	for (int i = 0; i <= N - M; i++) {
		vector<int> selected(values.begin() + i, values.begin() + i + M);
		
		// 计算按照从小到大排列的L值
		long long L1 = 0;
		for (int j = 0; j < M - 1; j++) {
			long long diff = (long long)selected[j+1] * selected[j+1] - (long long)selected[j] * selected[j];
			L1 += abs(diff);
		}
		
		// 计算按照从大到小排列的L值
		long long L2 = 0;
		for (int j = 0; j < M - 1; j++) {
			long long diff = (long long)selected[M-j-2] * selected[M-j-2] - (long long)selected[M-j-1] * selected[M-j-1];
			L2 += abs(diff);
		}
		
		min_L = min(min_L, min(L1, L2));
	}
	
	cout << min_L << endl;
	return 0;
}

对于样例输入：
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的河床上铺设水质检测器。在他铺设之前，河床上已经存在一些检测器。如果两个检测器上下或者左右相邻，那么这两个检测器就是互相连通的。连通具有传递性，即如果A和B连通，B和C连通，那么A和C也连通。现在他需要在河床上增加铺设一些检测器使得所有的检测器都互相连通。他想知道最少需要增加铺设多少个检测器？

解题思路

题目要求在一个2×n的河床上增加最少的检测器，使得所有检测器互相连通。河床用一个2×n的字符矩阵表示，其中’#‘表示已有检测器，’.'表示空白位置。如果两个检测器上下或左右相邻，则它们互相连通，且连通具有传递性。

这道题目可以使用动态规划来解决。我们需要考虑如何让所有检测器连通，并且使新增的检测器数量最少。

状态定义

我们定义状态dp[i][j]表示：当处理到第i列，且第i列的第j行为’#'（无论是原有的还是新放置的），并且前i列的所有检测器都连通时，需要新增的最少检测器数量。

其中：

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

状态转移

对于位置(i,j)，我们有两种可能的转移来源：

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

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

列i-1    列i
  □ ---- □  (行0)
  |      |
  □ ---- □  (行1)

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

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

列i-1    列i
  # ---- #  (行0)
  |      |
  □      □  (行1)

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

2. 从dp[i-1][1]转移：

列i-1    列i
  □      #  (行0)
  |      |
  # ---- □  (行1)

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

状态转移方程如下：

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

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

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

dp[i][j] = min(dp[i-1][j], dp[i-1][1-j] + (s[i][1-j]=='#'?0:1)) + 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，使得所有检测器连通的最小花费。

代码实现

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+30;

char s[N][2];
int dp[N][2]; // dp[i][j]表示当前第i列第j行为'#'且与前面的检测器连通时的最小花费

void way(){
    string t;
    int n;
    // 数据输入
    for(int j=0;j<2;j++){
        cin>>t;// 读入一个字符串
        n = t.size();
        for(int i=1;i<=n;i++)s[i][j] = t[i-1];
    }

    int st = n+1,en = 0; // 找到左右两边的起始位置（最左边有检测器的位置）和（最右边有检测器的位置）。
    for(int i=1;i<=n;i++){
        if(s[i][0]=='#'||s[i][1]=='#'){
            st = min(i,st);
            en = max(en,i);
        }
    }
    
    // 初始化dp数组
    memset(dp, 0x3f, sizeof(dp)); // 初始化为一个很大的值
    
    // 处理起始位置
    if(s[st][0]=='#') dp[st][0]=0; // 如果已经有检测器，花费为0
    else dp[st][0]=1; // 否则需要放置一个检测器，花费为1
    
    if(s[st][1]=='#') dp[st][1]=0; // 如果已经有检测器，花费为0
    else dp[st][1]=1; // 否则需要放置一个检测器，花费为1
    
    // 如果起始位置两行都有检测器，需要确保它们连通
    if(s[st][0]=='#' && s[st][1]=='#') {
        dp[st][0] = dp[st][1] = 0; // 两个位置都已有检测器，花费为0
    }
    
    for(int i=st+1;i<=en;i++){
        // 计算dp[i][0]
        if(s[i][0]=='#') { // 如果当前位置已有检测器
            // 从上一列转移
            dp[i][0] = min(dp[i-1][0], dp[i-1][1] + (s[i][1]=='#'?0:1));
        } else { // 如果当前位置需要放置检测器
            dp[i][0] = min(dp[i-1][0], dp[i-1][1] + (s[i][1]=='#'?0:1)) + 1;
        }
        
        // 计算dp[i][1]
        if(s[i][1]=='#') { // 如果当前位置已有检测器
            // 从上一列转移
            dp[i][1] = min(dp[i-1][1], dp[i-1][0] + (s[i][0]=='#'?0:1));
        } else { // 如果当前位置需要放置检测器
            dp[i][1] = min(dp[i-1][1], dp[i-1][0] + (s[i][0]=='#'?0:1)) + 1;
        }
    }
    
    cout<<min(dp[en][0],dp[en][1])<<endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    way();
    return 0;
}

示例分析

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

输入：

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

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

列号: 1 2 3 4 5 6 7 8 9
行0:  . # # . . . . . #
行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 2 3 4 5 6 7 8 9
行0:  . # # + + . . . #
行1:  . # . # . # + + .

或者：

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

这两种方案都需要增加5个检测器，使所有检测器连通。