第十四届蓝桥杯省赛C++ B组所有题目以及题解（C++）【编程题均通过100%测试数据】

点击全文阅读

第一题《日期统计》【枚举】

【问题描述】

小蓝现在有一个长度为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

现在他想要从这个数组中寻找一些满足以下条件的子序列:
        1.子序列的长度为 8:
        2.这个子序列可以按照下标顺序组成一个 yyy,ymmdd 格式的日期，并且要求这个日期是 2023 年中的某一天的日期，例如 20230902，20231223。yyyy 表示年份，mm 表示月份，dd 表示天数，当月份或者天数的长度只有一位时需要一个前导零补充。
请你帮小蓝计算下按上述条件一共能找到多少个不同的 2023 年的日期。对于相同的日期你只需要统计一次即可。

【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

【代码】

#include <iostream>using namespace std;int main() {    int array[100] = {        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 daysInMonth[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};    int ans = 0;    for (int month = 1; month <= 12; ++month) {        for (int day = 1; day <= daysInMonth[month]; ++day) {            int dateSeq[8] = {2, 0, 2, 3, month / 10, month % 10, day / 10, day % 10};            int k = 0;            for (int i = 0; i < 100; ++i) {                if (array[i] == dateSeq[k]) {                    ++k;                    if (k == 8) {                        ans++;                        break;                    }                }            }        }    }    printf("%d\n", ans);    return 0;}

【答案】

235

---

第二题《01串的熵01串的熵》【模拟】

【问题描述】

【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

题解来源：用户登录

【代码】

//首先要理解题目的意思//不要被题目的数据吓到//例如当S等于100时，100的信息熵 = -0的个数*(0的个数/总位数)*log2(0的个数/总位数)-1的个数*(1的个数/总位数)*log2(1的个数/总位数)//然后我们  长度为23333333的01串 从0的个数为0开始枚举，直到1.0*23333333/2(因为0的个数比1的个数少，所以一定不会超过23333333的一半)//注意点:在判断浮点数是否等于一个数的时候不能if(x == y)  而是要判断它是否属于某一范围，或者二者差的绝对值属于某一范围一般取<0.01#include<stdio.h>#include<math.h>int main(){    double n = 23333333,sum = 0;    int o = 0,l = 0;    for(o = 0;o <= n/2;o++){        sum = 0;        sum -= o*(o / n) * log2(o / n) + (n - o)*((n - o) / n) * log2((n - o) / n);        if(sum > 11625907.5 && sum < 11625907.6){            printf("%d",o);            break;        }    }    return 0;}

【答案】

11027421

---

第三题《冶炼金属》【数学】

本题题解参考这篇博客：【数学】第十四届蓝桥杯省赛C++ B组《冶炼金属》（C++）

---

第四题《飞机降落》 【DFS+贪心】

本题题解参考这篇博客：【DFS+贪心】第十四届蓝桥杯省赛C++ B组《飞机降落》（C++）

---

第五题《接龙数列》 【DP】

本题题解参考这篇博客：【DP】第十四届蓝桥杯省赛C++ B组《接龙数列》（C++）

---

第六题《岛屿个数》 【DFS】

【题目描述】

【输入格式】

第一行一个整数 T，表示有 T 组测试数据。

接下来输入 T 组数据。

对于每组数据，第一行包含两个用空格分隔的整数 M、N 表示地图大小；接下来输入 M 行，每行包含 N 个字符，字符只可能是 0 或 1。

【输出格式】

对于每组数据，输出一行，包含一个整数表示答案。

【数据范围】

对于 30% 的评测用例，1 ≤ M,N ≤ 10。
对于 100% 的评测用例，1 ≤ T ≤ 10，1 ≤ M,N ≤ 50。

【输入样例】

2
5 5
01111
11001
10101
10001
11111
5 6
111111
100001
010101
100001
111111

【输出样例】

1

3

【样例解释】 

对于第一组数据，包含两个岛屿，下面用不同的数字进行了区分：

01111
11001
10201
10001
11111

岛屿 2 在岛屿 1 的 “环” 内部，所以岛屿 2 是岛屿 1 的子岛屿，答案为 1。

对于第二组数据，包含三个岛屿，下面用不同的数字进行了区分：

111111
100001
020301
100001
111111

注意岛屿 3 并不是岛屿 1 或者岛屿 2 的子岛屿，因为岛屿 1 和岛屿 2 中均没有“环”。

【思路】

题解来源：AcWing 4959. 岛屿个数 - AcWing

在地图周围一圈增加一圈0作为外海， dfs遍历外海每一个方格， 若与外海方格相邻的岛屿未被遍历过，那么这就是一个新的岛屿， 再用一个dfs去遍历这个岛。 

【代码】

#include <bits/stdc++.h>using namespace std;const int N = 60;int g[N][N], n, m, res = 0;bool st[N][N];int dx[] = {0, 0, 1, -1},    dy[] = {1, -1, 0, 0};void dfs_1(int r, int c){    st[r][c] = true;    //四向连通    for (int i = 0; i < 4; i ++)     {        int x = dx[i] + r, y = dy[i] + c;        if (st[x][y] || g[x][y] == 0) continue;        dfs_1(x, y);    }}void dfs_0(int r, int c){    st[r][c] = true;    //八向连通    for (int i = -1; i <= 1; i ++)        for (int j = -1; j <= 1; j ++)        {            int x = r + i, y = c + j;            if (x < 0 || x > n + 1 || y < 0 || y > m + 1 || st[x][y]) continue;            if (g[x][y] == 0) dfs_0(x, y);            else dfs_1(x, y), res ++;        }}int main (){    int T; cin >> T;    while (T --)     {        memset(g, 0, sizeof g);        memset(st, false, sizeof st);        cin >> n >> m; res = 0;        for (int i = 1; i <= n; i ++)            for (int j = 1; j <= m; j ++)             {                char c; cin >> c;                g[i][j] = c - '0';            }        dfs_0(0, 0);//从一个外海方格开始dfs        cout << res << endl;    }    return 0;}

---

第七题《子串简写》【二分】

【题目描述】

【输入格式】 

第一行包含一个整数 K。

第二行包含一个字符串 S 和两个字符 

【输入样例】

4
abababdb a b

【输出样例】

6

【样例解释】

符合条件的子串如下所示，中括号内是该子串

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

【思路】

题解来源：AcWing 4960. 子串简写 - AcWing

二分/双指针都行
先按照位置处理出来两个数组
然后枚举开头的位置，二分出结尾在另一个数组的合法位置，直接累加答案

【代码】

#include<iostream>#include <vector>using namespace std;int k;char st,ed;string p;void solve(){    cin >> k;    cin >> p >> st >> ed;    vector<int> ps, pe;    for (int i = 0; i < p.size(); i ++)    {        if(p[i] == st) ps.push_back(i);        if(p[i] == ed) pe.push_back(i);    }    long long ans = 0;    for (int i = 0; i < ps.size(); i ++)    {        int x = ps[i];        int X = x + k - 1;        int l = 0, r = pe.size() - 1;        while (l < r)        {            int mid = l + r >> 1;            if(pe[mid] >= X) r = mid;            else l = mid + 1;        }        if(pe[l] >= X) ans += pe.size() - l;    }    cout << ans << endl;}int main(){    ios::sync_with_stdio(false);    cin.tie(0);    solve();    return 0;}

---

第八题《整数删除》【双向链表+最小堆】

【题目描述】

给定一个长度为 N 的整数数列：,,...,。

%20

你要重复以下操作 K 次：

%20

每次选择数列中最小的整数（如果最小值不止一个，选择最靠前的），将其删除，并把与它相邻的整数加上被删除的数值。

%20

输出 K 次操作后的序列。

%20

【输入格式】

%20

第一行包含两个整数 N 和 K。

%20

第二行包含 N 个整数，,,...,。

%20

【输出格式】

%20

输出 N%20− K%20个整数，中间用一个空格隔开，代表 K 次操作后的序列。

%20

【数据范围】

%20

对于 20% 的数据，1%20≤%20K%20<%20N%20≤%2010000。
%20对于 100%%20的数据，1%20≤%20K%20<%20N%20≤%205×，0%20≤%20Ai%20≤ 。

%20

【输入样例】

%20

%20%205%203
%201%204%202%208%207%20

%20

【输出样例】

%20

%20%20

17%207

%20

%20

【样例解释】

%20

数列变化如下，中括号里的数是当次操作中被选择的数：

%20

%20%20[1]%204%202%208%207
%205%20[2]%208%207
%20[7]%2010%207
%2017%207%20

%20

【思路】

%20

%20%20

题解来源：AcWing%204961.%20整数删除%20|%20堆%20|%20双向链表%20-%20AcWing

%20

%20

【代码】

#pragma GCC target ("avx")#pragma GCC optimize (2, 3, "Ofast", "inline", "-ffast-math")#include <bits/stdc++.h>using namespace std;using ll = long long;__attribute__((unused)) int io_ = []() {    ios::sync_with_stdio(false);    cin.tie(nullptr), cout.tie(nullptr);    return 0;}();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】

【题目描述】

某景区一共有 N 个景点，编号 1 到 N。

景点之间共有 N−1 条双向的摆渡车线路相连，形成一棵树状结构。

在景点之间往返只能通过这些摆渡车进行，需要花费一定的时间。

小明是这个景区的资深导游，他每天都要按固定顺序带客人游览其中 K 个景点：,,...,。

%20

今天由于时间原因，小明决定跳过其中一个景点，只带游客按顺序游览其中 K−1%20个景点。

%20

具体来说，如果小明选择跳过 ，那么他会按顺序带游客游览 ,,...,,,...,(1%20≤%20i%20≤%20K)。

%20

请你对任意一个 ，计算如果跳过这个景点，小明需要花费多少时间在景点之间的摆渡车上？

%20

【输入格式】

%20

第一行包含 2 个整数 N 和 K。

%20

以下 N−1%20行，每行包含 3 个整数 u,v%20和 t，代表景点 u%20和 v 之间有摆渡车线路，花费 t 个单位时间。

%20

最后一行包含 K 个整数 ,,...,%20代表原定游览线路。

%20

【输出格式】

%20

输出 K 个整数，其中第 i 个代表跳过  之后，花费在摆渡车上的时间。

%20

【数据范围】

%20

对于 20% 的数据，2%20≤%20K%20≤%20N%20≤%20100。
%20对于 40% 的数据，2%20≤%20K%20≤%20N%20≤%2010000。
%20对于 100% 的数据，2≤K≤N≤100000，1≤u,v,≤N，1≤t≤100000。保证  两两不同。

%20

【输入样例】

%20

%20%20

6%204
%201%202%201
%201%203%201
%203%204%202
%203%205%202
%204%206%203
%202%206%205%201

%20

%20

【输出样例】

%20

%20%20

10%207%2013%2014

%20

%20

【样例解释】

%20

原路线是 2→6→5→1。

%20

当跳过 2 时，路线是 6→5→1，其中 6→5 花费时间 3+2+2=7，5→1%20花费时间 2+1=3，总时间花费 10。

%20

当跳过 6 时，路线是 2→5→1，其中 2→5%20花费时间 1+1+2=4，5→1%20花费时间 2+1=3，总时间花费 7。

%20

当跳过 5 时，路线是 2→6→1，其中 2→6%20花费时间 1+1+2+3=7，6→1%20花费时间 3+2+1=6，总时间花费 13。

%20

当跳过 1 时，路线时 2→6→55，其中 2→6%20花费时间 1+1+2+3=7，6→5%20花费时间 3+2+2=7，总时间花费 14。

%20

【代码】

%20

#include%20<iostream>#include<cstring>#include<algorithm>using%20namespace%20std;typedef%20long%20long%20LL;const%20int%20N%20=%201e5%20+%2010,%20M%20=%20N%20*%202,%20K%20=%2020;int%20h[N],%20e[M],%20w[M],%20ne[M],%20idx;int%20depth[N],%20f[N][K];LL%20d[N];int%20q[N];int%20n,%20k;void%20add(int%20a,%20int%20b,%20int%20c){%20%20%20%20e[idx]%20=%20b,%20w[idx]%20=%20c,%20ne[idx]%20=%20h[a],%20h[a]%20=%20idx++;}void%20dfs(int%20u,%20int%20fa){%20%20%20%20depth[u]%20=%20depth[fa]%20+%201;%20%20%20%20f[u][0]%20=%20fa;%20%20%20%20for%20(int%20i%20=%201;%20i%20<=%2019;%20i++)%20%20%20%20%20%20%20%20f[u][i]%20=%20f[f[u][i%20-%201]][i%20-%201];%20%20%20%20for%20(int%20i%20=%20h[u];%20~i;%20i%20=%20ne[i])%20%20%20%20{%20%20%20%20%20%20%20%20int%20j%20=%20e[i];%20%20%20%20%20%20%20%20if%20(j%20==%20fa)%20continue;%20%20%20%20%20%20%20%20d[j]%20=%20d[u]%20+%20w[i];%20%20%20%20%20%20%20%20dfs(j,%20u);%20%20%20%20}}int%20lca(int%20a,%20int%20b){%20%20%20%20if%20(depth[a]%20<%20depth[b])%20swap(a,%20b);%20%20%20%20for%20(int%20i%20=%2019;%20~i;%20i--)%20%20%20%20%20%20%20%20if%20(depth[f[a][i]]%20>=%20depth[b])%20%20%20%20%20%20%20%20%20%20%20%20a%20=%20f[a][i];%20%20%20%20if%20(a%20==%20b)%20return%20a;%20%20%20%20for%20(int%20i%20=%2019;%20~i;%20i--)%20%20%20%20%20%20%20%20if%20(f[a][i]%20!=%20f[b][i])%20%20%20%20%20%20%20%20{%20%20%20%20%20%20%20%20%20%20%20%20a%20=%20f[a][i];%20%20%20%20%20%20%20%20%20%20%20%20b%20=%20f[b][i];%20%20%20%20%20%20%20%20}%20%20%20%20return%20f[a][0];}LL%20get(int%20a,%20int%20b){%20%20%20%20int%20p%20=%20lca(a,%20b);%20%20%20%20return%20d[a]%20+%20d[b]%20-%202%20*%20d[p];}int%20main(){%20%20%20%20memset(h,%20-1,%20sizeof%20h);%20%20%20%20scanf("%d%d",%20&n,%20&k);%20%20%20%20for%20(int%20i%20=%201;%20i%20<%20n;%20i++)%20%20%20%20{%20%20%20%20%20%20%20%20int%20a,%20b,%20c;%20%20%20%20%20%20%20%20scanf("%d%d%d",%20&a,%20&b,%20&c);%20%20%20%20%20%20%20%20add(a,%20b,%20c),%20add(b,%20a,%20c);%20%20%20%20}%20%20%20%20dfs(1,%200);%20%20%20%20for%20(int%20i%20=%200;%20i%20<%20k;%20i++)%20scanf("%d",%20&q[i]);%20%20%20%20LL%20sum%20=%200;%20%20%20%20for%20(int%20i%20=%200;%20i%20+%201%20<%20k;%20i++)%20sum%20+=%20get(q[i],%20q[i%20+%201]);%20%20%20%20for%20(int%20i%20=%200;%20i%20<%20k;%20i++)%20%20%20%20{%20%20%20%20%20%20%20%20LL%20res%20=%20sum;%20%20%20%20%20%20%20%20//%20跳过i(i不是端点),等同于砍掉i-1->i和i->i+1,加上i-1->i+1%20%20%20%20%20%20%20%20if%20(i%20&&%20i%20!=%20k%20-%201)%20res%20+=%20get(q[i%20-%201],%20q[i%20+%201])%20-%20get(q[i%20-%201],%20q[i])%20-%20get(q[i],%20q[i%20+%201]);%20%20%20%20%20%20%20%20//%20跳过i(i是左端点),等同于砍掉i->i+1%20%20%20%20%20%20%20%20else%20if%20(!i)%20res%20-=%20get(q[i],%20q[i%20+%201]);%20%20%20%20%20%20%20%20//%20跳过i(i是右端点),等同于砍掉i-1->i%20%20%20%20%20%20%20%20else%20res%20-=%20get(q[i%20-%201],%20q[i]);%20%20%20%20%20%20%20%20printf("%lld%20",%20res);%20%20%20%20}%20%20%20%20puts("");%20%20%20%20return%200;}

%20

---

%20

第十题《砍树》【LCA+树上差分】

%20

【题目描述】

%20

【输入格式】

输入共 n+m 行，第一行为两个正整数 n,m。

后面 n−1 行，每行两个正整数 , 表示第 i 条边的两个端点。

%20

后面 m 行，每行两个正整数%20,。

%20

【输出格式】

%20

一行一个整数，表示答案，如有多个答案，输出编号最大的一个。

%20

【数据范围】

%20

对于 30% 的数据，保证 1%20<%20n%20≤%201000。
%20对于 100% 的数据，保证 1%20<%20n%20≤%20，1%20≤%20m%20≤ 。

%20

【输入样例】

%20

%20%206%202
%201%202
%202%203
%204%203
%202%205
%206%205
%203%206
%204%205%20

%20

【输出样例】

%20

%20%20

4

%20

%20

【样例解释】

%20

断开第 2 条边后形成两个连通块：{3,4}，{1,2,5,6}，满足 3 和 6 不连通，4 和 5 不连通。

%20

断开第 4 条边后形成两个连通块：{1,2,3,4}，{5,6}，同样满足 3 和 6 不连通，4 和 5 不连通。

%20

4 编号更大，因此答案为 4。

%20

【思路】

%20

%20%20

题解来源：4963.%20砍树%20-%20AcWing题库

%20

%20

【代码】

#include<bits/stdc++.h>using namespace std;typedef long long LL;typedef unsigned long long uLL;typedef pair<int, int> PII;#define pb(s) push_back(s);#define SZ(s) ((int)s.size());#define ms(s,x) memset(s, x, sizeof(s))#define all(s) s.begin(),s.end()const int inf = 0x3f3f3f3f;const int mod = 1000000007;const int N = 200010;int n, m;std::vector<int> e[N];int depth[N], fa[N][32];int f[N];int root;int ans;map<PII, int> mp;void bfs(int root){    ms(depth, 0x3f);    depth[0] = 0, depth[root] = 1;    queue<int> q;    q.push(root);    while (!q.empty()) {        auto t = q.front();        q.pop();        for (int j : e[t]) {            if (depth[j] > depth[t] + 1) {                depth[j] = depth[t] + 1;                q.push(j);                fa[j][0] = t;                for (int k = 1; k <= 15; k++) {                    fa[j][k] = fa[fa[j][k - 1]][k - 1];                }            }        }    }}int lca(int a, int b) {    if (depth[a] < depth[b]) swap(a, b);    for (int k = 15; k >= 0; k--) {        if (depth[fa[a][k]] >= depth[b]) {            a = fa[a][k];        }    }    if (a == b) return a;    for (int k = 15; k >= 0; --k) {        if (fa[a][k] != fa[b][k]) {            a = fa[a][k];            b = fa[b][k];        }    }    return fa[a][0];}int dfs(int u, int fa) {    int res = f[u];    for (auto v : e[u]) {        if (v == fa) continue;        int g = dfs(v, u);        if (g == m) {            ans = max(ans, mp[ {v, u}]);        }        res += g;    }    return res;}void solve(){    cin >> n >> m;    for (int i = 0; i < n - 1; ++i) {        int u, v;        cin >> u >> v;        mp[ {u, v}] = mp[ {v, u}] = i + 1;        e[u].push_back(v);        e[v].push_back(u);    }    bfs(1);    for (int i = 0; i < m; ++i) {        int u, v;        cin >> u >> v;        int z = lca(u, v);        f[u]++;        f[v]++;        f[z] -= 2;    }    dfs(1, -1);    cout << (ans == 0 ? -1 : ans) << '\n';}int main(){    ios_base :: sync_with_stdio(false);    cin.tie(0); cout.tie(0);    int t = 1;    while (t--)    {        solve();    }    return 0;}

以上内容部分题目题解摘自他人博客题解，在题目处均已标明出处。若有侵权，私信删除。

点击全文阅读