蓝桥杯2023省赛C++/Java解题思路与代码实现详解

未分类 2天前程序员胖胖胖虎阿

5 0 0

记录算法竞赛的解题历程与心得体会
愿与各位编程爱好者共同进步，分享解题智慧✨

内容概览：

1、日期统计-（解析）-深度优先搜索应用（典型蓝桥风格
2、二进制熵值-（解析）-理解题意是关键，掌握对数运算方法
3、金属冶炼-（解析）-数学极值推导即可解决
4、航班调度-（解析）-全排列搜索（蓝桥经典题型
5、数字接龙-（解析）-动态规划优化（名称唬人的基础DP
6、岛屿计数-（解析）-广度优先与深度优先结合（染色技巧很重要
7、字符串缩写-（解析）-前缀和数组的巧妙运用
8、元素删除-（解析）-优先队列与链表结合（模拟过程
9、10 LCA类题目暂留，后续将出专题讲解

核心知识点：
1、二分搜索
2、emplace方法
3、对数函数

1、日期统计

题目要求

给定长度为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

```
需要满足：
1. 8位连续子序列
2. 构成yyyymmdd格式的2023年有效日期
3. 相同日期仅统计一次

最终输出符合条件的独特日期数量
解题思路：
1. 固定前四位为2023
2. 对剩余数字进行组合搜索
3. 注意处理月份和天数的有效范围
4. 使用标记数组避免重复统计

C++实现

#include
#include
using namespace std;
vector digits{ // 已过滤年份部分
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
};
vector> dateRecord(13,vector(32,false)); // 日期记录
void validateDate(int month, int day){
if(month==4||month==6||month==9||month==11){
if(day>30) return;
}
else if(month==2){
if(day>28) return;
}
dateRecord[month][day] = true;
}

Java实现

import java.util.*;
public class Main {
static List digits = Arrays.asList(
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
);
static boolean[][] dateRecord = new boolean[13][32];
}

2、二进制熵值

题目图示

解题要点：
1. 理解熵值计算公式
2. 注意对数运算的底数转换
3. 确定0和1的合理分布比例

C++实现

#include
#include
using namespace std;
int main(){
const int total = 23333333;
for(int cnt=1; cnt<=total/2; cnt++){
double p0 = cnt*1.0/total;
double p1 = 1-p0;
double entropy = -cnt*p0*log2(p0)-(total-cnt)*p1*log2(p1);
if(fabs(entropy-11625907.5798)<1e-4){
cout<<cnt<<endl;
break;
}
}
return 0;
}

3、金属冶炼

问题描述

根据冶炼记录推导转换率范围：

输入示例：
```
3
75 3
53 2
59 2

```
输出示例：
```
20 25

```
解题思路：
1. 计算每条记录的理论极值
2. 取所有记录的交集范围
3. 最小值由上限推导，最大值由下限推导

C++实现

#include
#define ll long long
using namespace std;
int main(){
int n;
cin>>n;
ll minV=0, maxV=1e18;
while(n--){
ll a,b;
cin>>a>>b;
minV = max(minV, a/(b+1)+1);
maxV = min(maxV, a/b);
}
cout<<minV<<" "<<maxV<<endl;
}