2023 蓝桥杯题解 （部分）
填空问题
试题 A：日期统计
这题是要我们找一个子序列，满足合法日期。 一共有100个数字
首先要知道子序列：
子序列是指相对顺序不变，从数组中拿出n个数字（也可以理解为删掉若干数字），他不是连续的子序列。
思路 ： 跑一个dfs 从左往右跑，先搜年，再搜月 最后搜日（这里要记录每次搜到的下标，下一次搜索从下标+1开始搜，保证相对顺序不变） 。
搜索完后存到map或者set里面，最好用整数存 year1000+month100+day 处理月份和日期 来存成整数。
也可以转换为字符串如 20230102 来存，但是要注意前导0的处理 如 111 不处理就是2023111 ，会露情况。
最后输出set 或者map的 size 即可
这里要注意2023不是闰年，2月的合法日期<= 28 日
AC 代码
#include<bits/stdc++.h>
using namespace std;
int a[105]= { 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 m[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
map<string,int>mp;
void dfs(int a[],int year,int month,int day,int idxy){
if(day!=0&&year!=0&&month!=0){
// cout<<year<<" "<<month<<" "<<day<<endl;
string s;
s=to_string(year) + (month < 10 ? "0" : "") + to_string(month) + (day < 10 ? "0" : "") + to_string(day);
//cout<<s<<endl;
mp[s]=100;
return ;
}
if(year==0){
for(int i=idxy;i<100;i++){
if(a[i]==2){
year=2;
dfs(a,year,month,day,i+1);
}
}
}
else if(year==2){
for(int i=idxy;i<100;i++){
if(a[i]==0){
year=20;
dfs(a,year,month,day,i+1);
}
}
}else if(year==20){
for(int i=idxy;i<100;i++){
if(a[i]==2){
year=202;
dfs(a,year,month,day,i+1);
}
}
}else if(year==202){
for(int i=idxy;i<100;i++){
if(a[i]==3){
year=2023;
dfs(a,year,month,day,i+1);
}
}
}else if(year==2023){
if(month==0){
for(int i=idxy;i<100;i++){
for(int j=i+1;j<100;j++){
int num;
num=a[i]*10+a[j];
if(num>=1&&num<=12){
month=num;
dfs(a,year,month,day,j+1);
}
}
}
}else if(day==0){
for(int i=idxy;i<100;i++){
for(int j=i+1;j<100;j++){
int num;
num=a[i]*10+a[j];
if(num>=1&&num<=m[month]){
day=num;
dfs(a,year,month,day,j+1);
}
}
}
}
}
}
int main(){
//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
dfs(a,0,0,0,0);
cout<<mp.size();
}
01 串的熵
根据题目的信息，我们可以得出 H(S) 化简后的 表达式 H(S)= n0*p(0)*log2(1/p(0))+ n1*p(1)*log2(1/p(1))
这里的n0 n1 指这俩0 1 的个数，p指概率，log里面我去了1/p 是把符号提取了进去。
有了这个，我们只需要暴力计算二者的数量即可，有题目可知n0+n1=23333333 n0<n1
技巧：对数可以用C++log函数 他是以e为底的，我们对数换底即可。
#include<iostream>
#include<cmath>
using namespace std;
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
double sum=0;
double sum2=0;
// i 表示0 串
for(int i=1;i<=23333333/2;i++){
sum=i*((i*1.0/23333333)*(log(23333333*1.0/i)/log(2)));
//cout<<sum<<endl;
double j=23333333-i;
sum2=j*1.0*((j*1.0/23333333)*(log(23333333*1.0/j)/log(2)));
if(fabs(sum+sum2-11625907.5798)<1e-4){
printf("%.4lf\n",sum+sum2);
cout<<i<<endl;
}
}
}
P9240 [蓝桥杯 2023 省 B] 冶炼金属
二分检验模板，写一个判断函数，然后二分答案即可。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int minans=100000000000,maxans=-1;
int n;
int a[10010];
int b[10010];
int pd(int mid){
for(int i=1;i<=n;i++){
if(a[i]/mid>b[i])return -1;
if(a[i]/mid<b[i])return 0;
}
return 1;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i];
}
int l=0,r=1e9;
int t=(l+r);
while(l<=r){
int mid=(l+r)/2;
int tp =pd(mid);
if(tp==1){
minans=min(minans,mid);
maxans=max(maxans,mid);
l=mid+1;
}
else if(tp==-1)l=mid+1;
else r=mid-1;
}
l=0,r=1e9;
while(l<=r){
int mid=(l+r)/2;
int tp =pd(mid);
if(tp==1){
minans=min(minans,mid);
maxans=max(maxans,mid);
r=mid-1;
}
else if(tp==-1)l=mid+1;
else r=mid-1;
}
cout<<minans<<" "<<maxans;
}
[蓝桥杯 2023 省 B] 飞机降落
思路 ： 看到N超级小，所以可以用dfs直接暴力搜索 是否存在。
dfs 需要记录当前时间 每次dfs都判断一下vis i 是不是全部都是1，全部是 1 代表全部都降落了 那就f=1 return 。
每层递归 1.情况1 直接让飞机飞到并且降落：
2.情况二:让飞机飞到，盘旋后在降落
3.情况三： 飞机飞到+盘旋时间都已经比当前t晚了，坠机了，不管他，不进行任何操作（必有vis[i]=0）。
ac代码：
#include<bits/stdc++.h>
using namespace std;
struct Node{
int t;
int d;
int l;
};
Node a[20];
int f=0;
int vis[20];
void dfs(int x,int t,int n){
if(f)return ;
int pd=1;
t+=a[x].l;
for(int i=1;i<=n;i++){
if(vis[i]==1)continue;
pd=0;
// ·É»úûµ½ µÈ·É»ú·É¹ýÀ´½µÂäµÄÇé¿ö
if(t<=a[i].t){
vis[i]=1; // Ö±½Ó½µÂä²»µÈµÄÇé¿ö
dfs(i,a[i].t,n);
vis[i]=0;
}
// ·É»úÒѾ·Éµ½£¬¿ÉÒÔ½µÂäµÄÇé¿ö
if(t<=a[i].t+a[i].d&&t>a[i].t){
vis[i]=1; // ÅÌÐýÒ»¶¨Ê±¼äµÄÇé¿ö
dfs(i,t,n);
vis[i]=0;
}
// ²»dfs µÄÇé¿ö 1. ʱ¼äÒѾ³¬³öÁËÎҵȴýµÄ·¶Î§¡£
}
if(pd){
f=1;
//cout<<t<<" ";
return ;
}
}
void slove(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].t>>a[i].d>>a[i].l;
}
for(int i=1;i<=n;i++){
f=0;
vis[i]=1;
dfs(i,a[i].t,n);
vis[i]=0;
if(f)break;
}
if(f)cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
int main(){
int t;
cin>>t;
while(t--){
slove();
}
return 0;
}
接龙数列
很明显的DP板子题 。 我们可以类比 最长上升子序列来看这道题，其实就是找最长接龙 序列，那么要删的数 = 总数 – 最长序列。
注意：求最小上升学列需要往前找 和他匹配的且值最大的状态，又因为 对于最长接龙序列来说如果存在多个匹配，最右边必然最大，所以只需要存储左边第一个匹配的数的值即可。· 这里要注意 个位数和任何数字都匹配，需要循环找最值。
状态转移方程：dp[i]=max(num[s[i][0]-‘0’]+1,single+1); single+1 指当前序列只有自己，num[s[i][0]-‘0’]+1 指前一个状态最大值。
AC 代码：
#include<bits/stdc++.h>
using namespace std;
string s[100010];
int dp[100010];
int single;
int num[10];
int ans=0;
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>s[i];
}
for(int i=1;i<=n;i++){
if(s[i].length()==1){
dp[i]=max(dp[i],single+1);
for(int j=0;j<=9;j++){
dp[i]=max(dp[i],num[j]+1);
}
for(int j=0;j<=9;j++){
num[j]=dp[i];
}
}else{
dp[i]=max(num[s[i][0]-'0']+1,single+1);
num[s[i][s[i].length()-1]-'0']=max(dp[i],num[s[i][s[i].length()-1]-'0']);
}
// for(int j=i-1;j>=1;j--){
// if(){
// dp[i]=max(dp[i],dp[j]+1);
// }
// }
}
for(int i=1;i<=n;i++){
ans=max(ans,dp[i]);
}
cout<<n-ans;
return 0;
}
岛屿个数
N很小 这题可以BFS 也可以是DFS(优化一点点)
思路： 一个岛如果被 包围了，那么他一定不能通过搜索，搜索到地图外面。
也就是说DFS 搜他，如果可以出界，那么就是一个独立的岛屿，注意 这题我们需要往八个方向走，因为 当出现样例二的情况时候，四联通是无法搜索出地图外的，对于中间的那个岛屿，而是需要斜着走。！！
AC 代码
#include <bits/stdc++.h>
using namespace std;
// 蓝桥杯代码备份
string s[60];
int a[60][60];
int dir[8][2] = {1, 0, 0, 1, -1, 0, 0, -1, 1, 1, -1, -1, 1, -1, -1, 1};
int n, m;
int f;
int ans;
int cnt = 2; // 设置id.
void init()
{
cnt = 2;
ans = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (s[i][j - 1] == '0')
{
a[i][j] = 0;
}
else
a[i][j] = 1;
}
}
}
void dfs(int x, int y, int vis[60][60], int id)
{
if (x < 1 || x > n || y < 1 || y > m)
{
f = 1;
return;
}
if (a[x][y] == id)
a[x][y] = -1;
for (int i = 0; i < 8; i++)
{
int nx, ny;
nx = x + dir[i][0];
ny = y + dir[i][1];
if (nx < 1 || nx > n || ny < 1 || ny > m)
{
f = 1;
continue;
}
if (a[nx][ny] != 0 && a[nx][ny] != id)
continue;
if (vis[nx][ny] == 1)
continue;
vis[nx][ny] = 1;
if (a[nx][ny] == id)
a[nx][ny] = -1;
dfs(nx, ny, vis, id);
}
}
// 染色处理
void dfs_setid(int x, int y, int id)
{
if (x < 1 || x > n || y < 1 || y > m)
{
return;
}
for (int i = 0; i < 4; i++)
{
int nx, ny;
nx = x + dir[i][0];
ny = y + dir[i][1];
if (nx < 1 || nx > n || ny < 1 || ny > m)
{
continue;
}
if (a[nx][ny] != 1)
continue;
a[nx][ny] = id;
dfs_setid(nx, ny, id);
}
}
void slove()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> s[i];
}
// 转换成数字处理
init();
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (a[i][j] == 1)
{
++cnt;
a[i][j] = cnt;
dfs_setid(i, j, cnt);
// int vis[60][60] = {0};
// f = 0;
// vis[i][j] = 1;
// dfs(i, j, vis);
// vis[i][j] = 0;
}
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (a[i][j] != 0 && a[i][j] != -1)
{
f = 0;
int vis[60][60] = {0};
vis[i][j] = 1;
dfs(i, j, vis, a[i][j]);
// cout << a[i][j];
if (f)
ans++;
}
}
}
// for (int i = 1; i <= n; i++)
// {
// for (int j = 1; j <= m; j++)
// {
// cout << a[i][j] << " ";
// }
// cout << endl;
// }
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t--)
{
slove();
}
}
子串简写
思路 ：二分
首先 如果直接用STL 对每一个c1 遍历他的C2 最坏情况下，复杂度是n*n 对于每一个c1 都去遍历一遍。
必然超时。
解决方法： 预处理右界C2，记录C2的下标。那么对于每个C1 我们就找 第一个满足k 条件的C2，答案ans+= 总大小-当前C2预处理的下标（后面加上自己一共有多少C2），又因为 C2预处理数组记录的是下标，必然从左往右，从小到达，满足二分的单调性。 所以最终时间复杂度可达n*logn
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<int> b;
int ans;
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int k;
cin >> k;
string s;
char h, e;
cin >> s >> h >> e;
for (int i = 0; i < s.length(); i++)
{
if (s[i] == e)
{
b.push_back(i);
}
}
// 二分 时间复杂度n*lgn 1e5 可以
for (int i = 0; i < s.length(); i++)
{
if (s[i] == h)
{
int l = 0, r = b.size() - 1;
while (l <= r)
{
int mid = (l + r) / 2;
if (b[mid] - i + 1 >= k)
r = mid - 1;
else
l = mid + 1;
}
ans += b.size() - r - 1; // 这里省略了+1
}
}
cout << ans;
return 0;
}
U547217 [蓝桥杯 2023 省 B] 整数删除
像这种每次取最小值的题目，优先考虑堆，又因为 需要不断修改每一个数的两侧相连的数，所以考虑使用双向链表。
思路：用一个链表记录每个数的前后。 堆去存每个数 的下标和值（按值排序）
每次取最小的数字，让他两侧的数字相加，并且连接链表，（因为在堆里面没法直接删掉，什么时候取到在去删掉，可以用对应的值取判断和我最新的数值是否相等，相等你就是最新的，不相等就是以前还没删掉的），把新的数放到堆里面，以此类推执行K次 即可。
代码：
#include <bits/stdc++.h>
#define int long long
using namespace std;
// 1 2 4 7 8
struct Node
{
int last, next, num;
};
// 数组链表
Node a[600010];
struct xb
{
int num;
int pos;
bool operator<(const xb &other) const
{
if (num > other.num)
return true;
else if (num < other.num)
return false;
else
return pos > other.pos;
}
};
priority_queue<xb> dui;
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++)
{
cin >> a[i].num;
a[i].last = i - 1;
a[i].next = i + 1;
}
for (int i = 1; i <= n; i++)
{
dui.push({a[i].num, i});
}
// while (!dui.empty())
// {
// cout << dui.top().num << " " << dui.top().pos << endl;
// dui.pop();
// }
// k 次操作
while (k--)
{
while (1)
{
// 每次取一个最小的数字
xb tp;
tp = dui.top();
dui.pop(); // 弹出元素
if (tp.num != a[tp.pos].num)
{
continue;
}
// cout << tp.num << endl;
int last, next;
last = a[tp.pos].last;
next = a[tp.pos].next;
a[last].num += tp.num;
a[next].num += tp.num;
a[tp.pos].num = -1;
// 重新连接
// 越界判断
{
a[last].next = next;
a[next].last = last;
}
if (last != 0)
{
dui.push({a[last].num, last});
}
if (next != n + 1)
{
dui.push({a[next].num, next});
}
break;
}
}
for (int i = 1; i <= n; i++)
{
if (a[i].num != -1)
{
cout << a[i].num << " ";
}
}
return 0;
}