第十四届蓝桥杯c++组B组做题笔记

本文主要是介绍第十四届蓝桥杯c++组B组做题笔记，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A题：日期统计：

【问题描述】
小蓝现在有一个长度为 100 的数组，数组中的每个元素的值都在 0 到 9 的范围之内。数组中的元素从左至右如下所示：
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
现在他想要从这个数组中寻找一些满足以下条件的子序列：

子序列的长度为 8；
这个子序列可以按照下标顺序组成一个 yyyymmdd 格式的日期，并且
要求这个日期是 2023 年中的某一天的日期，例如 20230902，20231223。
yyyy 表示年份，mm 表示月份，dd 表示天数，当月份或者天数的长度只
有一位时需要一个前导零补充。
请你帮小蓝计算下按上述条件一共能找到多少个不同 的 2023 年的日期。
对于相同的日期你只需要统计一次即可。

笔记：

这道题采用暴力的解法，从数组开头开始前四位作为年份接下来两位作为月份做后两位作为日期，这里需要将子序列转换成对应的日期格式。

这里有学习了一种写法：将一个整数数组转化成一个字符串：

#include <iostream>
#include <sstream>int main() {int arr[] = {1, 2, 3, 4, 5};const int size = sizeof(arr) / sizeof(arr[0]);// 使用 stringstream 将 int 转换为 stringstd::ostringstream oss;for (int i = 0; i < size; ++i) {oss << arr[i];}std::string result = oss.str();std::cout << result << std::endl;return 0;
}

这个程序首先创建一个 std::ostringstream 对象 oss，然后遍历整数数组 arr，将每个整数写入到 oss 中。最后，通过调用 oss.str() 将 oss 中的内容转换为一个 std::string 类型的字符串。需要注意的是，这种方法会把整数转换为字符串后直接拼接起来，而不会有任何分隔符。如果需要添加分隔符，例如逗号或空格，你可以在每次循环中添加相应的分隔符。

但这些写法有点僵简单问题复杂化：

这里给出一种思路，首先我们创建一个int类型静态数组将题干数据存入数组中，接着将该静态数组的内容复制到动态数组上：

int arr[] = {2, 0, 2, 3, 0, 3, 2, 8, 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};std::vector<int> array(arr, arr + sizeof(arr) / sizeof(arr[0]));

接着我们创建一个int类型的函数返回最终结果，该函数内我们传入动态数组array，使用一个for循环从数组的开头遍历到最后一个日期数据的开头也就是末尾-8的位置，然后我们利用subsequence函数将日期串分割出来，使用一个判断函数判断该字符串是否合法。

int countUniqueDates(const std::vector<int>& array) {std::set<std::vector<int> > uniqueDates;for (size_t i = 0; i <= array.size() - 8; ++i) {std::vector<int> subsequence(array.begin() + i, array.begin() + i + 8);if (isValidDate(subsequence)) {uniqueDates.insert(subsequence);}}return uniqueDates.size();
}

这里我们需要注意的电视我们存储结果的容器要使用set容器应为可以自动去重，这里for循环的索引可以使用int代替，这里介绍一下size_t：size_t 是 C/C++ 中的一种数据类型，通常用于表示内存中对象的大小或索引，以及用于存储任何可能会返回的数组或容器的大小。

接着我们来编写判断函数：

这里我们传入日期串，我们将其中的年、月、日提取出来即可，提取出来之后我们只需要对不合法的情况进行判断即可因为合法的情况太繁杂：

bool isValidDate(const std::vector<int>& subsequence) {int year = subsequence[0] * 1000 + subsequence[1] * 100 + subsequence[2] * 10 + subsequence[3];int month = subsequence[4] * 10 + subsequence[5];int day = subsequence[6] * 10 + subsequence[7];if (year != 2023)return false;if (month < 1 || month > 12 || day < 1 || day > 31)return false;if (month == 2) {if (day > 28)return false;} else if (month == 4 || month == 6 || month == 9 || month == 11) {if (day > 30)return false;}return true;
}

但是这则代码的逻辑是错误的，因为子串比不仅限于连续的八位，所以我们的思路还是错了，我们可以进行八次for循环，前四次锁定2023这个前缀，接下来连续四次循环将这四个数进行组合，判断这个日期是否合法：

#include <bits/stdc++.h>
using namespace std;set<int> res;void check(int x, int y) {if (x > 12 || y > 31) return;if ((x == 1 || x == 3 || x == 5 || x == 7 || x == 8 || x == 10 || x == 12) && y <= 31) {res.insert(x * 100 + y);}if ((x == 4 || x == 6 || x == 9 || x == 11) && y <= 30) {res.insert(x * 100 + y);}if (x == 2 && y <= 28) {res.insert(x * 100 + y);}
}int main() {int a[] = {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};for (int i = 0; i < 100; i++) {if (a[i] != 2) continue;for (int j = i; j < 100; j++) {if (a[j] != 0) continue;for (int k = j; k < 100; k++) {if (a[k] != 2) continue;for (int l = k; l < 100; l++) {if (a[l] != 3) continue;for (int m = l; m < 100; m++) {for (int n = m; n < 100; n++) {for (int o = n; o < 100; o++) {for (int p = o; p < 100; p++) {check(a[m] * 10 + a[n], a[o] * 10 + a[p]);}}}}}}}}cout << res.size() << endl;return 0;
}

B题：01串的熵：

笔记：

这道题注意的点是对于数据类型的把控，int能到2^10，但尽量我们使用longlong类型来处理大数据，第一个点：定义类型别名：我们使用typedef的方法来进行定义：

typedef long long ll;

然后对于公式，我们注意到h是一个浮点数为了方便处理，我们将h处理为整数，直接将其乘以10的n次方消去小数点，然后我们开始列公式，这个公式中存在p0，p1两个概率值是浮点数，而我们所求的h是一个longlong类型的数据，所以我们需要将这两个概率值单列出来求解，采用double类型处理这两个数据，然后再带入公式中，这里我们的概率是有两个longlong类型的数据相除得到的，所以我们为了得到的数据是double类型的，我们需要在对其中一个数据 * 1.0使其变为double类型的数据。

#include <iostream>
#include <cmath>const long long H = 116259075798;
const long long L = 23333333;bool check(long long x) {double p0 = x * 1.0 / L;double p1 = 1 - p0;long long h = (x * p0 * log2(p0) + (L - x) * p1 * log2(p1)) * 10000;return H + h == 0;  // 这里改成 H - h == 0
}int main() {for (long long i = 0; i <= L / 2; i++) {if (check(i)) {std::cout << i << std::endl;}}return 0;
}

C：冶炼金属：

这个题就比较简单了直接就是用A / B 找出最小的那个值作为上界，然后再用A / (B + 1)找到最小的值作为下界，在这个区间内找出符合所有案例的数值存入到res中再将res的起始位置和终止位置输出就是最大取值和最小取值。

#include<bits/stdc++.h>
using namespace std;int main(){int n;cin >> n;const int MAX_N = 10000000;int MA = MAX_N, MI = MAX_N;vector<int> a(n, 0);vector<int> b(n, 0);for(int i = 0; i < n; i++){cin >> a[i] >> b[i];MA = min((a[i] / b[i]), MA);MI = min((a[i] / (b[i] + 1)), MI);}vector<int> res;for(int i = MI; i <= MA; i++){bool index = false;for(int j = 0; j < n; j++){if(a[j] / i != b[j]){index = false;break;}else{index = true;}}if(index)	res.push_back(i);}cout << res[0] << " " << res[res.size() - 1] << endl;;return 0;
}

D题：飞机降落：

笔记：

这道题我对于暴力解法的思路是：

对三架飞机进行全排列得到所有的降落顺序再看那个序列可以全部降落：

这里关于全排列c++中有指定的函数可以实现：

#include <iostream>
#include <algorithm> // 包含 next_permutation 函数的头文件
#include <vector>using namespace std;int main() {// 定义一个数组int arr[] = {1, 2, 3};int n = sizeof(arr) / sizeof(arr[0]);// 将数组转换为向量，以便使用 next_permutation 函数vector<int> permutation(arr, arr + n);// 打印初始排列cout << "Initial permutation: ";for (int i = 0; i < n; ++i) {cout << permutation[i] << " ";}cout << endl;// 获取下一个排列并打印，直到所有排列都被打印出来cout << "All permutations: " << endl;do {for (int i = 0; i < n; ++i) {cout << permutation[i] << " ";}cout << endl;} while (next_permutation(permutation.begin(), permutation.end()));return 0;
}

接下来就考虑怎么是的一个数组的元素内部包含三个参数了，这里我们可以使用结构体来做：

#include <iostream>
#include <vector>using namespace std;struct plane {int t;int l;int d;plane() : t(0), l(0), d(0) {}
};int main() {int n;cin >> n;vector<plane> a;// 向向量 a 中添加 n 个元素for (int i = 0; i < n; i++) {plane p;cin >> p.t >> p.l >> p.d;a.push_back(p);}for (int i = 0; i < n; i++) {cout << a[i].t << " " << a[i].l << " " << a[i].d;}return 0;
}

这里需要着重注意怎么想数组内添加结构体！！

我们先来理解一下dfs和回溯暴力解题的方法：

#include <iostream>
using namespace std;
const int N = 10+20;
struct plane{int t,d,l;
}p[N];//飞机 
int n;
bool sc[N];//记录飞机是否成功降落 
bool dfs(int u,int time){//u表示安排到第几架飞机，time表示上一架飞机降落的时间 if(u>=n) return true;//当u>=n时表示所有的飞机都降落成功，返回true for(int i=0;i<n;i++){//遍历飞机数组if(!sc[i]){//找到还没有降落的飞机看是否满足降落条件 sc[i] = true;//先标记成功降落 if(p[i].t+p[i].d < time){//当该飞机到达时间与盘旋时间和小于上一架飞机降落时间//说明这架飞机不能成功降落，回溯降落状态， sc[i] = false;//并且这架飞机在此序列无法成功降落那么后续也无法成功(time会增大，if条件也不会满足) return false;}//得到这架飞机降落的时间// max(time,p[i].t)：飞机开始降落前花费的时间//值为time时：飞机到达但上一架飞机还未落地，只能等到上一飞机落地后开始降落//值 p[i].t： 飞机到达且上一架飞机已经落地，到达后就降落 int t = max(time,p[i].t) + p[i].l;//确定该架飞机此时降落 ，继续寻找下一个降落的飞机 if(dfs(u+1,t)) return true;//该降落顺序飞机全部能降落 //后续有飞机不满足降落条件，回溯前面的降落顺序，重新寻找 sc[i] = false;}}return false;
}
void solve(){cin>>n;for(int i=0;i<n;i++){//初始化飞机状态 cin>>p[i].t>>p[i].d>>p[i].l;sc[i] = false;}if(dfs(0,0)) cout<<"YES"<<endl;else cout<<"NO"<<endl;
}
int main()
{int t;cin>>t;while(t--){solve();}return 0;
}

我们从dfs(0,0)开始深搜过程，处理第一架飞机：将其状态置为已降落，然后判断该飞机是否真的可以降落：（1）如果不能降落，将该飞机状态回溯，接着返回false（2）如果可以降落，将t更新，接着dfs后面的飞机，此时队列首位已经是第一台飞机，其状态以置为已降落所以也不会遍历到第一架，如果第二架不能降落，前提条件是第二架的到达时间加盘旋时间小于第一架的降落时间，所以第二架飞机降落不了这整个以第一架飞机为首的队列都为false。接着dfs就魏false进行下一步状态回溯，将第一架飞机的状态回溯，然后遍历下一架飞机将其置为首位开始继续判断。

#include<bits/stdc++.h>
using namespace std;struct plane{int t;int d;int l;int state;
};vector<plane> ps;bool dfs(int t, int n, int T){if(n == T) return true;for(int i = 0; i < T; i++){if(ps[i].state == 0){ps[i].state = 1;if(ps[i].t + ps[i].d < t){ps[i].state = 0;return false;}if(ps[i].t + ps[i].d >= t){int new_t = max(t, ps[i].t) + ps[i].l; // 更新时间if(dfs(new_t, n + 1, T)) return true; // 递归调用时传入更新后的时间和下一个飞机的序号ps[i].state = 0;}}}return false;
}int main(){int n;cin >> n;while(n--){int T;cin >> T; // 输入飞机数量ps.resize(T); // 调整向量大小以容纳飞机信息for(int i = 0; i < T; i++){cin >> ps[i].t >> ps[i].d >> ps[i].l;ps[i].state = 0;}if(dfs(0, 0, T)) cout << "YES" << endl;else cout << "NO" << endl;}return 0;
}

这里有几个注意的点：建立飞机队列时我们需要确定该队列的大小，这里我们采用了resize的方法，因为这是创建的队列为公共变量在main函数外部所以我们需要用resize来确定大小。c++98版本不支持在定义结构体时对内部变量直接赋值，所以对于每架飞机的状态我们采取在输入个飞机参数的时候为其状态赋值为0.接着判断dfs能否找到可以降落的飞机队列：

在递归开始前我们要记住递归三部曲：

1）确定递归函数的参数和返回值

2）确定终止条件

3）确定单层递归的逻辑

首先传入的参数肯定要有遍历飞机的数量，当前的时间。然后进入递归我们要思考终止条件，这里首先的终止条件就是当遍历的飞机数量达到了T也就是全部遍历完了就返回true，然后开始遍历所有飞机，检查当前飞机是否降落，如果没有降落就将其状态置为已降落，然后判断当前飞机是否真的能降落，如果不能那么该飞机之后的飞机无论怎么排序度无济于事所以回溯该飞机的状态，然后返回false，如果可以降落，那么将当前时间更新，然后递归后续的飞机判断是否可以找到一个可以降落的队列，如果可以返回 true，若果不可以我们需要回溯当前飞机的状态以及当前的时间。

我觉得这道题的那点还是在于暴力遍历所有排序的过程，一开始我始终想不明白的一点是当前传入的飞机n我误认为是飞机的编号，就是我百思不得其解明明是i++的遍历过程怎么遍历不同的顺序，也就是怎么遍历132这样的顺序呢。后来就想明白了传入的n是降落飞机的数量，遍历并不依据这个n，而是依据飞机的状态。每多遍历一架飞机，那么当前飞机的状态已经变为已降落了，在进入下一层递归是我们还是将整个飞机队列遍历一遍取出其中未降落的飞机。如果排在队列前面的飞机出现无降落队列的情况，我们就会回溯到第一层递归去，接着在i++接着处理下一架飞机，这就是从        1   2   3   ---->    1   3   2的过程。

E：接龙数列

这道题使用到了dp的解法，这里我们按照规矩进行动规五部曲：1）dp含义：这里我们dp[i]表示的是末尾为i的字符串的最大接龙长度，2）递推公式：这里我们的状态转移方程为：dp[j] = max(dp[j], dp[i] + 1)情况是：取当前字符串和不取当前字符串。3）初始化：因为字符串的每一位都是0-9的数字，所以我们的dp数组的大小设置为10，将所有数组元素初始化为0,4）遍历顺序：我们从第一个字符串开始遍历即可。

#include<bits/stdc++.h>
using namespace std;int main(){int n;cin >> n;int mx = 0;vector<int> dp(10, 0);string s;int count = n;while(n--){cin >> s;int a = s[0] - '0';int b = s[s.size() - 1] - '0';dp[b] = max(dp[b], dp[a] + 1);mx = max(mx, dp[b]);}cout << count - mx << endl; return 0;
}

这篇关于第十四届蓝桥杯c++组B组做题笔记的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---