第十六屆藍橋杯大賽軟件賽C/C++大學B組部分題解

第十六屆藍橋杯大賽軟件賽C/C++大學B組題解

試題A: 移動距離

問題描述

小明初始在二維平面的原點，他想前往坐標(233,666)。在移動過程中，他只能采用以下兩種移動方式，并且這兩種移動方式可以交替、不限次數地使用：

水平向右移動，即沿著x軸正方向移動一定的距離。
沿著一個圓心在原點(0,0)、以他當前位置到原點的距離為半徑的圓的圓周移動，移動方向不限（即順時針或逆時針移動不限）。

在這種條件下，他到達目的地最少移動多少單位距離？你只需要輸出答案四舍五入到整數的結果。

解題思路

這個問題可以轉化為：如何從原點到達目標點，使得路徑長度最小。

首先，我們可以觀察到，如果目標點在x軸上，那么直接水平向右移動是最優的。

對于一般情況，我們可以分兩步走：

先沿著x軸正方向移動到點(r,0)，其中r是目標點到原點的距離
然后沿著半徑為r的圓弧移動到目標點

目標點(233,666)到原點的距離為：
r = √(2332 + 6662) = √(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: 可分解的正整數

問題描述

定義一種特殊的整數序列，這種序列由連續遞增的整數組成，并滿足以下條件：

序列長度至少為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是可分解的。請你統計這組數據中可分解的正整數的數量。

解題思路

代碼實現

#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，計算新產值：

金礦新產值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的循環

因此，我們可以先模擬前幾次調整，然后根據情況決定最終結果。

代碼實現

#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;
}

對于樣例輸入：

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) |B2??? - B2?|

其中B_i表示展廳第i個位置上畫作的藝術價值。

現在，他們希望通過精心挑選和排列這M幅畫作，使L達到最小值。請你幫他們計算出這個最小值是多少。

解題思路

這個問題要求我們從N幅畫中選擇M幅，并排列它們，使得相鄰畫作藝術價值平方的差的絕對值之和最小。

首先，我們可以觀察到，對于任意兩幅畫的藝術價值a和b，|a2 - b2| = |a-b|·|a+b|。這意味著，如果我們想要最小化|a2 - b2|，我們應該選擇藝術價值接近的畫作放在相鄰位置。

一個直觀的策略是：

對所有畫作的藝術價值進行排序
選擇M幅連續的畫作（因為連續的畫作藝術價值差異最小）
按照特定順序排列這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]: |22 - 12| = |4 - 1| = 3
[2,4]: |42 - 22| = |16 - 4| = 12
[4,5]: |52 - 42| = |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)，我們有兩種可能的轉移來源：

從(i-1,j)轉移：即上一列同一行的位置
從(i-1,1-j)轉移：即上一列不同行的位置，但這需要通過當前列的另一行(i,1-j)連接

下面用圖示來說明狀態轉移：

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

假設我們當前要計算dp[i][0]（即列i 行0的狀態）：

從dp[i-1][0]轉移：

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

如果(i,0)是’#‘，且(i-1,0)也是’#'，它們自然連通。
如果(i,0)不是’#'，需要放置一個檢測器，花費+1。

從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; // 如果已經有檢測器，花費為0else dp[st][0]=1; // 否則需要放置一個檢測器，花費為1if(s[st][1]=='#') dp[st][1]=0; // 如果已經有檢測器，花費為0else 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個檢測器，使所有檢測器連通。