第十六届蓝桥杯大赛软件赛决赛 C/C++ 大学 A 组
·
第十六届蓝桥杯大赛软件赛决赛 C/C++ 大学 A 组
第十六届蓝桥杯大赛软件赛决赛
C/C++ 大学 A 组
【选手须知】
考试开始后，选手首先下载题目，并使用考场现场公布的解压密码解压试
题。
考试时间为 4 小时。考试期间选手可浏览自己已经提交的答案，被浏览的
答案允许拷贝。时间截止后，将无法继续提交或浏览答案。
对同一题目，选手可多次提交答案，以最后一次提交的答案为准。
选手必须通过浏览器方式提交自己的答案。选手在其它位置的作答或其它
方式提交的答案无效。
试题包含“结果填空”和“程序设计”两种题型。
结果填空题：要求选手根据题目描述直接填写结果。求解方式不限。不要
求源代码。把结果填空的答案直接通过网页提交即可，不要书写多余的内容。
程序设计题：要求选手设计的程序对于给定的输入能给出正确的输出结果。
考生的程序只有能运行出正确结果才有机会得分。
注意：在评卷时使用的输入数据与试卷中给出的示例数据可能是不同的。
选手的程序必须是通用的，不能只对试卷中给定的数据有效。
对于编程题目，要求选手给出的解答完全符合 GNU C/C++ 标准，不能使
用诸如绘图、Win32API、中断调用、硬件操作或与操作系统相关的 API。
代码中允许使用 STL 类库。
注意: main 函数结束必须返回 0。
注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>，不能通
过工程设置而省略常用头文件。
所有源码必须在同一文件中。调试通过后，拷贝提交。
提交时，注意选择所期望的编译器类型。
第十六届蓝桥杯大赛软件赛决赛
1第十六届蓝桥杯大赛软件赛决赛 C/C++ 大学 A 组
试题 A: OCR 校正
本题总分：5 分
【问题描述】
小蓝维护着一套 OCR 文字识别系统。最近，系统频繁地将数字 0 和英文
字母 O 混淆，这让他十分头疼。一次测试中，系统将一串长度为 2025 的、全
部由数字 0 组成的字符串识别成了一个长度相同的字符串，但其中只有首尾两
个字符被正确识别为数字 0，其余部分都被错误地识别成了字母 O。
为了校正识别结果，小蓝需将所有的字母 O 替换回数字 0。只是，出于安
全的考虑，该系统不允许直接批量修改所有字母 O，而是设定了如下替换规则：
1. 首次操作，可任意选择一个字母 O，将其替换为数字 0；
2. 后续操作，选择一个与数字 0 相邻的字母 O，将其替换为数字 0；
3. 重复上述步骤，直到所有字母 O 都被替换为数字 0。
小蓝想知道，在满足上述替换规则的情况下，总共有多少种不同的替换顺
序可以将所有字母 O 替换为数字 0。两种替换顺序被视为不同的，当且仅当它
们在某一步骤中选择了不同位置的字符。
现在，请你帮他计算这个数量。由于答案可能很大，你只需给出其对
109 + 7 取余后的结果即可。
【答案提交】
这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个
范围在 0 至 109 + 6 的整数，在提交答案时只填写这个整数，填写多余的内容将
无法得分。
试题 A: OCR 校正
2第十六届蓝桥杯大赛软件赛决赛 C/C++ 大学 A 组
试题 B: 小蓝的生日礼物
本题总分：5 分
【问题描述】
2025 年 6 月 15 日是小蓝的生日，他的妈妈为他准备了一盒特别的生日礼
物：8 张印有数字的卡片，上面分别写着 0, 0, 2, 2, 5, 5, 1, 6。
小蓝想用这些卡片拼凑出三角形。他的想法是，从卡片中选择至少一张卡
片，组成一个数字，作为三角形的一条边长。例如，他可以选择卡片 2，5，1，
组成 251、215、521、512、125、152 等数字。在组合数字时，不允许出现前导
0 ，也不允许组合出值为 0 的数（无法成为三角形的边）。
为了拼成一个三角形，他需要用同样的方法，再选择一些卡片组成第二个
数字，作为三角形的第二条边长，然后再选择一些卡片组成第三个数字，作为
三角形的第三条边长。
需要注意的是，在每次组成边长时，每张卡片只能使用一次。也就是说，
如果卡片 6 已经被用来组成第一个边长，那么在组成第二个和第三个边长时，
就不能再使用这张卡片 6 了。
现在，小蓝想知道，他总共可以拼凑出多少个不同的三角形？这里不同的
三角形指的是三条边长所构成的集合不同。例如，边长为 {1, 2, 3} 和 {2, 3, 4} 的
三角形被认为是不同的，而边长为 {2, 5, 6} 和 {5, 2, 6} 的三角形则被认为是相同
的。
【答案提交】
这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个
整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
试题 B: 小蓝的生日礼物
3第十六届蓝桥杯大赛软件赛决赛C/C++大学A组
试题 C: 土地整平计划
时间限制: 1.0s
内存限制: 256.0MB
本题总分：10 分
【问题描述】
小蓝作为一个二维生物快乐地生活在二维坐标系中，他最近得到了一块土
地，他想把这块土地整平用于修建花园。具体来说，这块土地从左到右长度为
n 格，第 i 格的高度为 hi (i ∈ [1, n])。小蓝每次可以花费代价 w 将一段连续的区
间 [l,r] 中的土地高度都变为 w，其中 l ≤ r，这段区间需要满足以下三组条件之
一：
1. l = 1，r < n，且对于 i ∈ [l,r] 有 hi , hr+1，此时代价 w = hr+1 ；
2. l > 1，r = n，且对于 i ∈ [l,r] 有 hi , hl−1，此时代价 w = hl−1 ；
3. 1 < l ≤ r < n，hl−1 = hr+1，且对于 i ∈ [l,r] 有 hi , hl−1，此时代价
w = hl−1 = hr+1 。
小蓝希望在若干次操作之后将这块土地整平，即所有格子的高度都相等，
并且花费的代价总和最小。请你帮助他计算一下最小花费。
【输入格式】
输入的第一行包含一个正整数 n 。
第二行包含 n 个正整数 h1, h2, · · · , hn ，相邻整数之间使用一个空格分隔。
【输出格式】
输出一行包含一个整数表示答案。
【样例输入】
8
5 4 10 4 20 5 4 5
试题C: 土地整平计划
4第十六届蓝桥杯大赛软件赛决赛 C/C++ 大学 A 组
【样例输出】
10
【样例说明】
样例输出和说明错误
选择将土地高度都变为 5 ，只需操作两次：将 [2, 5] 和 [7, 7] 的高度都变为
5 ，代价总和为 10 。
【评测用例规模与约定】
对于 50% 的评测用例，1 ≤ n ≤ 5000 ；
对于所有评测用例，1 ≤ n ≤ 106 ，1 ≤ hi ≤ 106。
试题 C: 土地整平计划
5第十六届蓝桥杯大赛软件赛决赛C/C++大学A组
试题 D: 生日相遇问题
时间限制: 1.0s
内存限制: 256.0MB
本题总分：10 分
【问题描述】
小蓝和小乔是好朋友，他们想知道在未来的日子里，什么时候他们的生日
会在同一个星期几。已知小蓝的生日是 m 月 d1 日，小乔的生日是 n 月 d2 日，
请你计算从今年开始（今年为 2025 年），未来 k 年内（包括今年，即年份在区
间 [2025, 2025 + k) 中），他们生日在同一个星期几的年份有哪些。
提示：
• 闰年的判断规则为：年份能被 4 整除但不能被 100 整除，或能被 400 整
除。闰年的 2 月有 29 天，非闰年的 2 月有 28 天。
• 如果某人的生日是 2 月 29 日，那么在非闰年中，他/她的生日将被视为 2
月 28 日进行计算。
• 保证输入日期均为合法日期。
【输入格式】
输入一行包含五个正整数 m, d1, n, d2, k，相邻整数之间使用一个空格分隔。
【输出格式】
输出若干行，每行包含一个整数，表示小蓝和小乔生日在同一个星期几的
年份（从今年开始计算，按照年份从小到大的顺序输出）。如果在未来 k 年内没
有这样的年份，输出英文 No Answer。
【样例输入】
1 16 5 21 8
试题D: 生日相遇问题
6第十六届蓝桥杯大赛软件赛决赛 C/C++ 大学 A 组
【样例输出】
2028
2032
【样例说明】
此样例中，小蓝的生日是 1 月 16 日，小乔的生日是 5 月 21 日。
从 2025 到 2032 年间，满足题意的是：
• 2028 年，1 月 16 日是星期日，5 月 21 日也是星期日。
• 2032 年，1 月 16 日是星期五，5 月 21 日也是星期五。
【评测用例规模与约定】
对于 25% 的评测用例，1 ≤ k ≤ 10 ；
对于 50% 的评测用例，1 ≤ k ≤ 20 ；
对于 75% 的评测用例，1 ≤ k ≤ 30 ；
对于所有评测用例，1 ≤ k ≤ 50，1 ≤ m, n ≤ 12，1 ≤ d1, d2 ≤ 31 。
试题 D: 生日相遇问题
7第十六届蓝桥杯大赛软件赛决赛 C/C++ 大学 A 组
试题 E: 树
时间限制: 1.0s
内存限制: 256.0MB
本题总分：15 分
【问题描述】
给定一棵树, 你需要从树上选择若干个点, 使得选择的任意两点之间的距离
均大于 2 。
输出符合条件的选择的方案数 (可以选中任意个, 但不能不选)。由于答案可
能很大, 你只需要输出答案对 998244353 取模的结果。
【输入格式】
输入的第一行包含一个正整数 n 。
接下来 n − 1 行，每行包含两个正整数 ui , vi ，用一个空格分隔，表示结点
ui 和结点 vi 之间有一条边。保证给定的图是一棵树。
【输出格式】
输出一行包含一个整数表示答案。
【样例输入】
6
1 2
1 3
3 4
3 5
5 6
【样例输出】
12
试题 E: 树
8第十六届蓝桥杯大赛软件赛决赛 C/C++ 大学 A 组
【评测用例规模与约定】
对于 40% 的评测用例，1 ≤ n ≤ 20 ；
对于 80% 的评测用例，1 ≤ n ≤ 5000 ；
对于所有评测用例，1 ≤ n ≤ 3 × 105 ，ui , vi ，1 ≤ ui , vi ≤ n 。
试题 E: 树
9第十六届蓝桥杯大赛软件赛决赛 C/C++ 大学 A 组
试题 F: 连锁反应
时间限制: 1.0s
内存限制: 256.0MB
本题总分：15 分
【问题描述】
小蓝在数轴上放置了 n 枚炸弹，第 i 枚炸弹的位置为 pi，其爆炸范围为
[pi − li , pi + ri ]。当一枚炸弹爆炸时，其范围内的所有其他未爆炸的炸弹均会被
引爆。小蓝希望知道至少需要主动引爆多少枚炸弹，才能使得所有炸弹都爆炸。
【输入格式】
输入的第一行包含一个正整数 n 。
接下来 n 行，每行包含三个整数 pi , li ,ri ，相邻整数之间使用一个空格分
隔。
【输出格式】
输出一行包含一个整数表示答案。
【样例输入】
5
3 1 1
1 0 2
6 2 1
9 4 2
10 1 1
【样例输出】
2
【样例说明】
主动引爆炸弹 2, 4，即可引爆所有炸弹。
试题 F: 连锁反应
10第十六届蓝桥杯大赛软件赛决赛 C/C++ 大学 A 组
【评测用例规模与约定】
对于 20% 的评测用例，1 ≤ n ≤ 2000 ；
对于另外 20% 的评测用例，li = 0 ；
对于所有评测用例，1 ≤ n ≤ 200000，0 ≤ pi , li ,ri ≤ 105 。
试题 F: 连锁反应
11第十六届蓝桥杯大赛软件赛决赛C/C++大学A组
试题 G: 翻转硬币
时间限制: 2.0s
内存限制: 256.0MB
本题总分：20 分
【问题描述】
给定 n 个硬币的初始状态, 以及 m 次如下类型的操作:
1 x y: 将 [x, y] 之间的硬币每隔一个翻转一个，即翻转 x, x+2, x+4, · · · , x+2t
( x + 2t ≤ y ) ；
2 x y: 将 [x, y] 之间的硬币每隔两个翻转一个，即翻转 x, x+3, x+6, · · · , x+3t
( x + 3t ≤ y ) ；
3 x y: 将 [x, y] 之间的硬币全部翻转；
4 x y: 查询 [x, y] 之间正面朝上的硬币个数。
【输入格式】
输入的第一行包含两个正整数 n, m ，用一个空格分隔，分别表示硬币数和
操作数。
第二行包含 n 个整数 f1, f2, · · · , fn ，相邻整数之间使用一个空格分隔，表
示每个硬币的初始状态, 其中 fi = 0 表示第 i 个硬币为反面朝上, fi = 1 表示第 i
个硬币为正面朝上。
接下来 m 行，每行包含三个正整数 ai , xi , yi ，相邻整数之间使用一个空格
分隔，表示一次操作。
【输出格式】
输出若干行。对于每次查询操作 (4 x y), 输出一行包含一个整数表示该查
询的答案。
【样例输入】
5 8
1 0 0 1 0
试题G: 翻转硬币
12第十六届蓝桥杯大赛软件赛决赛 C/C++ 大学 A 组
1 2 3
4 1 5
2 3 5
4 2 5
3 1 5
4 2 3
3 1 4
4 1 5
【样例输出】
3
3
0
5
【评测用例规模与约定】
对于 20% 的评测用例，1 ≤ n, m ≤ 5000 ；
对于另外 20% 的评测用例，1 ≤ n, m ≤ 105 ，且没有 1 x y 类型的操作；
对于另外 20% 的评测用例，1 ≤ n, m ≤ 105 ，且没有 2 x y 类型的操作；
对于所有评测用例，1 ≤ n ≤ 5×105，1 ≤ m ≤ 105，fi ∈ {0, 1}，ai ∈ {1, 2, 3, 4}，
1 ≤ xi ≤ yi ≤ n。
试题 G: 翻转硬币
13第十六届蓝桥杯大赛软件赛决赛 C/C++ 大学 A 组
试题 H: 斐波那契数列
时间限制: 1.0s
内存限制: 256.0MB
本题总分：20 分
【问题描述】
斐波那契数列是一个满足如下要求的数列
F
1
= 1
F
2
= 1
Fi = Fi−1 + Fi−2(i > 2)
我们规定一个类似的数列满足
G
1
= 2
G
2
= 3
Gi = Gi−1 × Gi−2(i > 2)
求该数列 G 的前 n 项的乘积对 998244353 取模的结果。
【输入格式】
输入一行包含一个正整数 n 。
【输出格式】
输出一行包含一个整数表示答案。
【样例输入】
5
【样例输出】
69984
试题 H: 斐波那契数列
14第十六届蓝桥杯大赛软件赛决赛 C/C++ 大学 A 组
【评测用例规模与约定】
对于 70% 的评测用例，n ≤ 106 ；
对于所有评测用例，1 ≤ n ≤ 1018 。
试题 H: 斐波那契数列
15第十六届蓝桥杯大赛软件赛决赛 C/C++ 大学 A 组
试题 I: 游戏
时间限制: 1.0s
内存限制: 256.0MB
本题总分：25 分
【问题描述】
小蓝在进行一个游戏。这个游戏有 n 个槽位和 n − 1 个石块，初始时第 n
个槽位是空的，其余每个槽位都有一个石块，对于两个相连的槽位 u, v ，若 u
是空的，那么小蓝可以将 v 里的石块移到 u 中。开始时，对于任意的 1 ≤ i < n，
第 i 个槽位和第 i + 1 个槽位是相连的。游戏的最终目的是将每一个编号为 i 的
石块移动到编号为 i 的槽位中。
小蓝在经过几次简单的尝试后发现，这个游戏并不一定有解，但好在他可
以花费 1 的代价，任选两个槽位使它们相连。小蓝希望你帮他求出，至少要花
费多少的代价，能够让这个游戏有解。
【输入格式】
输入的第一行包含一个正整数 n 。
第二行包含 n − 1 个正整数 a1, a2, · · · , an−1 ，相邻整数之间使用一个空格分
隔，分别表示初始第 i 个槽位内石块的编号，保证 ai 各不相同。
【输出格式】
输出一行包含一个整数表示答案。
【样例输入】
5
4 1 2 3
【样例输出】
1
试题 I: 游戏
16第十六届蓝桥杯大赛软件赛决赛 C/C++ 大学 A 组
【样例说明】
小蓝可以令槽位 1 和槽位 5 相连，然后将石块 4 移动到槽位 5 ，将石块 1
移动到槽位 1 ，将石块 2 移动到槽位 2 ，将石块 3 移动到槽位 3 ，将石块 4 移
动到槽位 4 ，即可完成游戏的目标。
【评测用例规模与约定】
对于 30% 的评测用例，n ≤ 5 ；
对于 50% 的评测用例，最小代价不超过 1 ；
对于所有评测用例，1 ≤ n ≤ 3 × 105 ，1 ≤ ai < n 。
试题 I: 游戏
17第十六届蓝桥杯大赛软件赛决赛C/C++大学A组
试题 J: 公路
时间限制: 1.0s
内存限制: 256.0MB
本题总分：25 分
【问题描述】
小蓝居住的国家有 n 座城市，城市与城市之间由 n − 1 条公路连接，而且任
意两个城市都可以通过公路互相到达。
这个国家的公路由几个公司共同修建，如果小蓝希望通过某条公路，就必
须持有修建这条公路的公司的通行证，但只要申请一次通行证，就可以在每一
条这个公司修建的公路上通行。
小蓝经常要在不同城市之间旅行，每次他要从一个城市到另一个不同的城
市，都需要根据需要通过的公路申请相应的通行证。具体来说，如果小蓝的路
线经过了一条或者更多条 A 公司修建的公路，小蓝就需要申请一次 A 公司的通
行证。
现在小蓝希望知道，对于这 n × (n − 1) 种不同的情况，他需要申请通行证
的次数总共是多少。
【输入格式】
输入的第一行包含一个正整数 n 。
接下来 n − 1 行，每行包含三个正整数 ui , vi ,wi ，相邻整数之间使用一个空
格分隔，表示城市 ui 和城市 vi 之间有一条由公司 wi 修建的公路。
【输出格式】
输出一行包含一个整数表示答案。
【样例输入】
4
1 2 1
1 3 1
1 4 2
试题J: 公路
18第十六届蓝桥杯大赛软件赛决赛 C/C++ 大学 A 组
【样例输出】
16
【样例说明】
下表给出了每种情况需要申请的通行证数量，总和为 16 。
1
2
3
4
1
/ 1 1 1
2
1 / 1 2
3
1
1 / 2
4
1
2
2 /
【评测用例规模与约定】
对于 30% 的评测用例，1 ≤ n ≤ 300 ；
对于另外 20% 的评测用例，ui = i ，vi = i + 1 ；
对于另外 20% 的评测用例，ui = 1 ，vi = i + 1 ；
对于 80% 的评测用例，1 ≤ n ≤ 50000 ；
对于所有评测用例，1 ≤ wi , ui , vi ≤ n ≤ 500000 。
试题 J: 公路
19
更多推荐
5
0- 0
已为社区贡献2条内容
所有评论(0)