正文

第十四届蓝桥杯c/c++_大学b组省赛真题

屠一乐  屠一乐  2023-04-11  283

关键词：

C/C++_B组

试题 A: 日期统计
试题 B: 01 串的熵
试题 C: 冶炼金属
试题 D: 飞机降落
试题 E: 接龙数列
试题 F: 岛屿个数
试题 G: 子串简写
试题 H: 整数删除
试题 I: 景区导游
试题 J: 砍树

【考生须知】
考试开始后，选手首先下载题目，并使用考场现场公布的解压密码解压试题。
考试时间为 4 小时。考试期间选手可浏览自己已经提交的答案，被浏览的答案允许拷贝。时间截止后，将无法继续提交或浏览答案。
对同一题目，选手可多次提交答案，以最后一次提交的答案为准。
选手必须通过浏览器方式提交自己的答案。选手在其它位置的作答或其它方式提交的答案无效。
试题包含“结果填空”和“程序设计”两种题型。
结果填空题：要求选手根据题目描述直接填写结果。求解方式不限。不要求源代码。把结果填空的答案直接通过网页提交即可，不要书写多余的内容。
程序设计题：要求选手设计的程序对于给定的输入能给出正确的输出结果。考生的程序只有能运行出正确结果才有机会得分。
注意：在评卷时使用的输入数据与试卷中给出的示例数据可能是不同的。选手的程序必须是通用的，不能只对试卷中给定的数据有效。
对于编程题目，要求选手给出的解答完全符合 GNU C/C++ 标准，不能使用诸如绘图、Win32API、中断调用、硬件操作或与操作系统相关的 API。
代码中允许使用 STL 类库。
注意: main 函数结束必须返回 0。
注意: 所有依赖的函数必须明确地在源文件中 #include ，不能通过工程设置而省略常用头文件。
所有源码必须在同一文件中。调试通过后，拷贝提交。提交时，注意选择所期望的编译器类型。

试题 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 年的日期。对于相同的日期你只需要统计一次即可。

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

试题 B: 01 串的熵

本题总分：5 分

【问题描述】
对于一个长度为 n 的 01 串 S = x1 x2 x3…xn，香农信息熵的定义为 H(S ) =
−Σn p(xi) log2(p(xi))，其中 p(0), p(1) 表示在这个 01 串中 0 和 1 出现的占比。比如，对于 S = 100 来说，信息熵 H(S ) = − 1 log2(1 ) − 2 log2(2 ) − 2 log2(2 ) =
1.3083。对于一个长度为 23333333 的 01 串，如果其信息熵为 11625907.5798，
且 0 出现次数比 1 少，那么这个 01 串中 0 出现了多少次？

试题 C: 冶炼金属

时间限制: 1.0s 内存限制: 256.0MB 本题总分：10 分

【问题描述】
小蓝有一个神奇的炉子用于将普通金属 O 冶炼成为一种特殊金属 X。这个炉子有一个称作转换率的属性 V，V 是一个正整数，这意味着消耗 V 个普通金属 O 恰好可以冶炼出一个特殊金属 X，当普通金属 O 的数目不足 V 时，无法继续冶炼。
现在给出了 N 条冶炼记录，每条记录中包含两个整数 A 和 B，这表示本次投入了 A 个普通金属 O，最终冶炼出了 B 个特殊金属 X。每条记录都是独立的，这意味着上一次没消耗完的普通金属 O 不会累加到下一次的冶炼当中。
根据这 N 条冶炼记录，请你推测出转换率 V 的最小值和最大值分别可能是多少，题目保证评测数据不存在无解的情况。

【输入格式】
第一行一个整数 N，表示冶炼记录的数目。
接下来输入 N 行，每行两个整数 A、B，含义如题目所述。

【输出格式】
输出两个整数，分别表示 V 可能的最小值和最大值，中间用空格分开。

【样例输入】

3
75 3
53 2
59 2

【样例输出】
20 25

【样例说明】
当 V = 20 时，有：⌊ 75 ⌋ = 3，⌊ 53 ⌋ = 2，⌊ 59 ⌋ = 2，可以看到符合所有冶炼

记录。

20 20 20

当 V = 25 时，有：⌊ 75 ⌋ = 3，⌊ 53 ⌋ = 2，⌊ 59 ⌋ = 2，可以看到符合所有冶炼

记录。

25 25 25

且再也找不到比 20 更小或者比 25 更大的符合条件的 V 值了。

【评测用例规模与约定】
对于 30% 的评测用例，1 ≤ N ≤ 102。对于 60% 的评测用例，1 ≤ N ≤ 103。
对于 100% 的评测用例，1 ≤ N ≤ 104，1 ≤ B ≤ A ≤ 109。

试题 D: 飞机降落

时间限制: 2.0s 内存限制: 256.0MB 本题总分：10 分

【问题描述】
N 架飞机准备降落到某个只有一条跑道的机场。其中第 i 架飞机在 Ti 时刻到达机场上空，到达时它的剩余油料还可以继续盘旋 Di 个单位时间，即它最早可以于 Ti 时刻开始降落，最晚可以于 Ti + Di 时刻开始降落。降落过程需要 Li 个单位时间。
一架飞机降落完毕时，另一架飞机可以立即在同一时刻开始降落，但是不能在前一架飞机完成降落前开始降落。
请你判断 N 架飞机是否可以全部安全降落。

【输入格式】
输入包含多组数据。
第一行包含一个整数 T ，代表测试数据的组数。对于每组数据，第一行包含一个整数 N。
以下 N 行，每行包含三个整数：Ti，Di 和 Li。

【输出格式】
对于每组数据，输出 YES 或者 NO，代表是否可以全部安全降落。

【样例输入】
2
3
0 100 10
10 10 10
0 2 20
3

0 10 20
10 10 20
20 10 20

【样例输出】
YES NO

【样例说明】
对于第一组数据，可以安排第 3 架飞机于 0 时刻开始降落，20 时刻完成降
落。安排第 2 架飞机于 20 时刻开始降落，30 时刻完成降落。安排第 1 架飞机于 30 时刻开始降落，40 时刻完成降落。
对于第二组数据，无论如何安排，都会有飞机不能及时降落。

【评测用例规模与约定】
对于 30% 的数据，N ≤ 2。
对于 100% 的数据，1 ≤ T ≤ 10，1 ≤ N ≤ 10，0 ≤ Ti, Di, Li ≤ 105。

试题 E: 接龙数列

时间限制: 1.0s 内存限制: 256.0MB 本题总分：15 分

【问题描述】
对于一个长度为 K 的整数数列：A1, A2, . . . , AK，我们称之为接龙数列当且仅当 Ai 的首位数字恰好等于 Ai−1 的末位数字 (2 ≤ i ≤ K)。
例如 12, 23, 35, 56, 61, 11 是接龙数列；12, 23, 34, 56 不是接龙数列，因为 56
的首位数字不等于 34 的末位数字。所有长度为 1 的整数数列都是接龙数列。现在给定一个长度为 N 的数列 A1, A2, . . . , AN，请你计算最少从中删除多少
个数，可以使剩下的序列是接龙序列？

【输入格式】
第一行包含一个整数 N。
第二行包含 N 个整数 A1, A2, . . . , AN。

【输出格式】
一个整数代表答案。

【样例输入】
5
11 121 22 12 2023

【样例输出】
1

【样例说明】
删除 22，剩余 11, 121, 12, 2023 是接龙数列。

【评测用例规模与约定】
对于 20% 的数据，1 ≤ N ≤ 20。对于 50% 的数据，1 ≤ N ≤ 10000。
对于 100% 的数据，1 ≤ N ≤ 105，1 ≤ Ai ≤ 109。所有 Ai 保证不包含前导 0。

试题 F: 岛屿个数

时间限制: 2.0s 内存限制: 256.0MB 本题总分：15 分

【问题描述】
小蓝得到了一副大小为 M × N 的格子地图，可以将其视作一个只包含字符‘0’（代表海水）和 ‘1’（代表陆地）的二维数组，地图之外可以视作全部是海水，每个岛屿由在上/下/左/右四个方向上相邻的 ‘1’ 相连接而形成。
在岛屿 A 所占据的格子中，如果可以从中选出 k 个不同的格子，使得他们的坐标能够组成一个这样的排列：(x0, y0), (x1, y1), . . . , (xk−1, yk−1)，其中(x(i+1)%k, y(i+1)%k) 是由 (xi, yi) 通过上/下/左/右移动一次得来的 (0 ≤ i ≤ k − 1)，此时这 k 个格子就构成了一个 “环”。如果另一个岛屿 B 所占据的格子全部位于这个 “环” 内部，此时我们将岛屿 B 视作是岛屿 A 的子岛屿。若 B 是 A 的子岛屿，C 又是 B 的子岛屿，那 C 也是 A 的子岛屿。
请问这个地图上共有多少个岛屿？在进行统计时不需要统计子岛屿的数目。

【输入格式】
第一行一个整数 T ，表示有 T 组测试数据。
接下来输入 T 组数据。对于每组数据，第一行包含两个用空格分隔的整数M、N 表示地图大小；接下来输入 M 行，每行包含 N 个字符，字符只可能是‘0’ 或 ‘1’ 。
【输出格式】
对于每组数据，输出一行，包含一个整数表示答案。

【样例输入】
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 中均没有
“环”。

【评测用例规模与约定】
对于 30% 的评测用例，1 ≤ M, N ≤ 10。
对于 100% 的评测用例，1 ≤ T ≤ 10，1 ≤ M, N ≤ 50。

试题 G: 子串简写

时间限制: 1.0s 内存限制: 256.0MB 本题总分：20 分

【问题描述】
程序猿圈子里正在流行一种很新的简写方法：对于一个字符串，只保留首尾字符，将首尾字符之间的所有字符用这部分的长度代替。例如 internation- alization 简写成 i18n，Kubernetes （注意连字符不是字符串的一部分）简写成 K8s, Lanqiao 简写成 L5o 等。
在本题中，我们规定长度大于等于 K 的字符串都可以采用这种简写方法
（长度小于 K 的字符串不配使用这种简写）。
给定一个字符串 S 和两个字符 c1 和 c2，请你计算 S 有多少个以 c1 开头
c2 结尾的子串可以采用这种简写？

【输入格式】
第一行包含一个整数 K。
第二行包含一个字符串 S 和两个字符 c1 和 c2。

【输出格式】
一个整数代表答案。

【样例输入】
4
abababdb a b

【样例输出】
6

【样例说明】
符合条件的子串如下所示，中括号内是该子串：

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

【评测用例规模与约定】
对于 20% 的数据，2 ≤ K ≤ |S | ≤ 10000。
对于 100% 的数据，2 ≤ K ≤ |S | ≤ 5 × 105。S 只包含小写字母。c1 和 c2 都是小写字母。
|S | 代表字符串 S 的长度。

试题 H: 整数删除

时间限制: 1.0s 内存限制: 256.0MB 本题总分：20 分

【问题描述】
给定一个长度为 N 的整数数列：A1, A2, . . . , AN。你要重复以下操作 K 次：每次选择数列中最小的整数（如果最小值不止一个，选择最靠前的），将其
删除。并把与它相邻的整数加上被删除的数值。
输出 K 次操作后的序列。

【输入格式】
第一行包含两个整数 N 和 K。
第二行包含 N 个整数，A1, A2, A3, . . . , AN。

【输出格式】
输出 N − K 个整数，中间用一个空格隔开，代表 K 次操作后的序列。
【样例输入】
5 3
1 4 2 8 7

【样例输出】
17 7

【样例说明】
数列变化如下，中括号里的数是当次操作中被选择的数：

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

[7] 10 7
17 7

【评测用例规模与约定】
对于 20% 的数据，1 ≤ K < N ≤ 10000。
对于 100% 的数据，1 ≤ K < N ≤ 5 × 105，0 ≤ Ai ≤ 108。

试题 I: 景区导游

时间限制: 5.0s 内存限制: 256.0MB 本题总分：25 分

【问题描述】
某景区一共有 N 个景点，编号 1 到 N。景点之间共有 N − 1 条双向的摆渡车线路相连，形成一棵树状结构。在景点之间往返只能通过这些摆渡车进行，需要花费一定的时间。
小明是这个景区的资深导游，他每天都要按固定顺序带客人游览其中 K 个景点：A1, A2, . . . , AK。今天由于时间原因，小明决定跳过其中一个景点，只带游客按顺序游览其中 K − 1 个景点。具体来说，如果小明选择跳过 Ai，那么他会按顺序带游客游览 A1, A2, . . . , Ai−1, Ai+1, . . . , AK, (1 ≤ i ≤ K)。
请你对任意一个 Ai，计算如果跳过这个景点，小明需要花费多少时间在景点之间的摆渡车上？

【输入格式】
第一行包含 2 个整数 N 和 K。
以下 N − 1 行，每行包含 3 个整数 u, v 和 t，代表景点 u 和 v 之间有摆渡车线路，花费 t 个单位时间。
最后一行包含 K 个整数 A1, A2, . . . , AK 代表原定游览线路。

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

【样例输入】
6 4
1 2 1
1 3 1
3 4 2

3 5 2
4 6 3
2 6 5 1

【样例输出】
10 7 13 14

【样例说明】
原路线是 2 → 6 → 5 → 1。
当跳过 2 时，路线是 6 → 5 → 1，其中 6 → 5 花费时间 3 + 2 + 2 = 7，
5 → 1 花费时间 2 + 1 = 3，总时间花费 10。
当跳过 6 时，路线是 2 → 5 → 1，其中 2 → 5 花费时间 1 + 1 + 2 = 4，
5 → 1 花费时间 2 + 1 = 3，总时间花费 7。
当跳过 5 时，路线是 2 → 6 → 1，其中 2 → 6 花费时间 1 + 1 + 2 + 3 = 7，
6 → 1 花费时间 3 + 2 + 1 = 6，总时间花费 13。
当跳过 1 时，路线时 2 → 6 → 5，其中 2 → 6 花费时间 1 + 1 + 2 + 3 = 7，
6 → 5 花费时间 3 + 2 + 2 = 7，总时间花费 14。
【评测用例规模与约定】
对于 20% 的数据，2 ≤ K ≤ N ≤ 102。对于 40% 的数据，2 ≤ K ≤ N ≤ 104。
对于 100% 的数据，2 ≤ K ≤ N ≤ 105，1 ≤ u, v, Ai ≤ N，1 ≤ t ≤ 105。保证
Ai 两两不同。

试题 J: 砍树

时间限制: 1.0s 内存限制: 256.0MB 本题总分：25 分

【问题描述】
给定一棵由 n 个结点组成的树以及 m 个不重复的无序数对 (a1, b1), (a2, b2),
. . . , (am, bm)，其中 ai 互不相同，bi 互不相同，ai ≠ bj(1 ≤ i, j ≤ m)。
小明想知道是否能够选择一条树上的边砍断，使得对于每个 (ai, bi) 满足 ai 和 bi 不连通，如果可以则输出应该断掉的边的编号（编号按输入顺序从 1 开始），否则输出 -1。
【输入格式】
输入共 n + m 行，第一行为两个正整数 n，m。
后面 n − 1 行，每行两个正整数 xi，yi 表示第 i 条边的两个端点。后面 m 行，每行两个正整数 ai，bi。

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

【样例输入】

6 2
1 2
2 3
4 3
2 5
6 5
3 6
4 5

【样例输出】
4

【样例说明】
断开第 2 条边后形成两个连通块：3, 4，1, 2, 5, 6，满足 3 和 6 不连通，4
和 5 不连通。
断开第 4 条边后形成两个连通块：1, 2, 3, 4，5, 6，同样满足 3 和 6 不连通，4 和 5 不连通。
4 编号更大，因此答案为 4。

【评测用例规模与约定】
对于 30% 的数据，保证 1 < n ≤ 1000。
对于 100% 的数据，保证 1 < n ≤ 105，1 ≤ m ≤ n 。

蓝桥杯省赛c++组别大学b组历年题解

第十届蓝桥杯C/C++B组省赛题解第十一届蓝桥杯7月场次b组题解第十一届蓝桥杯省赛B组(C/C++组)(第二场)第十二届蓝桥杯（省赛）（C/C++大学B组）查看详情

蓝桥杯省赛c++组别大学b组历年题解

第十届蓝桥杯C/C++B组省赛题解第十一届蓝桥杯7月场次b组题解第十一届蓝桥杯省赛B组(C/C++组)(第二场)第十二届蓝桥杯（省赛）（C/C++大学B组）查看详情

蓝桥杯省赛c++组别大学b组历年题解

第十届蓝桥杯C/C++B组省赛题解第十一届蓝桥杯7月场次b组题解第十一届蓝桥杯省赛B组(C/C++组)(第二场)第十二届蓝桥杯（省赛）（C/C++大学B组）查看详情

第十四届蓝桥杯省赛c/c++大学b组题解(代码片段)

第十四届蓝桥杯省赛c/c++大学B组题解个人答案，有错漏感谢指正哈试题A:日期统计本题总分：5分【问题描述】小蓝现在有一个长度为100的数组，数组中的每个元素的值都在0到9的范围之内。数组中的元素从... 查看详情

2023年第十四届蓝桥杯将至来看看第十二届蓝桥杯javab组题目如何(代码片段)

...天就要考蓝桥杯了，今年报的java组，下午做了套第十二届蓝桥杯java组真题分享一下5道填空，5道编程二、2021年蓝桥杯javaB组省赛真题目录A、B、C、D、E为填空题A:ASC[5分]思路⭐%%%代码🌟publicclassMain publicstaticvoidmain(... 查看详情

第十届蓝桥杯c/c++b组省赛题解(代码片段)

A.组队答案：490本题很简单可以直接手算，找到每列最高分数，且做到不重复就可以，有重复可选择次高分数B年号字串【问题描述】小明用字母A对应数字1，B对应2，以此类推，用Z对应26。对于27以上的... 查看详情

第十四届蓝桥杯省赛c++b组（个人经历+题解）(代码片段)

...气还是不错的哈哈哈。时隔一个月，有些平台上已经有了第十四届蓝桥杯的题目，我打算记录一下自己参赛的经历并写下每道题的题解。PS:本博客中编程题的代码都是在Acwing平台上提交且通过的代码。A：日期统计暴力枚举解题... 查看详情

蓝桥杯2020第十一届javaa组省赛

目录试题A:门牌制作【问题描述】【答案提交】【题解】试题B:既约分数【问题描述】【答案提交】【题解】试题C:蛇形填数【问题描述】... 查看详情

第十二届蓝桥杯2021年省赛真题(java大学b组)第一场(更新中)(代码片段)

蓝桥杯2021年省赛真题(Java大学B组）#AASC#B卡片朴素解法弯道超车#C直线直线方程集合分式消除误差平面几何#D货物摆放暴力搜索缩放质因子#E路径搜索深度优先搜索记忆化搜索枝剪广搜双向搜索单源最短路径DijkstraFloydA*动态规... 查看详情

java实现第十二届蓝桥杯c++b组省赛真题（希望能和各位佬能一起讨论算法题：讨论群：99979568）

如有错误，还请佬评论或私信指出（写的稍些急）等后面在补充补充解题思路，在补一套C++实现，再也不肝博客了/(ㄒoㄒ)/~~（由于上传图片有限制，如果描述不清楚点击手写题解）手写题解... 查看详情

第十届蓝桥杯c/c++b组省赛题解(代码片段)

第十四届蓝桥杯大赛软件赛省赛-试题b---01串的熵解题思路+完整代码(代码片段)

欢迎访问个人网站来查看此文章：http://www.ghost-him.com/posts/db23c395/问题描述对于一个长度为n的01串S=x1x2x3...xnS=x_1x_2x_3...x_nS=x1x2x3...xn，香农信息熵的定义为H(S)=−∑1np(xi)log2(p(xi))H(S)=−\\textstyle\\sum_1^np... 查看详情

第十二届蓝桥杯省赛第一场c/c++b组真题及部分题解(代码片段)

上一篇博客：算法竞赛常用知识写在前面：大家好！我是晴空๓。如果博客中有不足或者的错误的地方欢迎在评论区或者私信我指正，感谢大家的不吝赐教。我的唯一博客更新地址是：https://ac-fun.blog.csdn.net/... 查看详情

第十一届蓝桥杯大赛软件类省赛第二场c/c++大学b组（python解答）(代码片段)

res=0foriinrange(1,2021):res+=str(i).count('2')print(res)答案：624辗转相除法deffunc(a,b): x=a%b while(x!=0): a=b b=x x=a%b returnbnum=0foriinrange(1,2021) 查看详情

2017第八届蓝桥杯c/c++b组省赛个人代码

第一题标题：购物单小明刚刚找到工作，老板人很好，只是老板夫人很爱购物。老板忙的时候经常让小明帮忙到商场代为购物。小明很厌烦，但又不好推辞。这不，XX大促销又来了！老板夫人开出了长长的购物单，都是有打... 查看详情

2021第十二届蓝桥杯大赛软件赛省赛（第二场），c/c++大学b组题解(代码片段)

第1题——求余（5分）直接输出2021%20答案：1#include<bits/stdc++.h>usingnamespacestd;intmain()cout<<2021%20;return0;第2题——双阶乘（5分）求2021的双阶乘，即把1到2021的奇数乘起来查看详情

java&&c++实现第十二届蓝桥杯c++b组省赛真题（希望能和各位佬能一起讨论算法题：讨论群：99979568）(代码片段)

山水有相逢来日皆可期告辞虽然是C++组的，但是和Java组的差不了两道题，大家都可以看一看如有错误，还请佬评论或私信指出（写的稍些急）等后面在补充补充解题思路，在补一套C++实现（... 查看详情