第十四届蓝桥杯省赛C++B组题解

考点

暴力枚举，搜索，数学，二分，前缀和，简单DP，优先队列，链表，LCA，树上差分

A 日期统计

暴力枚举：

#include<bits/stdc++.h>
using namespace std;
int b[]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int a[50];
int h,m,s;
set<int>q;//用来排重
int main()
{  for(int i=1;i<=40;i++)//年份已固定，只用从后40位枚举{cin>>a[i];}for(int i=1;i<=40;i++)for(int j=i+1;j<=40;j++)for(int k=j+1;k<=40;k++)for(int p=k+1;p<=40;p++){h=a[i]*1000+a[j]*100+a[k]*10+a[p];m=a[i]*10+a[j];s=a[k]*10+a[p];if(m>0&&m<=12&&s>0&&s<=b[m])q.insert(h);}cout<<q.size()<<endl;
}

B 01串的熵

暴力枚举：

#include <iostream>
#include <cmath>
using namespace std;
int main()
{int n = 23333333;for (int i = 1; i < n; ++i){double a = i * 1.0 / n;  // 0出现的占比double b = (n - i) * 1.0 / n;  // 1出现的占比double res = 0;res -= a * log2(a) * i + b * log2(b) * (n - i);if (fabs(res - 11625907.5798) < 0.0001){cout << i << endl;break;} }return 0;
}

C 冶炼金属

解题思路：
最大值可以遍历比较得出，但是最小值要么使用数学公式，要么就是二分答案

公式法：

#include <iostream>
using namespace std;
typedef long long ll;
ll N,A[10010],B[10010],res[10010],res2[10010];
ll minres=1e9+7;
ll maxres2=-1;
int main()
{cin>>N;for(int i=0;i<N;i++){cin>>A[i]>>B[i];res[i]=A[i]/B[i];minres=min(minres,res[i]);res2[i]=A[i]/(B[i]+1);maxres2=max(maxres2,res2[i]);}cout<<maxres2+1<<" "<<minres;return 0;
}

二分答案：

#include<bits/stdc++.h>
using namespace std;
int a[200100],b[200100],n;
int find(int x){for(int i=1;i<=n;i++){if(a[i]/x>b[i]){return 1;}else if(a[i]/x<b[i]){return 0;}}return 0;
}
int main(){int minn=INT_MAX,maxx=INT_MAX;cin>>n;for(int i=1;i<=n;i++){cin>>a[i]>>b[i];maxx=min(maxx,a[i]/b[i]);}int l=0,r=1e9,mid=0;while(l<=r){mid=(l+r)/2;if(find(mid)){l=mid+1;}else{r=mid-1;}}cout<<l<<" "<<maxx<<endl;return 0;
}

D 飞机降落

题目大意：
给你n架飞机的到达，降落花费和可等待时间，让你求是否能全部安全降落

解题思路：
因为最大数据为10，直接上dfs，遍历所有情况，是否有可以降落的情况，注意一下回溯和边界处理就行。（多实例，记得将标记数组初始化）

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl "\n";
int t[20],d[20],l[20],vis[20];
int n,flag; 
void dfs(int sum,int ans){if(ans>=n){flag=1;return ;}for(int i=1;i<=n;i++){if(!vis[i]&&(sum<=t[i]||sum<=t[i]+d[i])){if(sum<=t[i]){vis[i]=1;dfs(t[i]+l[i],ans+1);}else if(sum<=t[i]+d[i]){vis[i]=1;dfs(sum+l[i],ans+1);}else{continue;}vis[i]=0;}}
} 
void solve(){memset(vis,0,sizeof(vis));cin>>n;for(int i=1;i<=n;i++){cin>>t[i]>>d[i]>>l[i];}flag=0;dfs(0,0);if(flag){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}return ;
}
signed main()
{IOSint t=1;cin>>t;while(t--)solve();return 0;
}

E 接龙数列

题目大意：

给你n个数，问你删除几个可以将剩下的组成接龙数列。

解题思路：
因为接龙数列只需要判断首个数字和末尾数字，而且只能有$0-9$十种可能，所以，只需要开一个dp数组，将每个数的首个数字和末尾数字进行存储，并更新以末尾数字结尾的数组，即是否小于当前以首个数字结尾的接龙数列的长度+1的长度，小于则更新，最后输出最长的一个接龙数列的长度即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl "\n";
int dp[20];
void solve(){int n,maxx=0,a,b;string x;cin>>n;for(int i=1;i<=n;i++){cin>>x;a=x[0]-'0';b=x[x.size()-1]-'0';dp[b]=max(dp[b],dp[a]+1);maxx=max(dp[b],maxx);}cout<<n-maxx<<endl;return ;
}
signed main()
{IOSint t=1;//cin>>t;while(t--)solve();return 0;
}

F 岛屿个数

题目大意：
给你一个n*m的矩阵，由海0和陆地1组成，一个1围成的还就是一个岛屿，但是岛屿里面的岛屿属于子岛屿，不属于岛屿的范畴，让你求一共由多少个岛屿。

解题思路：
因为有环中环的情况，而且只需要判断最外环的情况，所以从最外围的海水开始遍历，接触到最外围海水的一定是岛屿，然后就先dfs一遍把最外围海水标记了，再从外围海水向陆地dfs一遍，每次遍历岛屿数量都加一，最后得出结果。

#include <stdio.h>
#include <stdlib.h>int M, N, d[52][52];void dfs_sea(int i, int j)
{if ((i >= 0 && i <= M + 1) && (j >= 0 && j <= N + 1)){if (d[i][j] == 0){d[i][j] = 2;//标记出外海//八个方向 dfs_sea(i, j + 1);dfs_sea(i, j - 1);dfs_sea(i + 1, j);dfs_sea(i + 1, j + 1);dfs_sea(i + 1, j - 1);dfs_sea(i - 1, j);dfs_sea(i - 1, j + 1);dfs_sea(i - 1, j - 1);}}
}void dfs_island(int i, int j)
{if ((i >= 0 && i <= M + 1) && (j >= 0 && j <= N + 1)){if (d[i][j] == 1){d[i][j] = 3;//搜索过的岛屿不再搜索 dfs_island(i + 1, j);//右 dfs_island(i - 1, j);//左 dfs_island(i, j + 1);//上 dfs_island(i, j - 1);//下 }}
}int main(int argc, char *argv[])
{// 请在此输入您的代码int T;scanf("%d", &T);while (T--){scanf("%d %d", &M, &N);//填充海水for (int i = 0; i < N + 2; i++){d[0][i] = 0;d[M + 1][i] = 0;}for (int i = 1; i < M + 1; i++){d[i][0] = 0;d[i][N + 1] = 0;}//输入图 for (int i = 1; i < M + 1; i++){for (int j = 1; j < N + 1; j++){scanf("%1d", &d[i][j]);}}dfs_sea(0, 0); //找出所有外海 int count;//计算岛屿数量 count = 0;for (int i = 0; i < M + 2; i++){for (int j = 0; j < N + 2; j++){if (d[i][j] == 1 && d[i - 1][j] == 2)//只能从外海搜索岛屿，所以岛屿前一定是外海“2”{dfs_island(i, j);//搜索岛屿 count++;}}}printf("%d\n", count);//以下代码可以打印出处理后的图/*for (int i = 0; i < M + 2; i++){for (int j = 0; j < N + 2; j++){printf("%1d", d[i][j]);if (j == N + 1)printf("\n");}}*/}return 0;
}

G 子串简写

题目大意：给定一个字符串和一个长度K，再给出两个字符a和b，求字符串有多少个长度大于等于K且是以a为首字母，b为尾字母的子串。

解题思路：
因为只需要判断首尾，所以可以直接从字符串的尾部向前遍历并用前缀和来记录b字符的个数，最后字符串从前往后遍历，每遇到一个a字符，就判断在其k-1的长度后，有多少个b字符，将其数量累加，最后输出即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl "\n";
int sum[1000100];
void solve(){int n,num=0;string x;char aa,bb;cin>>n;cin>>x;cin>>aa>>bb;for(int i=x.size()-1;i>=0;i--){if(x[i]==bb){sum[i]+=sum[i+1]+1;}else{sum[i]+=sum[i+1];}}for(int i=0;i<x.size();i++){if(x[i]==aa){num+=sum[i+n-1];}}cout<<num<<endl;return ;
}
signed main()
{IOSint t=1;//cin>>t;while(t--)solve();return 0;
}

H 整数删除

题目大意：给你n个数，和k次操作，每次操作将当前剩余数中最小数的左右两个数加上当前最小数的值（多个最小数从前往后进行操作，左边或者右边没有数则不操作），并将这个最小数剔除，问你k次操作后的序列是什么。

解题思路：
因为需要动态维护最小值，所以使用优先队列，但是因为每次进行操作后，最小值可能会发生变化，所以需要加上双向链表进行优化。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;const int N = 5e5 + 10;
ll v[N], l[N], r[N];void del(int x) {r[l[x]] = r[x], l[r[x]] = l[x];v[l[x]] += v[x], v[r[x]] += v[x];
}int main () {int n, k; cin >> n >> k;r[0] = 1, l[n + 1] = n;priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> h;for (int i = 1; i <= n; i ++)cin >> v[i], l[i] = i - 1, r[i] = i + 1, h.push({v[i], i});while (k --) {auto p = h.top(); h.pop();if (p.first != v[p.second]) h.push({v[p.second], p.second}), k ++;else del(p.second);}int head = r[0];while (head != n + 1) {cout << v[head]<< " ";head = r[head];}return 0;
}

最后两题考到了LCA算法，有点属于盲区了算是，回去恶补一下，两周内题解补上！！！