【第15届蓝桥杯C/C++B组】试题&参赛经历&经验&个人题解_十五届c++b组蓝桥杯答案

试题 A: 握手问题

我的答案

#include<iostream>
#include<vector>
using namespace std;
int Solution()
{
	int ans=0;
	for(int i=49;i>=7;--i){
		ans+=i;
		cout<<i<<endl;
	}	
	return ans;//1204
}
int main()
{
	cout<<Solution();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

GPT答案

这个问题可以用组合数学的知识来解决。

首先，总共有 50 个人，每个人要与除自己以外的其他所有人进行一次握手，那么总的握手次数为 (502)(250)。

但是有 7 个人彼此之间没有进行握手，这意味着这 7 个人之间本应该进行 (72)(27) 次握手，但是实际上没有进行握手。

所以最终的握手次数为 (502)−(72)(250)−(27)。

计算结果为：

(502)−(72)=50×492−7×62=1225−21=1204(250)−(27)=250×49−27×6=1225−21=1204

所以最终答案为 1204。

试题 B: 小球反弹

我的答案

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
long double Solution()
{
	long double length=343720.0,width=233333.0;
	long double dx=15.0,dy=17.0;
	long double step=411764.1176470588;//411764
	int t=0;
	long double dist=0;
	while(true){
		t++;
		dist+=step;
		
		while(dist>length+3){
			dist-=length;
		}
		if(abs(dist-length)<0.0001)
		break;
	}
	cout<<"t="<<t<<endl;
	cout<<"dist="<<dist<<endl;
	
	int x=15*15;
	int y=17*17;
	int x_y=x+y;
	double k=sqrt(x_y);
	long double total=t*step;
	cout<<"total="<<total<<endl;
	cout<<"k="<<k<<endl;
	long double ans=total*k/dx;
	
	cout<<endl;
	return ans;
}
int main()
{
	cout<<fixed<<Solution();//550162599.885198
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

这题由于太复杂gpt算不了，就不给出gpt的生成内容了

试题 C: 好数

我的答案

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int Solution()
{
	int n;
	cin>>n;
	int ans=0;
	for(int i=1;i<=n;i+=2)
	{
		int dont=0;
		int t=i;
			bool add=true;
		while(t>0){
			int wei=t%10;
			wei%=2;
			if(wei==dont)
			{
				add=false;
				break;
			}
			dont=wei;
			t/=10;
		}
		if(add)
			ans++;
	}
	return ans;
}
int main()
{
	cout<<Solution();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

GPT的评价

这段代码试图统计从 1 到给定的正整数 n 之间的好数的数量。在这段代码中，它使用了一个名为 Solution 的函数来计算好数的数量。

这段代码的思路是从 1 开始遍历到 n，对每个数字进行判断是否为好数。在判断是否为好数时，它使用了一个布尔变量 add 来表示当前数字是否为好数，并在遍历数字的每一位时进行更新。具体来说，它遍历了每个数字的每一位，如果相邻位上的数字奇偶性相同（即相邻位都是奇数或者都是偶数），则将 add 设置为 false，表示当前数字不是好数，否则将 add 设置为 true，表示当前数字是好数。最后统计所有好数的数量并返回。

这段代码的逻辑是正确的，可以用于计算好数的数量。但是，它的时间复杂度较高，因为对于每个数字，需要遍历其每一位来判断奇偶性。当 n 很大时，这种方法会很慢。在实际应用中，我们通常会选择更高效的算法来解决这个问题，比如动态规划。

GPT给出的答案

我们可以使用动态规划来解决这个问题。定义一个二维数组 dp[i][j]，其中 i 表示数字的位数，j 表示最高位数字。dp[i][j] 表示在位数为 i 时，最高位数字为 j 的好数的数量。

首先，我们需要确定状态转移方程。假设 i 位数的好数数量为 dp[i]，则有以下几种情况：

1. 如果当前位数是奇数位（个位、百位、万位…），那么当前位数的好数数量取决于前一位偶数位的好数数量，因为无论前一位的数字是什么，当前位都可以选择奇数位的数字（1、3、5、7、9）。
2. 如果当前位数是偶数位（十位、千位、十万位…），那么当前位数的好数数量取决于前一位奇数位的好数数量，因为无论前一位的数字是什么，当前位都可以选择偶数位的数字（0、2、4、6、8）。

根据以上分析，我们可以得出状态转移方程：

dp[i][j] = dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3] + dp[i - 1][4] + dp[i - 1][5] + dp[i - 1][6] + dp[i - 1][7] + dp[i - 1][8] + dp[i - 1][9]
1

其中，如果当前位数是奇数位，则 dp[i][j] 只与前一位偶数位的好数数量有关；如果当前位数是偶数位，则 dp[i][j] 只与前一位奇数位的好数数量有关。

最后，我们将所有位数为奇数位或偶数位的好数数量相加，即为从 1 到 N 之间的好数的数量。

#include <iostream>
#include <vector>
using namespace std;

// 计算从 1 到 N 之间的好数的数量
int countGoodNumbers(int N) {
    const int MOD = 1e9 + 7;
    // 初始化 dp 数组
    vector<vector<long long>> dp(20, vector<long long>(10, 0));
    // 初始条件：1 位数时，好数的数量为 5（1、3、5、7、9）
    for (int j = 1; j <= 9; ++j) {
        dp[1][j] = 1;
    }
    // 动态规划计算好数的数量
    for (int i = 2; i <= 19; ++i) {
        for (int j = 1; j <= 9; ++j) {
            if (i % 2 == 1) { // 当前位数为奇数位
                // 前一位是偶数位的好数数量
                for (int k = 0; k <= 9; k += 2) {
                    dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MOD;
                }
            } else { // 当前位数为偶数位
                // 前一位是奇数位的好数数量
                for (int k = 1; k <= 9; k += 2) {
                    dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MOD;
                }
            }
        }
    }
    // 计算好数的总数量
    long long ans = 0;
    for (int i = 1; i <= 19; ++i) {
        for (int j = 1; j <= 9; ++j) {
            ans = (ans + dp[i][j]) % MOD;
        }
    }
    return ans;
}

int main() {
    int N;
    cin >> N;
    cout << countGoodNumbers(N) << endl;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

试题 D：R 格式

我的思路

这题不会写，没办法了，直接暴力。感觉应该是用高精度来实现，但是我忘了高精度乘法咋写了…

我的代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
void Solution()
{
	int n;
	long double d;
	cin>>n>>d;
	long double val=pow(2,n);
	long long result=d*val+0.5f;
	
	cout<<result;
}
int main()
{
	Solution();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

GPT写的跟我一样，都是错误答案

试题 E：宝石组合

$$S=H_a{H}_b{H}_c\cdot \frac{LCM(H_a,H_b,H_c)}{LCM(H_a,H_b)\cdot LCM(H_a,H_c)\cdot LCM(H_b,H_c)}$$

我的思路

​ 本来想用哈希表来剪枝，不知道为什么当时没写出来，一直报错，devc++我又不知道哪里错了，没办法 反正也是骗分，直接暴力了。

GPT的思路和我的一样，都是：

1.先对宝石的 “闪亮度” 进行排序，从小到大排列。

2.枚举所有可能的三种宝石组合，可以采用三重循环来实现，其中第一个循环选择第一种宝石，第二个循环选择第二种宝石，第三个循环选择第三种宝石。

3.对于每种组合，计算它们的精美程度。精美程度可以定义为三种宝石的乘积除以它们的最小公倍数。最小公倍数可以通过最大公约数来求得。

我的答案

#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_map>
#include<map>
#include<utility>
using namespace std;
int gcd(int a,int b){
	if(!b)
		return a;
	return gcd(b,a%b);
}
int lcm(int a,int b){
	return a/gcd(a,b)*b;
}
void Solution()
{
	int n;
	cin>>n;
	vector<int>g(n);
	for(int &a:g)
		cin>>a;
	sort(g.begin(),g.end());
	int a=0,b=0,c=0;
	int maxx=0;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(j!=i)
			{
				for(int k=0;k<n;k++){
					if(k!=j&&k!=i)
					{
						int q,w,e,r;
						
						q=lcm(g[i],g[j]);
						w=lcm(g[i],g[k]);
						e=lcm(g[j],g[k]);
						r=lcm(q,g[k]);
						int tem=g[i]*g[j]*g[k]*r/q/w/e;
						if(tem>maxx){
							maxx=tem;
							a=g[i];
							b=g[j];
							c=g[k];
						}
					}
				}
			}
		}
	}
	cout<<a<<' '<<b<<' '<<c;
	return;
}
int main()
{
	Solution();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

试题F：数字接龙

我的思路

​ 一眼是图论的题，再看一眼以为是普通的DFS或者BFS，最后想好决定使用DFS解决。第一印象感觉没啥难的，但是中间有一个不可以出现交叉的线路，这个设定卡了我很久，最后才想到使用set来纪录是否交叉，感觉最后的答案会超出时间复杂度或者内存，但是样例能过。这个题是我考试时候写的第三题，写了快一个多小时才写完。当时都想放弃了，还有点后悔学过图论，因为图论的题都是一步错就全错，非常耽误时间。

我的代码

#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<set>
#include<utility>
using namespace std;
string Solution()
{
	vector<vector<int>>move{{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0}};
	int n,k;
	cin>>n>>k;
	int totalsize=n*n-1;
	vector<vector<int>>g(n,vector<int>(n));
	for(auto &a1:g)
		for(auto &a2:a1)
			cin>>a2;
	vector<vector<bool>>vis(n,vector<bool>(n,false));
	set<pair<double,double>>st;
	string ans="";
	function<void(int,int,string)>dfs=[&](int i,int j,string s){
		if(s.size()==totalsize){
			if(i==n-1&&j==n-1)
			{
				if(ans==""||!lexicographical_compare(ans.begin(),ans.end(),s.begin(),s.end()))
					ans=s;
			}
			return;
		}
		int nxt=(g[i][j]+1)%k;
		for(int u=0;u<8;u++)
		{
			int x=i+move[u][0];
			int y=j+move[u][1];
			if(x>=0&&x<n&&y>=0&&y<n&&!vis[x][y]&&g[x][y]==nxt)
			{
				if(u%2==1)
				{
					double rx=i+move[u-1][0];
					double ry=j+move[u-1][1];
					double lx=i+move[u+1][0];
					double ly=j+move[u+1][1];
					double tx=(rx+lx)/2.0;
					double ty=(ry+ly)/2.0;
					pair<double,double>insp;
					insp.first=tx;
					insp.second=ty;
					auto it=st.find(insp);
					if(it!=st.end())
						continue;
					else
					{
						st.insert(insp);
						vis[x][y]=true;//与下面重复了 
						char fr='0'+u;
						string tem=s+fr;
						dfs(x,y,tem);
						st.erase(insp);
						vis[x][y]=false;
					}
				}
				else
				{
					vis[x][y]=true;
					char fr='0'+u;
					string tem=s+fr;
					dfs(x,y,tem);
					vis[x][y]=false;
				}
			}
		}
	};
	if(n==1)
		return "";
	vis[0][0]=true;
	dfs(0,0,"");	
	return ans==""?"-1":ans;
}
//F
/*
3 3
0 2 0
1 1 1
2 0 2
*/
int main()
{	
	cout<<Solution();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

GPT的点评

这段代码实现了对数字接龙问题的求解，通过深度优先搜索（DFS）来找到符合条件的路径。具体来说，它遍历了从起点到终点的所有可能路径，并使用一个集合 st 来记录已经访问过的格子，以避免重复访问。在搜索过程中，通过递归调用 dfs 函数，不断更新路径，并根据规则判断下一步可以移动到哪个格子。如果找到了满足条件的路径，则将其记录下来，并在搜索结束后输出。

总体来说，这段代码是一个较为合理的实现，应该能够成功解决数字接龙问题。

GPT的代码

要解决数字接龙问题，可以采用深度优先搜索（DFS）的方法来寻找路径。具体步骤如下：

1. 从左上角 (0, 0) 出发，向右下方向进行搜索。
2. 在每个格子上，尝试所有可能的移动方向，并检查是否满足接龙规则。
3. 使用递归深度优先搜索，直到找到一条满足条件的路径或者搜索到底部无法继续。
4. 注意记录已经访问过的格子，避免重复访问。

下面是基于上述思路的代码实现：

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

// 定义八个方向的移动向量
const int dx[] = {1, 1, 0, -1, -1, -1, 0, 1};
const int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};

// 检查移动是否在边界内
bool isValid(int x, int y, int N) {
    return x >= 0 && x < N && y >= 0 && y < N;
}

// 深度优先搜索函数
bool dfs(vector<vector<int>>& board, vector<vector<bool>>& visited, int x, int y, int K, string& path) {
    if (path.length() == K) // 已经找到一条路径
        return true;

    for (int i = 0; i < 8; ++i) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (isValid(nx, ny, board.size()) && !visited[nx][ny] && board[nx][ny] == (path.length() % K)) {
            visited[nx][ny] = true;
            path.push_back('0' + board[nx][ny]);
            if (dfs(board, visited, nx, ny, K, path))
                return true;
            path.pop_back();
            visited[nx][ny] = false;
        }
    }
    return false;
}

// 主函数，解决数字接龙问题
string solve(vector<vector<int>>& board, int N, int K) {
    vector<vector<bool>> visited(N, vector<bool>(N, false));
    string path;
    visited[0][0] = true;
    path.push_back('0' + board[0][0]);
    if (dfs(board, visited, 0, 0, K, path))
        return path;
    else
        return "-1";
}

int main() {
    int N, K;
    cin >> N >> K;
    vector<vector<int>> board(N, vector<int>(N));
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            cin >> board[i][j];

    cout << solve(board, N, K) << endl;

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

试题G：爬山

我的思路

​ 一眼动态规划。但是由于前面图论浪费了太多时间，剩余时间肯定写不完。没办法只能使用优先队列+贪心来实现了。测试用例能过，应该能骗点分。

我的代码

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
int Solution()
{
	int n,P,Q;
	cin>>n>>P>>Q;
	
	priority_queue<int,vector<int>>pq;
	for(int i=0;i<n;i++)
	{
		int a;
		cin>>a;
		pq.push(a);
	}
	for(int i=0;i<P;i++){
		int val=pq.top();
		pq.pop();
		val=sqrt(val);
		pq.push(val);
	}
	for(int i=0;i<Q;i++){
		int val=pq.top();
		pq.pop();
		val/=2;
		pq.push(val);
	}
	
	int ans=0;
	while(!pq.empty())
	{
		ans+=pq.top();
		pq.pop();
	}
	return ans;
	
}
int main()
{
	cout<<Solution();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

GPT的思路

这个问题可以使用动态规划来解决。我们可以定义一个二维数组 dp[i][j]，其中 dp[i][j] 表示前 i 座山使用 P 次第一种魔法和 Q 次第二种魔法时，总体力消耗的最小值。然后我们可以根据当前山的高度以及剩余魔法使用次数进行状态转移，最后得到的 dp[n][P][Q] 就是答案。

具体的状态转移方程如下：

• 对于每座山，我们有两种选择：不使用魔法或者使用第一种或第二种魔法。
• 如果我们选择不使用魔法，则当前山的高度就是 h[i]，体力消耗为 dp[i-1][j][k] + h[i]。
• 如果我们选择使用第一种魔法，则当前山的高度变为 ⌊√h[i]⌋，体力消耗为 dp[i-1][j-1][k] + ⌊√h[i]⌋。
• 如果我们选择使用第二种魔法，则当前山的高度变为 ⌊h[i]/2⌋，体力消耗为 dp[i-1][j][k-1] + ⌊h[i]/2⌋。

最后我们在所有可能的选择中选取体力消耗最小的值作为 dp[i][j][k] 的值。

下面是代码实现：

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

int main() {
    int n, P, Q;
    cin >> n >> P >> Q;
    vector<int> h(n);
    for (int i = 0; i < n; ++i) {
        cin >> h[i];
    }

    vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(P + 1, vector<int>(Q + 1, 0)));

    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= P; ++j) {
            for (int k = 0; k <= Q; ++k) {
                // 不使用魔法
                dp[i][j][k] = dp[i - 1][j][k] + h[i - 1];
                // 使用第一种魔法
                if (j > 0) {
                    int new_height = sqrt(h[i - 1]);
                    dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j - 1][k] + new_height);
                }
                // 使用第二种魔法
                if (k > 0) {
                    int new_height = h[i - 1] / 2;
                    dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j][k - 1] + new_height);
                }
            }
        }
    }

    cout << dp[n][P][Q] << endl;

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

试题H：拔河

我的思路

​ 当时做的时候读错题了，以为编号不连续，最后随便写了个答案交了。这没办法，代码就不展示了。

GPT的答案

这个问题可以使用动态规划来解决。首先，我们需要计算出所有可能的子数组的力量值之和，并保存下来。然后，我们可以使用动态规划来找到两个力量值之和尽可能接近的两个子数组。

具体步骤如下：

1. 遍历数组，计算每个子数组的力量值之和，保存在一个二维数组中。
2. 对于每个子数组，计算其力量值之和与前面所有子数组的力量值之和的差值，并保存在一个新的二维数组中。
3. 使用动态规划来找到力量值之和尽可能接近的两个子数组。可以定义一个二维数组 dp，其中 dp[i][j] 表示在前 i 个子数组中，选取 j 个子数组时的最小力量值之和差距。
4. 动态规划的状态转移方程为：dp[i][j] = min(dp[i-1][j], abs(sum[i] - sum[k] - dp[k][j-1]))，其中 sum[i] 表示前 i 个子数组的力量值之和，k 为从 j-1 到 i-1 的遍历。
5. 最终的答案即为 dp[n][2]。

下面是实现代码：

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

int minPowerDifference(vector<int>& powers) {
    int n = powers.size();
    // 计算每个子数组的力量值之和
    vector<int> sum(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        sum[i] = sum[i - 1] + powers[i - 1];
    }

    // 计算力量值之和的差值并保存
    vector<vector<int>> diff(n + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= n; ++i) {
        for (int j = i; j <= n; ++j) {
            diff[i][j] = sum[j] - sum[i - 1];
        }
    }

    // 动态规划找到力量值之和尽可能接近的两个子数组
    vector<vector<int>> dp(n + 1, vector<int>(3, INT_MAX / 2));
    dp[0][0] = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= 2; ++j) {
            for (int k = j - 1; k <= i - 1; ++k) {
                dp[i][j] = min(dp[i][j], abs(diff[i][i] - dp[k][j - 1]));
            }
        }
    }

    return dp[n][2];
}

int main() {
    int n;
    cin >> n;
    vector<int> powers(n);
    for (int i = 0; i < n; ++i) {
        cin >> powers[i];
    }
    cout << minPowerDifference(powers) << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

我的感想

​ 蓝桥杯结束了，学了这么久的算法，虽然写的不是特别好，大多都是直接暴力，但是希望能进国赛吧。感觉这次出的题比去年的要简单，图论那道题其实直接输出-1都能骗不少分。学了好久的动态规划居然一道题也没写。感觉爬山这题应该是能写的，很普通的动态规划而已。最后拿什么奖我在评论区里面说。