2023年蓝桥杯第十四届CC++大学B组真题及代码

目录

1A：日期统计

解析代码_暴力_正解

2B：01串的熵

解析代码_暴力_正解

3C：冶炼金属

解析代码_暴力_正解

4D：飞机降落

解析代码_暴力dfs_正解

5E：接龙数列

解析代码_dp_正解

6F：岛屿个数

解析代码_bfs_正解

7G：子串简写

解析代码1_暴力_超时

解析代码2_二分_正解

解析代码3_前缀和_正解

8H：整数删除

解析代码_优先队列+链表_正解

9I：景区导游

解析代码（待续）

10J：砍树

 解析代码（待续）

---

 

题库链接：题库 - 蓝桥云课 (lanqiao.cn)

1A：日期统计（填空5分）

---

解析代码_暴力_正解

答案是235，暴力枚举，别看有八层循环，前4层接近没有，效率也挺高

#include <iostream>
using namespace std;
bool  date_flag[1232]; // 月+日 的范围是 01-01 到 12-31，找到哪个日期，就标记为 true; 
int main()
{int arr[] = { 5, 6, 8, 6, 9, 1, 6, 1, 2, 4, 9, 1, 9, 8, 2, 3, 6, 4, 7, 7, 5, 9, 5, 0, 3, 8, 7, 5, 8, 1, 5, 8, 6, 1, 8, 3, 0, 3, 7, 9, 2,7, 0, 5, 8, 8, 5, 7, 0, 9, 9, 1, 9, 4, 4, 6, 8, 6, 3, 3, 8, 5, 1, 6, 3, 4, 6, 7, 0, 7, 8, 2, 7, 6, 8, 9, 5, 6, 5, 6, 1, 4, 0, 1,0, 0, 9, 4, 8, 0, 9, 1, 2, 8, 5, 0, 2, 5, 3, 3 };//int arr[100] = { 0 };//for (int i = 0; i < 100; ++i)//{//	cin >> arr[i];//}int res = 0;for (int a = 0; a <= 100 - 8; a++) // 2{if (arr[a] != 2)continue;for (int b = a + 1; b <= 100 - 7; b++) // 0{if (arr[b] != 0)continue;for (int c = b + 1; c <= 100 - 6; c++) // 2{if (arr[c] != 2)continue;for (int d = c + 1; d <= 100 - 5; d++) // 3{if (arr[d] != 3)continue;for (int e = d + 1; e <= 100 - 4; e++) // 月份第一个数 {if (arr[e] > 1)continue;for (int f = e + 1; f <= 100 - 3; f++) // 月第二个数 {int month = arr[e] * 10 + arr[f];  // 月份if (month > 12 || month == 0)continue;for (int g = f + 1; g <= 100 - 2; g++) // 日第一个数 {if (arr[g] > 3)continue;for (int h = g + 1; h <= 100 - 1; h++) // 日第二数 {int day = arr[g] * 10 + arr[h]; // 日 if (day > 31 || day == 0)continue; // 需要注意日期合法性，比如2月31日就不合法 int i = month * 100 + day;// printf("2023 %04d\n",i); // 可以输出看一下date_flag[i] = true;}}}}}}}}int ans = 0, uu = 0;for (int i = 101; i < 1231; i++){if (i == 229 || i == 230 || i == 231 || i == 431 || i == 631 || i == 931 || i == 1131) //不合法日期 （2023年不是润年） continue;ans += date_flag[i];}cout << ans << endl;return 0;
}

---

2B：01串的熵（填空5分）

---

解析代码_暴力_正解

        也是暴力枚举，注意公式怎么用代码表示，（当时本人题目都没看懂......）例子中 S = 100长度是3，所以加了3次，1的占比是1/3，0的占比是2/3，xi就是0或1。

#include <iostream>
#include <cmath>
using namespace std;int main()
{// 设 有 x 个 ‘0’ 和 y 个 ‘1’ ；则有x+y= 23333333,即 y=23333333-x , // 因为题目告诉了  0 出现次数比 1 少，也即是 x<=23333333/2 ,// ‘0’占比 x/(x+y)，‘1’占比 y/(x+y)  // 计算机最不怕的就是麻烦，开找double Hs = 11625907.5798;for (double x = 23333333 / 2; x >= 1; x--) // x应该很大，所以反过来循环 {double y = 23333333 - x;double p0 = x / (x + y);double p1 = y / (x + y); // p1=1.0-p0; double result = x * (-p0 * (log(p0) / log(2))) + y * (-p1 * (log(p1) / log(2)));// 上面公式是x个前面的，y个后面的，log是求e为底的对数，然后用换底公式if (11625907.5797 < result && result < 11625907.5799)  // 精度问题，没办法用等于 {printf("%.0f", x);break;//printf("x=%f  result=%f\n", x, result);}}return 0;
}

---

3C：冶炼金属（编程10分）

---

解析代码_暴力_正解

// 23年C冶炼金属
#include <iostream>#define int long long
#define endl '\n'
using namespace std;const int INF = 0x3f3f3f3f;signed main() // 10分题，没那么复杂，很简单，每次都判断可去范围就好了 
{ios::sync_with_stdio(0); // 关流cin.tie(0);cout.tie(0);int V_max = INF, V_min = -INF;int N = 0;cin >> N;while (N--){int A = 0, B = 0;cin >> A >> B;// A 中 V 个普通的金属提炼出 1 个特殊金属，总A个能提炼出B个// 75 -> 3// 75 / 3 = 25 // 最大消耗中的最小值// 75 / 4 + 1 = 19// 53 -> 2// 53 / 2 = 26.5// 53 / 3 + 1 = 18// 59 -> 2// 59 / 2 = 29.5// 59 / 3 + 1 = 20 // 所有最小消耗中最大值int Vmin = A / (B + 1) + 1; // 本次中，冶炼一个特殊金属至少消耗 Vmin 才能满足本次冶炼 B 个的条件 int Vmax = A / B; // 本次中，冶炼一个特殊金属最多消耗 Vmax 才能满足本次冶炼 B 个的条件V_min = max(V_min, Vmin); // 所有最小消耗中取最大值才能都满足 V_max = min(V_max, Vmax);	// 所有最大消耗中取最小值才能都满足}cout << V_min << " " << V_max << endl;return 0;
}

---

4D：飞机降落（编程10分）

---

解析代码_暴力dfs_正解

// 23年D_飞机降落 ： 暴力枚举DFS
// #include<bits/stdc++.h>
#include<iostream>
#define int long long
using namespace std;
const int N = 10 + 7;
bool check[N]; // 判断当前飞机是否已经降落
int n; // 飞机个数。struct plane
{int t, d, l;
}p[N];// u表示已经有U架飞机成功降落了
// time表示当前的时间，前一架飞机落地的时间
bool dfs(int u, int time)
{if (u >= n)return true;// 考虑第（u + 1）架飞机谁落for (int i = 0; i < n; i++){if (!check[i]){check[i] = true;if (p[i].t + p[i].d < time){check[i] = false; // 回溯到DFS之前的状态return false;}int t = max(time, p[i].t) + p[i].l;if (dfs(u + 1, t))return true;elsecheck[i] = false; // 回溯到DFS之前的状态}}return false;
}void solve()
{cin >> n;for (int i = 0; i < n; i++){cin >> p[i].t >> p[i].d >> p[i].l;}if (dfs(0, 0))cout << "YES" << endl;elsecout << "NO" << endl;for (int i = 0; i < n; i++){check[i] = false;}
}
signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t = 1;cin >> t;while (t--){solve();}return 0;
}
/*
2
3
0 100 10
10 10 10
0 2 20
3
0 10 20
10 10 20
20 10 20
*/

---

5E：接龙数列（编程15分）

---

解析代码_dp_正解

动态规划代码：p[i] 表示以i位置为结尾最长的接龙子序列的长度。

p[i][j] 表示以i位置为结尾最长的接龙子序列的长度，最后一位数字是j，j>=0 && j <= 9

// 23年E_接龙序列
// #include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#define int long long
const int INF = 0x3f3f3f3f;
using namespace std;int get_first(int x)
{int tmp = x, ret = 0;while (tmp){ret = tmp % 10;tmp /= 10;}return ret;
}int get_last(int x)
{return x % 10;
}signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// dp[i] 表示以i位置为结尾最长的接龙子序列的长度// dp[i][j] 表示以i位置为结尾最长的接龙子序列的长度，最后一位数字是j，j>=0 && j <= 9int n = 0;cin >> n;vector<int> arr(n + 1);for (int i = 1; i <= n; ++i){cin >> arr[i];}vector<vector<int>> dp(n + 20, vector<int>(20));for (int i = 1; i <= n; ++i){for (int j = 0; j <= 9; ++j){// 不选/删除第i个数字dp[i][j] = dp[i - 1][j] + 1;}// 选/保留第i个数字int last = get_last(arr[i]);int first = get_first(arr[i]);dp[i][last] = min(dp[i - 1][first], dp[i][last]);}int ret = INF;for (int i = 0; i < 10; i++){ret = min(ret, dp[n][i]);}cout << ret << endl;return 0;
}

 

---

6F：岛屿个数（编程15分）

---

解析代码_bfs_正解

// 23年F_岛屿个数：从所有的外海点出发做BFS，遇到陆地后就做DFS
// #include<bits/stdc++.h>
#include <iostream>
#include <queue>
#define int long long
using namespace std;int dx[4] = { 0, 0 , -1, 1 }; // i点加dx，dy就是i点的上下左右下标
int dy[4] = { 1, -1 , 0, 0 };
int dx2[8] = { 0, 0 , -1, 1 , -1, 1,-1, 1 }; // i点加dx，dy就是i点的上下左右下标
int dy2[8] = { 1, -1 , 0, 0 , -1, 1, 1, -1 };
int m = 0, n = 0, res = 0;bool vis0[55][55];
bool vis1[55][55];void dfs(vector<vector<int>>& arr, int sr, int sc)
{//queue<pair<int, int>> q; // BFS版//q.push({ sr, sc });//vis1[sr][sc] = true;//while (!q.empty())//{//	auto& tmp = q.front();//	auto a = tmp.first;//	auto b = tmp.second;//	q.pop();//	for (int i = 0; i < 4; ++i)//	{//		int x = a + dx2[i], y = b + dy2[i];//		if (x >= 0 && x < m && y >= 0 && y < n && arr[x][y] == 1 && !vis1[x][y]) // DFS陆地//		{//			vis1[x][y] = true;//			q.push({ x, y });//		}//	}//}vis1[sr][sc] = true;for (int i = 0; i < 4; ++i){int x = sr + dx[i], y = sc + dy[i];if (x >= 0 && x < m && y >= 0 && y < n && arr[x][y] == 1 && !vis1[x][y]){vis1[x][y] = true;dfs(arr, x, y);}}
}void bfs(vector<vector<int>>& arr, int sr, int sc)
{queue<pair<int, int>> q;q.push({ sr, sc });vis0[sr][sc] = true;while (!q.empty()){auto& tmp = q.front();auto a = tmp.first;auto b = tmp.second;q.pop();for (int i = 0; i < 8; ++i){int x = a + dx2[i], y = b + dy2[i];if (x >= 0 && x < m && y >= 0 && y < n && arr[x][y] == 0 && !vis0[x][y]) // BFS海洋{vis0[x][y] = true;q.push({ x, y });}if (x >= 0 && x < m && y >= 0 && y < n && arr[x][y] == 1 && !vis1[x][y]) // 找陆地{++res;dfs(arr, x, y);}}}
}signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int N = 0;cin >> N;while (N--){cin >> m >> n;vector<vector<int>> arr(m, vector<int>(n));for (int i = 0; i <= n; i++)for (int j = 0; j <= m; j++)vis0[i][j] = vis1[i][j] = false;for (int i = 0; i < m; ++i){string tmp;cin >> tmp;for (int j = 0; j < n; ++j){arr[i][j] = tmp[j] - '0';}}bool flag = false;for (int i = 0; i < n; ++i) // 从外海点出发做bfs找陆地{if (arr[0][i] == 0){bfs(arr, 0, i);flag = true;}if (arr[m - 1][i] == 0){bfs(arr, m - 1, i);flag = true;}}for (int i = 0; i < m; ++i){if (arr[i][0] == 0){bfs(arr, i, 0);flag = true;}if (arr[i][n - 1] == 0){bfs(arr, i, n - 1);flag = true;}}if (!flag) // 如果外围全是岛{cout << 1 << endl;}else{cout << res << endl;res = 0;}}return 0;
}
/*
2
5 5
01111
11001
10101
10001
11111
5 6
111111
100001
010101
100001
111111
*/

---

7G：子串简写（编程20分）

---

解析代码1_暴力_超时

23年G子串简写
// 暴力法（超时）
#include <iostream>
#include <string>
#define int long long
#define endl '\n'
using namespace std;signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int k = 0;string str;char c1, c2;cin >> k >> str >> c1 >> c2;int sz = str.size(), ret = 0;for (int i = 0; i < sz; ++i){if (str[i] != c1)continue;for (int j = k - 1; j < sz; ++j){if (str[j] != c2)continue;if (j - i + 1 >= k)++ret;}}cout << ret << endl;return 0;
}

---

解析代码2_二分_正解

23年G子串简写
// 正解：二分
//#include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <vector>
#define int long long
#define endl '\n'
using namespace std;signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int k = 0;string str;char c1, c2;cin >> k >> str >> c1 >> c2;int sz = str.size(), ret = 0;vector<int> arr;arr.reserve(sz);for (int i = 0; i < sz; ++i){if (str[i] == c1){arr.push_back(i); // 存c1的下标}if (str[i] == c2) // 二分找前面k个长度外有多少个c1（找右端点）{if (i - k + 1 < 0 || !arr.size())continue;int left = 0, right = (int)arr.size() - 1;while (left < right){int mid = left + right + 1 >> 1;if (arr[mid] <= (i - k + 1))left = mid;elseright = mid - 1;}if (arr[right] <= i - k + 1)ret += (right + 1);}}cout << ret << endl;return 0;
}

---

解析代码3_前缀和_正解

23年G子串简写
// 正解：前缀和
//#include <bits/stdc++.h>
#include <iostream>
#include <string>
#define int long long
#define endl '\n'
using namespace std;signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int k = 0;string str;char c1, c2;cin >> k >> str >> c1 >> c2;int sz = str.size(), ret = 0;int sum_c1 = 0;for (int i = 0, j = k - 1; i < sz && j < sz; ++i, ++j){if (str[i] == c1)++sum_c1;if (str[j] == c2)ret += sum_c1;}cout << ret << endl;return 0;
}

---

8H：整数删除（编程20分）

---

解析代码_优先队列+链表_正解

//整数删除：优先队列 + 模拟链表
// #include<bits/stdc++.h>
#include <iostream>
#include <queue>
#define int long long
#define endl '\n'
using namespace std;
typedef pair<int, int> pii;
const int N = 5e5 + 10;
int arr[N], l[N], r[N]; // l[i]和r[i]分别表示i左边和右边的数字的下标
int st[N];
void solve()
{int n = 0, k = 0; cin >> n >> k;priority_queue<pii, vector<pii>, greater<pii>>q;for (int i = 0; i < n; i++){cin >> arr[i];q.push({ arr[i], i });st[i] = arr[i];l[i] = i - 1;r[i] = i + 1;if (r[i] == n)r[i] = -1;}while (k){pii t = q.top();q.pop();if (t.first != st[t.second]){q.push({ st[t.second], t.second });continue;}--k;int pos = t.second; // 获取该元素在原数组中的位置if (l[pos] >= 0) // 将该元素的相邻元素加上该数值st[l[pos]] += t.first;if (r[pos] >= 0)st[r[pos]] += t.first;if (l[pos] >= 0) // 更新相邻点的相邻元素r[l[pos]] = r[pos];if (r[pos] >= 0)l[r[pos]] = l[pos];st[pos] = -1; // 该元素已经被删除，打标记}for (int i = 0; i < n; ++i){if (st[i] != -1)cout << st[i] << " ";}cout << endl;
}signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);solve();return 0;
}

---

9I：景区导游（编程25分）

---

解析代码（待续）

（待续）

---

10J：砍树（编程25分）

---

 解析代码（待续）

（待续）