第十四届蓝桥杯省赛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()
{
IOS
int t=1;
cin>>t;
while(t--)
solve();
return 0;
}
E 接龙数列
题目大意：
给你n个数，问你删除几个可以将剩下的组成接龙数列。
解题思路：
因为接龙数列只需要判断首个数字和末尾数字，而且只能有
0
−
9
0-9
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()
{
IOS
int 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()
{
IOS
int 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算法，有点属于盲区了算是，回去恶补一下，两周内题解补上！！！