第十四届蓝桥杯 C/C++ 省赛 B 组题解 | 极客日志

C++算法

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

综述由AI生成第十四届蓝桥杯 C/C++ 省赛 B 组包含十道题目，涵盖日期统计、信息熵计算、冶炼金属转换率、飞机降落调度、接龙数列动态规划、岛屿连通性判断、字串简写前缀和优化、整数删除堆与链表优化、景区导游树上前缀和与 LCA 倍增、砍树树上差分等知识点。文章提供了从暴力枚举到优化的多种代码实现，涉及搜索、DP、前缀和、链表、堆、树结构等算法基础，适合准备竞赛的开发者参考。

GitMaster发布于 2026/3/16更新于 2026/5/1929 浏览

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

一共两道填空题，八道程序设计题。

A:日期统计（5 分）

题意：

小蓝现在有一个长度为 100 的数组，数组中的每个元素的值都在 0 到 9 的范围之内。数组中的元素从左至右如下所示：

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

现在他想要从这个数组中寻找一些满足以下条件的子序列：

子序列的长度为 8；
这个子序列可以按照下标顺序组成一个 yyyymmdd 格式的日期，并且要求这个日期是 2023 年中的某一天的日期，例如 20230902，20231223。yyyy 表示年份，mm 表示月份，dd 表示天数，当月份或者天数的长度只有一位时需要一个前导零补充。

请你帮小蓝计算下按上述条件一共能找到多少个不同的 2023 年的日期。对于相同的日期你只需要统计一次即可。

解法：

先按照题目要求找到第一个 2023 的位置：

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

删去这个位置之前的所有数

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

在剩余的数上枚举月份和日期。

注意到剩余的数不会产生 30 日和 31 日，也不会产生 2 月 29 日。所以不需要特判。

#include <bits/stdc++.h>
using namespace std;
int a[50];
bool f[2][10][3][10];
int main(){
    int n=0;
    int x=0;
    while(x!=-1){ cin>>x; a[++n]=x;}
    --n;
    int ans=0;
    for(int i=1;i<=n;i++){
        (a[i]>);
        ( j=i;j<=n;j++){
            (a[i]==&&a[j]==);
            (a[i]==&&a[j]>);
            ( k=j;k<=n;k++){
                (a[k]>);
                ( m=k;m<=n;m++){
                    (a[k]==&&a[m]==);
                    (f[a[i]][a[j]][a[k]][a[m]]);
                    ++ans; f[a[i]][a[j]][a[k]][a[m]]=;
                }
            }
        }
    }
    cout<<ans;
     ;
}

#include <bits/stdc++.h>
using namespace std;
int main(){
    double n=23333333;
    double ans=11625907.5798;
    double mn=ans,mi=-1;
    for(int i=1;i<n;i++){
        double a=i;
        double b=n-a;
        double anss=-(a*(a/n)*log2(a/n)+b*(b/n)*log2(b/n));
        anss-=ans;
        if(anss<0) anss=-anss;
        if(anss<mn){ mn=anss; mi=i;}
    }
    printf("%.8lf %.0lf",mn,mi);
    return 0;
}

20 25

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n; cin>>n;
    vector<int>a(n+1),b(n+1);
    for(int i=1;i<=n;i++){ cin>>a[i]>>b[i];}
    int l=-1,r=-1;
    for(int v=1;;v++){
        bool f=0;
        for(int i=1;i<=n;i++){
            if(a[i]/v==b[i])continue; f=1;break;
        }
        if(f){if(l!=-1)break;continue;}
        if(l==-1) l=v; r=v;
    }
    cout<<l<<' '<<r<<'\n';
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n; cin>>n;
    int l=-1,r=1000000000;
    for(int i=1;i<=n;i++){
        int a,b; cin>>a>>b;
        l=max(l,a/(b+1)+1); r=min(r,a/b);
    }
    cout<<l<<' '<<r<<'\n';
    return 0;
}

YES NO

#include <bits/stdc++.h>
using namespace std;
int n;
int t[11],d[11],l[11];
bool f;
bool v[11];
void dfs(int ti,int k){
    if(k==n){ f=1;return;}
    for(int i=1;i<=n;i++){
        if(v[i])continue;
        if(t[i]+d[i]<ti)return;
        v[i]=1;
        dfs(max(ti,t[i])+l[i],k+1);
        v[i]=0;
        if(f)break;
    }
}
int main(){
    int m; cin>>m;
    while(m--){
        f=0; cin>>n;
        for(int i=1;i<=n;i++){ cin>>t[i]>>d[i]>>l[i];}
        dfs(-1,0);
        if(f)puts("YES");else puts("NO");
    }
    return 0;
}

5
11 121 22 12 2023

#include <bits/stdc++.h>
using namespace std;
int n;
int l[100011],r[100011];
void f(int i,int x){ r[i]=x%10;while(x>9){ x/=10;} l[i]=x;}
int ans=0;
void dfs(int x,int k){ ans=max(ans,k);for(int i=x+1;i<=n;i++){if(x==0||l[i]==r[x]){dfs(i,k+1);}}}
int main(){ cin>>n;for(int i=1;i<=n;i++){int x; cin>>x;f(i,x);}dfs(0,0); cout<<n-ans;return 0;}

#include <bits/stdc++.h>
using namespace std;
int n;
int l[100011],r[100011];
void f(int i,int x){ r[i]=x%10;while(x>9){ x/=10;} l[i]=x;}
int s[100011];
int ans;
int main(){ cin>>n;for(int i=1;i<=n;i++){int x; cin>>x;f(i,x); s[i]=1;}
for(int i=1;i<=n;i++){
    for(int j=1;j<i;j++){
        if(l[i]==r[j]){ s[i]=max(s[i],s[j]+1);}
    }
} ans=0;
for(int i=1;i<=n;i++){ ans=max(ans,s[i]);}
cout<<n-ans;return 0;}

#include <bits/stdc++.h>
using namespace std;
int n;
int l[100011],r[100011];
void f(int i,int x){ r[i]=x%10;while(x>9){ x/=10;} l[i]=x;}
int s[100011];
int ans;
int main(){ cin>>n;for(int i=1;i<=n;i++){int x; cin>>x;f(i,x);}
for(int i=1;i<=n;i++){ s[r[i]]=max(s[r[i]],s[l[i]]+1);}
for(int i=0;i<=9;i++){ ans=max(ans,s[i]);}
cout<<n-ans;return 0;}

1
3

#include <bits/stdc++.h>
using namespace std;
int n,m;
int s[55][55];
int dx1[8]={-1,-1,-1,0,+1,+1,+1,0};
int dy1[8]={-1,0,+1,+1,+1,0,-1,-1};
bool ck1(int x,int y){if(x<0||y<0||x>n+1||y>m+1||s[x][y]==-1)return 0;return 1;}
bool v[5005];
void dfs1(int x,int y){ s[x][y]=-1;int nx,ny;for(int i=0;i<8;i++){ nx=x+dx1[i]; ny=y+dy1[i];if(ck1(nx,ny)){int a=s[nx][ny];if(a!=0){ v[a]=1;}else{dfs1(nx,ny);}}}}
int k;
int dx2[4]={-1,0,+1,0};
int dy2[4]={0,+1,0,-1};
bool ck2(int x,int y){if(x<1||y<1||x>n||y>m||s[x][y]!=1)return 0;return 1;}
void dfs2(int x,int y){ s[x][y]=k;int nx,ny;for(int i=0;i<4;i++){ nx=x+dx2[i]; ny=y+dy2[i];if(ck2(nx,ny)){dfs2(nx,ny);}}}
int main(){
    int t; cin>>t;
    while(t--){
        cin>>n>>m;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                char ch; cin>>ch; s[i][j]=ch-'0';
            }
        }
        k=2;
        int ans=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(s[i][j]==1){dfs2(i,j);++k;}
            }
        }
        dfs1(0,0);
        for(int i=2;i<k;i++){ ans+=v[i];}
        cout<<ans<<'\n';
        memset(s,0,sizeof(s));memset(v,0,sizeof(v));
    }
    return 0;
}

4 abababdb a b

[abab]abdb [ababab]db [abababdb] ab[abab]db ab[ababdb] abab[abdb]

#include <bits/stdc++.h>
using namespace std;
int main(){
    int k; cin>>k; string s; cin>>s;
    char c1,c2; cin>>c1>>c2;
    int n=s.size();
    long long ans=0;
    for(int i=0;i<n;i++){
        if(s[i]==c1){
            for(int j=i+k-1;j<n;j++){
                if(s[j]==c2){++ans;}
            }
        }
    }
    cout<<ans<<'\n';
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int main(){
    int k; cin>>k; string s; cin>>s;
    char c1,c2; cin>>c1>>c2;
    int n=s.size();
    vector<int>a(n);
    long long ans=0;
    for(int i=0;i<n;i++){
        if(s[i]==c1){ a[i]++;}
        if(i) a[i]+=a[i-1];
        if(s[i]==c2){
            int l=i-k+1;
            if(l>=0){ ans+=a[l];}
        }
    }
    cout<<ans<<'\n';
    return 0;
}

5 3
1 4 2 8 7

17 7

[1] 4 2 8 7
5 [2] 8 7
7 [10] 7
17 7

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,k; cin>>n>>k;
    vector<long long>s(n+1);
    for(int i=1;i<=n;i++){ cin>>s[i];}
    while(k--){
        long long mn=-1;int p=-1;
        for(int i=1;i<=n;i++){
            if(s[i]==-1)continue;
            if(p==-1|| s[i]<mn){ p=i; mn=s[i];}
        }
        s[p]=-1;
        for(int i=p-1;i>=1;i--){if(s[i]!=-1){ s[i]+=mn;break;}}
        for(int i=p+1;i<=n;i++){if(s[i]!=-1){ s[i]+=mn;break;}}
    }
    for(int i=1;i<=n;i++){
        if(s[i]==-1)continue; cout<<s[i]<<' ';
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
struct lb{int l,r;long long x;}s[500005];
#define pl pair<long long,int>
#define xx first
#define yy second
priority_queue<pl,vector<pl>,greater<pl>> q;
int main(){
    int n,k; cin>>n>>k;
    s[0].l=-1; s[0].r=1; s[0].x=-1;
    for(int i=1;i<=n;i++){
        cin>>s[i].x; s[i].l=i-1; s[i].r=i+1; q.push({s[i].x,i});
    }
    s[n].r=-1;
    for(int i=1;i<=k;i++){
        long long x=q.top().xx;int p=q.top().yy;
        while(s[p].x!=x){ x=s[p].x; q.pop(); q.push({x,p}); x=q.top().xx; p=q.top().yy;}
        q.pop();
        s[s[p].l].x+=x; s[s[p].r].x+=x;
        s[s[p].l].r=s[p].r; s[s[p].r].l=s[p].l;
        s[p].l=-1; s[p].r=-1;
    }
    int p=0;
    while(s[p].r!=-1){ p=s[p].r; cout<<s[p].x<<' ';
    }
    return 0;
}

10 7 13 14

#include <bits/stdc++.h>
using namespace std;
vector<pair<long long,int>>s[100005];
#define xx first
#define ww second
int h[100005];
long long d[100005];
int f[100005];
void dfs(int u){
    for(auto v:s[u]){
        if(h[v.xx])continue; h[v.xx]=h[u]+1; f[v.xx]=u; d[v.xx]=d[u]+v.ww;
        dfs(v.xx);
    }
}
int lca(int x,int y){
    if(h[x]>h[y])swap(x,y);
    while(h[x]!=h[y]){ y=f[y];}
    if(x==y){return x;}
    while(x!=y){ x=f[x]; y=f[y];}
    return x;
}
long long dist(int x,int y){
    if(x==0||y==0)return 0;
    int m=lca(x,y);
    long long sum=d[x]+d[y]-2*d[m];
    return sum;
}
int main(){
    int n,k; cin>>n>>k;
    for(int i=1;i<n;i++){
        int u,v,w; cin>>u>>v>>w; s[u].push_back({v,w}); s[v].push_back({u,w});
    }
    h[1]=1;dfs(1);
    vector<int>p(k+1);
    for(int i=1;i<=k;i++){ cin>>p[i];}
    long long ans=0;
    for(int i=1;i<=k;i++){
        ans=0;int l=0;
        for(int j=1;j<=k;j++){
            if(i==j)continue; ans+=dist(l,p[j]); l=p[j];
        }
        cout<<ans<<' ';
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
vector<pair<long long,int>>s[100005];
#define xx first
#define ww second
int h[100005];
long long d[100005];
int f[100005];
void dfs(int u){
    for(auto v:s[u]){
        if(h[v.xx])continue; h[v.xx]=h[u]+1; f[v.xx]=u; d[v.xx]=d[u]+v.ww;
        dfs(v.xx);
    }
}
int lca(int x,int y){
    if(h[x]>h[y])swap(x,y);
    while(h[x]!=h[y]){ y=f[y];}
    if(x==y){return x;}
    while(x!=y){ x=f[x]; y=f[y];}
    return x;
}
long long dist(int x,int y){
    if(x==0||y==0)return 0;
    int m=lca(x,y);
    long long sum=d[x]+d[y]-2*d[m];
    return sum;
}
int main(){
    int n,k; cin>>n>>k;
    for(int i=1;i<n;i++){
        int u,v,w; cin>>u>>v>>w; s[u].push_back({v,w}); s[v].push_back({u,w});
    }
    h[1]=1;dfs(1);
    vector<int>p(k+1);
    for(int i=1;i<=k;i++){ cin>>p[i];}
    long long ans=0;
    for(int i=1;i<k;i++){ ans+=dist(p[i],p[i+1]);}
    for(int i=1;i<=k;i++){
        long long sum=ans; sum-=dist(p[i-1],p[i]); sum-=dist(p[i],p[i+1]); sum+=dist(p[i-1],p[i+1]);
        cout<<sum<<' ';
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
vector<pair<long long,int>>s[100005];
#define xx first
#define ww second
int h[100005];
long long d[100005];
int f[100005][25];
void dfs(int u){
    for(int i=1;i<=24;i++){ f[u][i]=f[f[u][i-1]][i-1];}
    for(auto v:s[u]){
        if(h[v.xx])continue; h[v.xx]=h[u]+1; f[v.xx][0]=u; d[v.xx]=d[u]+v.ww;
        dfs(v.xx);
    }
}
int lca(int x,int y){
    if(h[x]>h[y])swap(x,y);
    for(int i=24;i>=0;i--){if(h[f[y][i]]>=h[x]){ y=f[y][i];}}
    if(x==y){return x;}
    for(int i=24;i>=0;i--){if(f[x][i]!=f[y][i]){ x=f[x][i]; y=f[y][i];}}
    return f[x][0];
}
long long dist(int x,int y){
    if(x==0||y==0)return 0;
    int m=lca(x,y);
    long long sum=d[x]+d[y]-2*d[m];
    return sum;
}
int main(){
    int n,k; cin>>n>>k;
    for(int i=1;i<n;i++){
        int u,v,w; cin>>u>>v>>w; s[u].push_back({v,w}); s[v].push_back({u,w});
    }
    h[1]=1;dfs(1);
    vector<int>p(k+1);
    for(int i=1;i<=k;i++){ cin>>p[i];}
    long long ans=0;
    for(int i=1;i<k;i++){ ans+=dist(p[i],p[i+1]);}
    for(int i=1;i<=k;i++){
        long long sum=ans; sum-=dist(p[i-1],p[i]); sum-=dist(p[i],p[i+1]); sum+=dist(p[i-1],p[i+1]);
        cout<<sum<<' ';
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>>s[100005];
#define xx first
#define ii second
int id[100005];
int f[100005];
int h[100005];
int cnt[100005];
void dfs(int u){
    for(auto v:s[u]){
        if(h[v.xx])continue; h[v.xx]=h[u]+1; f[v.xx]=u; id[v.xx]=v.ii;
        dfs(v.xx);
    }
}
void sol(int x,int y){
    if(h[x]>h[y])swap(x,y);
    while(h[x]!=h[y]){ cnt[id[y]]++; y=f[y];}
    if(x==y)return;
    while(x!=y){ cnt[id[x]]++; cnt[id[y]]++; x=f[x]; y=f[y];}
}
int main(){
    int n,k; cin>>n>>k;
    for(int i=1;i<n;i++){
        int u,v; cin>>u>>v; s[u].push_back({v,i}); s[v].push_back({u,i});
    }
    h[1]=1;dfs(1);
    for(int i=1;i<=k;i++){
        int x,y; cin>>x>>y;sol(x,y);
    }
    for(int i=n-1;i>=1;i--){
        if(cnt[i]==k){ cout<<i;return 0;}
    }
    cout<<-1;return 0;
}

#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>>s[100005];
#define xx first
#define ii second
int id[100005];
int f[100005][25];
int h[100005];
int cnt[100005];
void dfs(int u){
    for(int i=1;i<=24;i++){ f[u][i]=f[f[u][i-1]][i-1];}
    for(auto v:s[u]){
        if(h[v.xx])continue; h[v.xx]=h[u]+1; f[v.xx][0]=u; id[v.xx]=v.ii;
        dfs(v.xx);
    }
}
int lca(int x,int y){
    if(h[x]>h[y])swap(x,y);
    for(int i=24;i>=0;i--){if(h[f[y][i]]>=h[x]){ y=f[y][i];}}
    if(x==y)return x;
    for(int i=24;i>=0;i--){if(f[x][i]!=f[y][i]){ x=f[x][i]; y=f[y][i];}}
    return f[x][0];
}
void sol(int x,int y){
    int m=lca(x,y); cnt[id[x]]++; cnt[id[y]]++; cnt[id[m]]-=2;
}
void dfs2(int u,int fa){
    for(auto v:s[u]){
        if(v.xx==fa)continue;
        dfs2(v.xx,u); cnt[id[u]]+=cnt[id[v.xx]];
    }
}
int main(){
    int n,k; cin>>n>>k;
    for(int i=1;i<n;i++){
        int u,v; cin>>u>>v; s[u].push_back({v,i}); s[v].push_back({u,i});
    }
    h[1]=1;dfs(1);
    for(int i=1;i<=k;i++){
        int x,y; cin>>x>>y;sol(x,y);
    }
    dfs2(1,0);
    for(int i=n-1;i>=1;i--){
        if(cnt[i]==k){ cout<<i;return 0;}
    }
    cout<<-1;return 0;
}

#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>>s[100005];
#define xx first
#define ii second
int cnt[100005];
int ans=-1;
int n,k;
void dfs(int u,int fa){
    for(auto v:s[u]){
        if(v.xx==fa)continue;
        dfs(v.xx,u); cnt[u]+=cnt[v.xx];
    }
    if(abs(cnt[u])==k){
        for(auto v:s[u]){
            if(v.xx==fa){ ans=max(ans,v.ii);}
        }
    }
}
int main(){
    cin>>n>>k;
    for(int i=1;i<n;i++){
        int u,v; cin>>u>>v; s[u].push_back({v,i}); s[v].push_back({u,i});
    }
    for(int i=1;i<=k;i++){
        int x,y; cin>>x>>y; cnt[x]=1; cnt[y]=-1;
    }
    dfs(1,0);
    cout<<ans;return 0;
}

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

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

A:日期统计（5 分）

题意：

解法：

B:01 串的熵（5 分）

题意：

解法：

C:冶炼金属（10 分）

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

说明/提示

解法：

D:飞机降落（10 分）

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

说明/提示

解法：

E:接龙数列（15 分）

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

说明/提示

解法：

F:岛屿个数（15 分）

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

说明/提示

解法：

G:字串简写（20 分）

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

说明/提示

解法：

H:整数删除（20 分）

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

说明/提示

解法：

I:景区导游（25 分）

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

说明/提示

解法：

J:砍树（25 分）

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

说明/提示

解法：