第十四届蓝桥杯省赛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$ 十种可能，所以，只需要开一个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;
}