第十四届蓝桥杯大赛软件赛省赛（C/C++ 大学B组）题解

尝试再做一次，我记得还是有点难，我会尽量多写一点解析，尽量让基础比较弱的友友也能看懂，希望能给你带来帮助

1. 日期统计

题目描述

解题思路

具体代码

2. 01 串的熵

题目描述

解题思路

具体代码

3. 冶炼金属

题目描述

解题思路

具体代码

4. 飞机降落

题目描述

解题思路

具体代码

5. 接龙数列

题目描述

解题思路

具体代码

6. 岛屿个数（待写）

题目描述

解题思路

具体代码

7. 子串简写

题目描述

解题思路

具体代码

8. 整数删除（待写）

题目描述

解题思路

具体代码

1. 日期统计

题目描述

小蓝现在有一个长度为 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

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

解题思路

这道题在赛场上大家可能和我一样，脑子里面第一想法就是循环遍历，反正就8次，我也是这么做的，后面我的老师给我介绍了另一种解法，我都写一下

方法一

直接简单粗暴地循环，唯一需要注意的是记得筛出重复的日期，我用的set(不太清楚set用法的友友需要自己查一下哦)，自动帮我去重，我将每次符合条件的日期（一个八位数的数字）insert到set容器中，后面循环结束后，set的长度就是满足要求的日期的个数(具体代码在下面)

方法二：

这是老师赛后告诉我的，我看见网上也有很多这样写的。不需要循环原本的数组，而是循环遍历2023年的每一天，看看这一天年-月-日这八个数字是否在原数据中也顺序出现，这种解法就不要考虑有相同日期的情况(我文字描述不太清楚，可以直接看下面的代码，看了就知道)

具体代码

方法一代码

这个代码看起来很长，其实很简单(思路见上)，就是八重循环，但是需要仔细再仔细，代码里面我也有写注释，可以看看，不难

 // 长度为8 2023 01 24 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5+ 24 , M = 1e9 + 24 , n = 100;
// 原数据 
int m[100] = {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 D[] = {0 , 31 , 28 , 31 , 30 , 31, 30 , 31 , 31 , 30 , 31 , 30 , 31};  
set<int> s; //用set记录满足要求的日期(数字)，自动会去重，这样set中数字的个数就是答案 
int main()
{int a , b , c , d , e , f , j , h , day , month , date;
//	  1、确保前面4个数字是 2023   abcdfor(a = 0 ; a < n ; a ++){if(m[a] == 2)  // 2{for(b = a+1 ; b < n ; b ++){if(m[b] == 0)  // 0{for(c = b+1 ; c < n ; c ++){if(m[c] == 2)  // 2{for(d = c+1 ; d < n ; d ++){if(m[d] == 3)  // 3{
//									2、保证后面四位  月-日符合逻辑   efjhfor(e = d+1 ; e < n ; e ++){for(f = e+1 ; f < n ; f ++){
//											几月？？  满足month在1-12 month = m[e]*10 + m[f];if(month >= 1 && month <= 12){for(j = f+1 ; j < n ; j ++){for(h = j+1 ; h < n ; h ++){
//														几日？？  满足day在1-D[month]对应月的日期内 day = m[j]*10 + m[h];if(day >= 1 && day <= D[month]){date = 2023*10000 + month*100 + day;s.insert(date);}}}}}}}}}}}} }}cout << s.size();return 0 ; 
}

方法二代码

代码里面的注释写的比较详细可以看看

// 方法二 // 长度为8 2023 01 24 
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N = 3e5+ 24 , M = 1e9 + 24 , n = 100;
// 原数据 
int m[100] = {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 D[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};  
int main()
{int month, day, i, j, ans = 0 ;//	遍历2023年的12个月 for(month = 1 ; month <= 12 ; month ++){		
//		遍历每一天 for(day = 1 ; day <= D[month] ; day ++){string str = "2023";if(month < 10)  str += "0";  //月份只有一位数需要0填充 
//			to_string将数字类型的变量转换为对应的字符串表示str += to_string(month);if(day < 10)  str += "0";  //天数只有一位数需要0填充 str += to_string(day);
//			判断现在的str(这是一个8位数字组成的字符串，表示一个日期) 
//			判断字符串的8个字符是否在原数据m[]中存在，按照顺序//			i是原数据m[]的索引,j是str的索引， for(i = 0 , j = 0 ; i < n && j < 8 ; i ++){if(m[i] == str[j] - '0')  //如果str[j]这个这个数字在m[中存在] {j ++;  // j索引后移，用于判断下一个 }} if(j >= 8)  ans ++;} }cout << ans ;return 0 ;
}

2. 01 串的熵

题目描述

（文字复制过来格式有误，采用截图，请见谅）

解题思路

我的解法也比较没有技术含量，根据题意：

我们假设0出现了x次，1出现了23333333-x次
可以发现H(S)的值就是等于

带入公式中之后将x从0~23333333遍历，
如果答案大于23333333/2，记得把答案更新为23333333-ans，因为0出现的次数小于1的次数。

考试的时候我想的是根据公式推导出x的值，但是实在是不好算，就另辟蹊径，直接粗暴的遍历【怪不得大家又称蓝桥杯为暴力杯哈哈】

答案：11027421

具体代码

#include <bits/stdc++.h> 
using namespace std;
typedef long long ll;
const int N = 3e5+ 24 , M = 1e9 + 24 ;int n = 23333333;
double Hs = 11625907.5798;
int main()
{
//	cout << log2(4);int x , ans ;double temp;for(x = 0 ; x <= n ; x ++){double temp = -x*1.0/n*log2(x*1.0/n)*x - (n-x)*1.0/n*log2((n-x)*1.0/n)*(n-x);if(abs(temp - Hs) <= 0.0001){if(x > n/2)  ans = n - x;else  ans = x;break;}}cout << ans ;return 0 ;
}// 答案：11027421

3. 冶炼金属

题目描述

【问题描述】

小蓝有一个神奇的炉子用于将普通金属 O 冶炼成为一种特殊金属 X。这个炉子有一个称作转换率的属性 V，V 是一个正整数，这意味着消耗 V 个普通金属 O 恰好可以冶炼出一个特殊金属 X，当普通金属 O 的数目不足 V 时，无法继续冶炼。现在给出了 N 条冶炼记录，每条记录中包含两个整数 A 和 B，这表示本次投入了 A 个普通金属 O，最终冶炼出了 B 个特殊金属 X。每条记录都是独立的，这意味着上一次没消耗完的普通金属 O 不会累加到下一次的冶炼当中。根据这 N 条冶炼记录，请你推测出转换率 V 的最小值和最大值分别可能是多少，题目保证评测数据不存在无解的情况。

【输入格式】

第一行一个整数 N，表示冶炼记录的数目。接下来输入 N 行，每行两个整数 A、B，含义如题目所述。

【输出格式】

输出两个整数，分别表示 V 可能的最小值和最大值，中间用空格分开。

【样例输入】

75 3

53 2

59 2

【样例输出】

20 25

【样例说明】

当 V = 20 时，有：⌊ 75/ 20 ⌋ = 3，⌊ 53/ 20 ⌋ = 2，⌊ 59/ 20 ⌋ = 2，可以看到符合所有冶炼记录。

当 V = 25 时，有：⌊ 75 /25 ⌋ = 3，⌊ 53/ 25 ⌋ = 2，⌊ 59/ 25 ⌋ = 2，可以看到符合所有冶炼记录。

且再也找不到比 20 更小或者比 25 更大的符合条件的 V 值了。

【评测用例规模与约定】

对于 30% 的评测用例，1 ≤ N ≤ 10^2。

对于 60% 的评测用例，1 ≤ N ≤ 10^3。

对于 100% 的评测用例，1 ≤ N ≤ 10^4，1 ≤ B ≤ A ≤ 10^9。

解题思路

题目的意思还是挺好理解的，主要在V的最大值和最小值，其实是一个求交集的过程，只有交集才能满足每一个数据的要求，也就是右边界要取所有右边界的最小值（每组数据求出来的最大值中的最小值），左边界同理，需要所有求出来的左边界的最大值（每组数据求出来的最小值中的最大值），这个还是挺好理解的，如果实在不太理解，建议用样例验证一下，比较容易

现在我们来看看，怎么求每组数据对应的最大值与最小值：

最大值：这个比较简单，我们知道投入了 a 个普通金属 O，最终冶炼出了 b 个特殊金属 X，那么V的最大值就是a/b，没有比这个还大的值了

最小值：假设最小值为vmin，那么肯定存在a/vmin = b ,a/vmin取的是整数，因为vmin是金属O转换成X的转换率最小值，如果vmin减小一个单位，那么肯定b的值会增加一个单位，能理解吗，就是本来a/vmin就能冶炼出b个X，而vmin是冶炼出b个X的最小值，如果vmin减少，肯定b会增加，所以我们可得：a/(vmin-1) = b+1，那么，vmin = a/(b+1)+1

我的表达能力不太好，希望你能理解

具体代码

那看看代码，我没怎么写注释，就几行就能解决，如果不太懂，看看上面的思路

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{int n , a , b , vmax = 0x3f3f3f3f , vmin = 0;cin >> n;while(n --){cin >> a >> b ;vmax = min(vmax , a/b);vmin = max(vmin , a/(b+1)+1);}cout << vmin << " " << vmax << endl; return 0 ;
}

出现一个很变态的事，发现我把int改成longlong就过不了这道题，其实题目范围是在int内，我就是不理解为什么用longlong就不行。

4. 飞机降落

题目描述

【问题描述】

N 架飞机准备降落到某个只有一条跑道的机场。其中第 i 架飞机在 Ti 时刻到达机场上空，到达时它的剩余油料还可以继续盘旋 Di 个单位时间，即它最早可以于 Ti 时刻开始降落，最晚可以于 Ti + Di 时刻开始降落。降落过程需要 Li 个单位时间。一架飞机降落完毕时，另一架飞机可以立即在同一时刻开始降落，但是不能在前一架飞机完成降落前开始降落。请你判断 N 架飞机是否可以全部安全降落。

【输入格式】

输入包含多组数据。第一行包含一个整数 T，代表测试数据的组数。对于每组数据，第一行包含一个整数 N。以下 N 行，每行包含三个整数：Ti，Di 和 Li。

【输出格式】

对于每组数据，输出 YES 或者 NO，代表是否可以全部安全降落。

【样例输入】

0 100 10

10 10 10

0 2 20

0 10 20

10 10 20

20 10 20

【样例输出】

YES

【样例说明】

对于第一组数据，可以安排第 3 架飞机于 0 时刻开始降落，20 时刻完成降落。安排第 2 架飞机于 20 时刻开始降落，30 时刻完成降落。安排第 1 架飞机于 30 时刻开始降落，40 时刻完成降落。

对于第二组数据，无论如何安排，都会有飞机不能及时降落。

【评测用例规模与约定】

对于 30% 的数据，N ≤ 2。

对于 100% 的数据，1 ≤ T ≤ 10，1 ≤ N ≤ 10，0 ≤ Ti , Di , Li ≤ 10^5。

解题思路

因为这道题的数据范围比较少，我用的是全排列获取了每种情况，分别看是否能成功降落，如果存在一种，就YES，如果全排列的所有情况都不行就NO

具体可以看代码里面的注释

具体代码

// 数据不多 直接全排列列举所有可能 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct point{int t , d , l ; //到达 盘旋 降落时间 
}p[24];
void answer()
{int n , i , j , t , d , l , now ;bool flag = true;
//	a是下表数据，表示所有情况
//	通过全排列a的情况，实则是每架飞机的情况，不同的降落方案 int a[14]; // 1<= n <= 10cin >> n ;for(i = 1; i <= n ; i ++){a[i] = i ;cin >> p[i].t >> p[i].d >> p[i].l;} 
//	开始全排列列举所有情况
//	只要有一种情况满足要求，能成功降落就算YES,否则NO do{flag = true ; //表示是否成功now = 0 ; // 表示此刻的时间， for(i = 1 ; i <= n ; i ++){//到达 盘旋 降落时间 t = p[a[i]].t , d = p[a[i]].d , l = p[a[i]].l ;/*我们知道，每架飞机能够成功降落的时间在 t ~ t+l那么now可以在三个区间返回内 分别是   now<t    t<=now<=t+l    t+l<now1、now > t+l 这种情况肯定不行，现在的时间点已经超过飞机降落 2、now <= t+l 这又分两种2.1  t<=now 需要这架飞机等一下2.2  now<t   需要等飞机在t时间到来，需要等飞机一个是飞机等，另一中等飞机 */if(now > t+d){flag = false ; //失败break ; //结束，开始下一组排列情况 } else{if(now >= t){now = now + l ;}else{now = t + l ;}}}if(flag){
//			这组排列满足安排，可行，直接结束就行，只有找到一组情况就行，又不是找最优 cout << "YES" << endl;return ; }}while(next_permutation(a+1 , a+n+1));cout << "NO" << endl;
}
int main()
{int t;cin >> t ;while(t --){answer();}return 0 ;
}

5. 接龙数列

题目描述

【问题描述】

对于一个长度为 K 的整数数列：A1, A2, . . . , AK，我们称之为接龙数列当且仅当 Ai 的首位数字恰好等于 Ai−1 的末位数字 (2 ≤ i ≤ K)。例如 12, 23, 35, 56, 61, 11 是接龙数列；12, 23, 34, 56 不是接龙数列，因为 56 的首位数字不等于 34 的末位数字。所有长度为 1 的整数数列都是接龙数列。现在给定一个长度为 N 的数列 A1, A2, . . . , AN，请你计算最少从中删除多少个数，可以使剩下的序列是接龙序列？

【输入格式】

第一行包含一个整数 N。第二行包含 N 个整数 A1, A2, . . . , AN。

【输出格式】

一个整数代表答案。

【样例输入】

11 121 22 12 2023

【样例输出】

【样例说明】

删除 22，剩余 11, 121, 12, 2023 是接龙数列。

【评测用例规模与约定】

对于 20% 的数据，1 ≤ N ≤ 20。

对于 50% 的数据，1 ≤ N ≤ 10000。

对于 100% 的数据，1 ≤ N ≤ 10^5，1 ≤ Ai ≤ 10^9。所有 Ai 保证不包含前导 0。

解题思路

这道题用的dp，dp[i]表示以i（0<=i<=9）为结尾最长可以组成多长，那么答案就是n-max(dp[i]),max(dp[i])是能组成的最长的长度

对于每一个数字，我会用head和tail存下这个数的第一个/最后一个数字的值，

核心：dp[p[i].tail] = max(dp[p[i].tail] , dp[p[i].head] +1);

p[i].head和p[i].tail表示第i个数的头部和尾部

dp[p[i].tail]表示以p[i].tail（0<=p[i].tail<=9）为结尾最长可以组成多长

在dp[p[i].tail]（过去的值）和dp[p[i].head] +1求最大值，dp[p[i].head] +1表示在以p[i].head为结尾的数的基础上再加一，家的这个值就是第i个数，

具体代码

// 数据不多 直接全排列列举所有可能 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 24; 
struct point{int head , tail; //表示的是每一个整数的开头和结尾数字 
}p[N];
int dp[12];  // i（0<=i<=9）为结尾最长可以组成多长
int main()
{int n , a , i , j , ans = N;cin >> n ;for(i = 1 ; i <= n ; i ++){cin >> a;p[i].tail = a%10;  //尾部数字 while(a >= 10){a /= 10;}p[i].head = a; // 头部数据 }for(i = 1 ; i <= n ; i ++){dp[p[i].tail] = max(dp[p[i].tail] , dp[p[i].head] +1);} for(i = 0 ; i < 10 ; i ++){ans = min(ans , n-dp[i]);}cout << ans ;return 0 ;
}

6. 岛屿个数（待写）

题目描述

【问题描述】

小蓝得到了一副大小为 M × N 的格子地图，可以将其视作一个只包含字符 ‘0’（代表海水）和 ‘1’（代表陆地）的二维数组，地图之外可以视作全部是海水，每个岛屿由在上/下/左/右四个方向上相邻的 ‘1’ 相连接而形成。在岛屿 A 所占据的格子中，如果可以从中选出 k 个不同的格子，使得他们的坐标能够组成一个这样的排列：(x0, y0),(x1, y1), . . . ,(xk−1, yk−1)，其中 (x(i+1)%k , y(i+1)%k) 是由 (xi , yi) 通过上/下/左/右移动一次得来的 (0 ≤ i ≤ k − 1)，此时这 k 个格子就构成了一个 “环”。如果另一个岛屿 B 所占据的格子全部位于这个 “环” 内部，此时我们将岛屿 B 视作是岛屿 A 的子岛屿。若 B 是 A 的子岛屿，C 又是 B 的子岛屿，那 C 也是 A 的子岛屿。请问这个地图上共有多少个岛屿？在进行统计时不需要统计子岛屿的数目。

【输入格式】

第一行一个整数 T，表示有 T 组测试数据。接下来输入 T 组数据。对于每组数据，第一行包含两个用空格分隔的整数 M、N 表示地图大小；接下来输入 M 行，每行包含 N 个字符，字符只可能是 ‘0’ 或 ‘1’。

【输出格式】

对于每组数据，输出一行，包含一个整数表示答案。

【样例输入】

5 5

01111

11001

10101

10001

11111

5 6

111111

100001

010101

100001

111111

【样例输出】

【样例说明】

对于第一组数据，包含两个岛屿，下面用不同的数字进行了区分： 01111 11001 10201 10001 11111 岛屿 2 在岛屿 1 的 “环” 内部，所以岛屿 2 是岛屿 1 的子岛屿，答案为 1。对于第二组数据，包含三个岛屿，下面用不同的数字进行了区分： 111111 100001 020301 100001 111111

注意岛屿 3 并不是岛屿 1 或者岛屿 2 的子岛屿，因为岛屿 1 和岛屿 2 中均没有 “环”。

【评测用例规模与约定】

对于 30% 的评测用例，1 ≤ M, N ≤ 10。

对于 100% 的评测用例，1 ≤ T ≤ 10，1 ≤ M, N ≤ 50。

解题思路

暂无，我自己写不出来，先看看别人的，抱歉

具体代码

暂无

7. 子串简写

题目描述

【问题描述】

程序猿圈子里正在流行一种很新的简写方法：对于一个字符串，只保留首尾字符，将首尾字符之间的所有字符用这部分的长度代替。例如 internationalization 简写成 i18n，Kubernetes （注意连字符不是字符串的一部分）简写成 K8s, Lanqiao 简写成 L5o 等。在本题中，我们规定长度大于等于 K 的字符串都可以采用这种简写方法（长度小于 K 的字符串不配使用这种简写）。给定一个字符串 S 和两个字符 c1 和 c2，请你计算 S 有多少个以 c1 开头 c2 结尾的子串可以采用这种简写？

【输入格式】

第一行包含一个整数 K。

第二行包含一个字符串 S 和两个字符 c1 和 c2。

【输出格式】

一个整数代表答案。

【样例输入】

abababdb a b

【样例输出】

【样例说明】

符合条件的子串如下所示，中括号内是该子串：

[abab]abdb

[ababab]db

[abababdb]

ab[abab]db

ab[ababdb]

abab[abdb]

【评测用例规模与约定】

对于 20% 的数据，2 ≤ K ≤ |S | ≤ 10000。

对于 100% 的数据，2 ≤ K ≤ |S | ≤ 5 × 105。S 只包含小写字母。c1 和 c2 都是小写字母。 |S | 代表字符串 S 的长度。

解题思路

题意很好理解，其实就算找长度大于等于k且以 c1 开头 c2 结尾的连续子串的个数

这里用的是dp，大家可以看我的代码里面的注释

具体代码


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 24; 
string s;
ll num[N];
int main()
{int k , i , j ;ll ans = 0 ;char c1 , c2 ;cin >> k ;cin >> s >> c1 >> c2;
//	1、num[i]表示到第i个字符，c1字符的个数 ，从第一个字符开始 for(i = 1 ; i <= s.size() ; i ++){
//		动态规划 num[i] = num[i-1] + (s[i-1] == c1);}
//	2、从第k歌字符开始，如果 第i个字符s[i-1]等于c2，则以s[i]结尾字符为c2的个数有 num[i-k]个，这个自己可以推算一下 for(i = k ; i <= s.size() ; i ++){if(s[i-1] == c2){ans += num[i-k+1];   //我num的下标是从1开始的，所以这里要加1 }} cout << ans ; return 0; 
}