第十六届蓝桥杯大赛软件赛决赛 C/C++ 大学 B 组
·
第十六届蓝桥杯大赛软件赛决赛 C/C++ 大学 B 组
第十六届蓝桥杯大赛软件赛决赛
C/C++ 大学 B 组
【选手须知】
考试开始后，选手首先下载题目，并使用考场现场公布的解压密码解压试
题。
考试时间为 4 小时。考试期间选手可浏览自己已经提交的答案，被浏览的
答案允许拷贝。时间截止后，将无法继续提交或浏览答案。
对同一题目，选手可多次提交答案，以最后一次提交的答案为准。
选手必须通过浏览器方式提交自己的答案。选手在其它位置的作答或其它
方式提交的答案无效。
试题包含“结果填空”和“程序设计”两种题型。
结果填空题：要求选手根据题目描述直接填写结果。求解方式不限。不要
求源代码。把结果填空的答案直接通过网页提交即可，不要书写多余的内容。
程序设计题：要求选手设计的程序对于给定的输入能给出正确的输出结果。
考生的程序只有能运行出正确结果才有机会得分。
注意：在评卷时使用的输入数据与试卷中给出的示例数据可能是不同的。
选手的程序必须是通用的，不能只对试卷中给定的数据有效。
对于编程题目，要求选手给出的解答完全符合 GNU C/C++ 标准，不能使
用诸如绘图、Win32API、中断调用、硬件操作或与操作系统相关的 API。
代码中允许使用 STL 类库。
注意: main 函数结束必须返回 0。
注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>，不能通
过工程设置而省略常用头文件。
所有源码必须在同一文件中。调试通过后，拷贝提交。
提交时，注意选择所期望的编译器类型。
第十六届蓝桥杯大赛软件赛决赛
1第十六届蓝桥杯大赛软件赛决赛 C/C++ 大学 B 组
试题 A: 新型锁
本题总分：5 分
【问题描述】
密码学家小蓝受邀参加国际密码学研讨会，为此他设计了一种新型锁，
巧妙地融合了数学的严谨性与密码学的安全性。这把锁包含 2025 个连续
的数字格，每个格子需填入一个正整数，从而形成一个长度为 2025 的序列
{a1, a2, . . . , a2025}，其中 ai 表示第 i 个格子上的数字。
要想解锁，该序列需满足以下条件：任意两个相邻格子中的数字，其最小
公倍数（LCM）均为 2025。即对于所有的 i（1 ≤ i ≤ 2024），需满足：
LCM(ai , ai+1) = 2025
现在，请你计算有多少个不同的序列能够解开这把锁。由于答案可能很大，
你只需输出其对 109 + 7 取余后的结果即可。
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一
个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
试题 A: 新型锁
2第十六届蓝桥杯大赛软件赛决赛 C/C++ 大学 B 组
试题 B: 互质藏卡
本题总分：5 分
【问题描述】
小蓝整理着阁楼上的旧物，偶然发现了一个落满灰尘的卡片箱。打开箱子，
里面整齐地摆放着 17600 张卡片，每张卡片上都写有一个数字，恰好包含了从
1 到 17600 的所有正整数。
儿时的他热衷于收集各种卡牌，数量之多令人咋舌。如今，再次翻阅这些
尘封的记忆，小蓝不禁感慨万千。他想起收藏家前辈的箴言：“收藏的魅力在于
精粹，而非数量”。于是，他决定从这些卡牌中选取 2025 张，组成一套 “互质
藏卡”。
“互质藏卡” 的特点在于：任意两张卡片上的数字之间互质，即它们的最大
公约数恒为 1。现在，请你帮小蓝计算，共有多少种不同的选取方案，使得选
出的 2025 张卡片满足 “互质藏卡” 的条件。由于答案可能很大，你只需给出其
对 109 + 7 取余后的结果即可。
注意：两个选取方案被认为是不同的，当且仅当它们所包含的数字集合不
完全相同。即，若存在至少一个数字出现在其中一个集合但不出现在另一个集
合中，则这两个方案被视为不同。
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一
个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
试题 B: 互质藏卡
3第十六届蓝桥杯大赛软件赛决赛 C/C++ 大学 B 组
试题 C: 数字轮盘
时间限制: 1.0s
内存限制: 256.0MB
本题总分：10 分
【问题描述】
“数字轮盘” 是一款益智游戏，基于一个带有指针的圆形轮盘展开。轮盘边
缘按顺时针刻有数字 1 至 N，初始时指针指向 1。
游戏分为两阶段：旋转轮盘和恢复轮盘。
第一阶段，将轮盘顺时针旋转 K 次。每次旋转，数字依次后移一位，指针
指向的数字随之改变。例如，对于 N = 4 的轮盘，初始状态为 1, 2, 3, 4（指针指
向 1），旋转一次变为 4, 1, 2, 3（指针指向 4），再旋转一次变为 3, 4, 1, 2（指针
指向 3），依此类推。
第二阶段，小蓝需通过操作恢复初始状态，每次操作包含以下两步：
• 第一步：翻转以指针为起点、顺时针方向的前 N − 1 个数字的顺序。
• 第二步：翻转除指针外的 N − 1 个数字的顺序。
例如，对 N = 4，状态为 4, 1, 2, 3（指针指向 4）进行一次操作：
• 第一步：翻转 4, 1, 2，变为 2, 1, 4, 3（指针指向 2）。
• 第二步：翻转 1, 4, 3，变为 2, 3, 4, 1（指针指向 2）。
现在，给定轮盘的数字个数 N 和旋转次数 K，请计算小蓝最少需要几次操
作才能恢复初始状态。如果无法恢复初始状态，则输出 −1。
【输入格式】
输入的第一行包含一个整数 T，表示测试用例的数量。
接下来 T 行，每行包含两个整数 N 和 K，分别表示轮盘上的数字个数和
旋转次数。
试题 C: 数字轮盘
4第十六届蓝桥杯大赛软件赛决赛 C/C++ 大学 B 组
【输出格式】
输出共 T 行，每行包含一个整数，表示最少需要的操作次数。如果无法恢
复初始状态，则输出 −1。
【样例输入】
2
3 2
4 1
【样例输出】
2
-1
【评测用例规模与约定】
对于 30% 的评测用例，1 ≤ T ≤ 102，2 ≤ N ≤ 500，0 ≤ K ≤ 500。
对于 100% 的评测用例，1 ≤ T ≤ 105，2 ≤ N ≤ 109，0 ≤ K ≤ 109。
试题 C: 数字轮盘
5第十六届蓝桥杯大赛软件赛决赛C/C++大学B组
试题 D: 斐波那契字符串
时间限制: 1.0s
内存限制: 256.0MB
本题总分：10 分
【问题描述】
斐波那契字符串 S 是由 “0” 和 “1” 所组成的字符串，其生成规则如下：
• S 1 = 0。
• S 2 = 1。
• 对于任意正整数 n（n ≥ 3），S n = S n−2 + S n−1（“+” 表示字符串拼接）。
例如：S 3 = 01、S 4 = 101、S 5 = 01101。
在斐波那契字符串 S 中，定义逆序对为满足以下条件的整数对 (i, j)：
• 1 ≤ i < j ≤ |S |（其中 |S | 表示 S 的长度）。
• S [i] = 1（第 i 个字符为 “1”）并且 S [ j] = 0（第 j 个字符为 “0”）。
现在，给定一个正整数 N，请你计算出 S N 中所有逆序对 (i, j) 的总数。由
于结果可能很大，请输出其对 109 + 7 取余后的值。
【输入格式】
输入的第一行包含一个整数 T ，表示测试用例的数量。
接下来的 T 行，每行包含一个整数 N，表示要计算的斐波那契字符串的序
号。
【输出格式】
对于每个测试用例，输出一行，包含一个整数，表示 S N 中所有逆序对的
总数对 109 + 7 取余后的结果。
试题D: 斐波那契字符串
6第十六届蓝桥杯大赛软件赛决赛 C/C++ 大学 B 组
【样例输入】
2
3
5
【样例输出】
0
2
【样例说明】
对于 N = 3，S 3 = 01，逆序对总数为 0。
对于 N = 5，S 5 = 01101，逆序对为 (2, 4)、(3, 4)，总数为 2。
【评测用例规模与约定】
对于 20% 的评测用例，1 ≤ T ≤ 20，3 ≤ N ≤ 35。
对于 100% 的评测用例，1 ≤ T ≤ 105，3 ≤ N ≤ 105。
试题 D: 斐波那契字符串
7第十六届蓝桥杯大赛软件赛决赛 C/C++ 大学 B 组
试题 E: 项链排列
时间限制: 1.0s
内存限制: 256.0MB
本题总分：15 分
【问题描述】
小蓝有 A 颗蓝珠（用字符 ‘L’ 表示）和 B 颗桥珠（用字符 ‘Q’ 表示），他打
算用这些珠子串成一条项链。他认为项链的美感主要体现在其视觉 “变化” 上：
当项链中任意两个相邻的珠子种类不同时，就记为产生了一次 “变化”。
为了系统地研究不同排列的美感，小蓝将每一种项链的排列方式表示为一
个长度为 A + B 的字符串。这个字符串由 A 个字符 ‘L’ 和 B 个字符 ‘Q’ 组成。
相应地，一条项链的 “变化次数” 即为这个字符串中，所有相邻且不相同的字符
对的数目。
例如，如果项链的排列是 “LLQLQ”，那么：
• 第 1 个 ‘L’ 和第 2 个 ‘L’ 相同，无变化。
• 第 2 个 ‘L’ 和第 3 个 ‘Q’ 不同，产生了 1 次变化。
• 第 3 个 ‘Q’ 和第 4 个 ‘L’ 不同，产生了 1 次变化。
• 第 4 个 ‘L’ 和第 5 个 ‘Q’ 不同，产生了 1 次变化。
排列 “LLQLQ” 的总 “变化次数” 为 3。
现在，小蓝希望找到一种项链排列，使其总 “变化次数” 恰好为 C。对此，
请你帮他在所有满足这一条件的排列中，找出字典序最小的那一个。如果不存
在任何满足条件的排列方式，则输出 −1。
【输入格式】
输入仅一行，包含三个整数 A，B 和 C，分别表示蓝珠数量、桥珠数量和
目标变化次数。
试题 E: 项链排列
8第十六届蓝桥杯大赛软件赛决赛 C/C++ 大学 B 组
【输出格式】
输出一个长度为 A + B 的字符串，表示字典序最小的满足条件的排列。如
果不存在这样的排列，则输出 −1。
【样例输入 1】
2 2 2
【样例输出 1】
LQQL
【样例输入 2】
2 2 3
【样例输出 2】
LQLQ
【样例输入 3】
2 2 4
【样例输出 3】
-1
【评测用例规模与约定】
对于 20% 的评测用例，0 ≤ A, B,C ≤ 100，1 ≤ A + B ≤ 200。
对于 100% 的评测用例，0 ≤ A, B,C ≤ 106，1 ≤ A + B ≤ 2 × 106。
试题 E: 项链排列
9第十六届蓝桥杯大赛软件赛决赛C/C++大学B组
试题 F: 蓝桥星数字
时间限制: 1.0s
内存限制: 256.0MB
本题总分：15 分
【问题描述】
地球上，我们习惯用十进制数字来记录万物，从个位、十位，逐级向上构
成了我们熟悉的自然数体系。
然而，在遥远的蓝桥星，数字的排列和解读方式却与我们截然不同。蓝桥
星人并不单纯地以数值大小来衡量一个数字，他们更注重数字内部蕴含的 “节
奏感”。因此，对他们而言，任何一个有效的数字，其从左到右每一位上的数字
奇偶性都必须是交替出现的。
例如，对于 10 这个数字，其十位是奇数 1，个位是偶数 0，呈现奇偶交替，
因此 10 是个有效的数字。而对于 13 这个数字，其十位是奇数 1，个位也是奇
数 3，不符合奇偶交替的条件，因此 13 不是个有效的数字。
根据这个规则，蓝桥星的数字序列从 10 开始，依次为 10, 12, 14, 16, 18,
21, 23, 25, 27, 29, 30, . . .。
只不过，随着文明的发展，蓝桥星人需要一种方法，来快速找到第 N 个符
合这种奇偶交替规则的数字，以满足其日益增长的数字处理需求。现在，请你
帮助蓝桥星人，编写程序找出并输出第 N 个符合奇偶交替规则的数字。
【输入格式】
输入包含一个正整数 N，表示需要查找第 N 个符合规则的数字。
【输出格式】
输出一个整数，表示第 N 个符合奇偶交替规则的数字。
【样例输入 1】
1
试题F: 蓝桥星数字
10第十六届蓝桥杯大赛软件赛决赛 C/C++ 大学 B 组
【样例输出 1】
10
【样例输入 2】
11
【样例输出 2】
30
【评测用例规模与约定】
对于 20% 的评测用例，1 ≤ N ≤ 105。
对于 100% 的评测用例，1 ≤ N ≤ 1012。
试题 F: 蓝桥星数字
11第十六届蓝桥杯大赛软件赛决赛 C/C++ 大学 B 组
试题 G: 翻倍
时间限制: 1.0s
内存限制: 256.0MB
本题总分：20 分
【问题描述】
给定 n 个正整数 A1, A2, . . . , An，每次操作可以选择任意一个数翻倍。
请输出让序列单调不下降，也就是每个数都不小于上一个数，最少需要操
作多少次？
【输入格式】
输入的第一行包含一个正整数 n。
第二行包含 n 个正整数 A1, A2, . . . , An。
【输出格式】
输出一个整数表示需要的最小操作次数。
【样例输入】
6
4 3 2 1 7 9
【样例输出】
8
【样例说明】
可以将序列变为: 4,6,8,8,14,18，总计需要 0 + 1 + 2 + 3 + 1 + 1 = 8 次操作。
【评测用例规模与约定】
对于 20% 的评测用例，n ≤ 10, Ai ≤ 100。
试题 G: 翻倍
12第十六届蓝桥杯大赛软件赛决赛 C/C++ 大学 B 组
对于 50% 的评测用例，n ≤ 5000, Ai < 2 32，保证存在操作可以在所有 Ai 小
于 2 32 的情况下满足题目要求。
对于 100% 的评测用例, 1 ≤ n ≤ 2 × 105 , 1 ≤ Ai < 2 32。
试题 G: 翻倍
13第十六届蓝桥杯大赛软件赛决赛C/C++大学B组
试题 H: 近似回文字符串
时间限制: 1.0s
内存限制: 256.0MB
本题总分：20 分
【问题描述】
小蓝，一位昔日的编程大神，如今却因找不到工作，转行成了飞天大盗。
近日，他正筹划着盗取蓝桥王国的至宝——水晶项链。
水晶项链被珍藏在一个固若金汤的保险库中，要想开启保险库，就必须破
解保险库的密码。利用编程技能，小蓝截获情报，得知这个密码是一个长度为
N，且仅由小写英文字母构成的 “近似回文字符串”。
一个字符串 S 被称为 “近似回文字符串” 需满足以下条件：
1. S 本身不是回文串。
2. 从 S 中删除一个字符后，剩下的字符串是回文串。
例如，当 S = abbac 时，S 不是回文，但删除最后一个字符 c 后得到的
abba 是回文，所以 S 是 “近似回文字符串”。
现在，请你帮助小蓝计算长度为 N 的 “近似回文字符串” 的数量，为转行
做飞天大盗的小蓝提供助力。由于答案可能很大，你只需给出其对 109 + 7 取余
后的结果即可。
【输入格式】
输入一行，包含一个整数 N，表示密码字符串的长度。
【输出格式】
输出一个整数，表示长度为 N 的 “近似回文字符串” 的数量对 109 + 7 取余
后的结果。
【样例输入】
2
试题H: 近似回文字符串
14第十六届蓝桥杯大赛软件赛决赛 C/C++ 大学 B 组
【样例输出】
650
【评测用例规模与约定】
对于 10% 的评测用例，2 ≤ N ≤ 6。
对于 100% 的评测用例，2 ≤ N ≤ 105。
试题 H: 近似回文字符串
15第十六届蓝桥杯大赛软件赛决赛C/C++大学B组
试题 I: 子串去重
时间限制: 1.0s
内存限制: 256.0MB
本题总分：25 分
【问题描述】
给定一个字符串 S 以及若干组询问，每个询问包含两个区间 (La, Ra),
(Lb, Rb)，你需要判定 S La , S La+1, ..., S Ra 与 S Lb , S Lb+1, . . . , S Rb 去重后有多少个位
置上的字符是不同的。
这里的去重指的是每个子串对于每种字符，只保留第一个出现的那个，后
续出现的直接丢弃。
例如 aabcbac 在选中区间 (1, 5) 时，得到子串 aabcb，去重后为 abc，选中
区间 (3, 6) 时得到 bcba，去重后为 bca。
特别地，两个长度不同的子串中，较长串的多出的部分每个位置都视为不
同。
【输入格式】
输入第一行包含一个字符串 S。
第二行包含一个整数 m，表示询问次数。
接下来 m 行，每行包含四个整数，表示一次询问。
【输出格式】
输出共 m 行, 每行一个整数对应每次询问的答案。
【样例输入】
aabcbabacdab
3
1 1 2 2
1 10 6 9
4 7 9 12
试题I: 子串去重
16第十六届蓝桥杯大赛软件赛决赛 C/C++ 大学 B 组
【样例输出】
0
1
2
【评测用例规模与约定】
对于 40% 的评测用例，|S | ≤ 10，m = 1。
对于 60% 的评测用例，|S |, m ≤ 5000。
对于 100% 的评测用例，1 ≤ |S |, m ≤ 105 , 1 ≤ La ≤ Ra ≤ |S |, 1 ≤ Lb ≤ Rb ≤ |S |。
试题 I: 子串去重
17第十六届蓝桥杯大赛软件赛决赛 C/C++ 大学 B 组
试题 J: 涂格子
时间限制: 1.0s
内存限制: 256.0MB
本题总分：25 分
【问题描述】
小蓝正在玩一个涂格子的游戏。他有一个大小为 n × m 的矩阵，他要给这
个矩阵中的每个格子都涂上黑色或白色。小蓝希望最终涂完的格子像国际象棋
棋盘一样整齐。具体来说，他希望每一个同色连通块都是矩形，且与上下左右
四个异色的矩形相邻（如果存在的话）。下图中第一行的两个涂色方案是合法
的，第二行的两个涂色方案是不合法的。
同时小蓝希望 k 个格子具有特定的颜色。其中第 i 个格子位置是 (xi , yi)，
具有特定的颜色 ci。你需要帮助他求出符合要求的合法涂色方案有多少种。因
为方案数可能很大，请对 998244353 取模后输出。
【输入格式】
输入第一行包含三个正整数 n, m, k，含义如问题描述所述。
试题 J: 涂格子
18第十六届蓝桥杯大赛软件赛决赛 C/C++ 大学 B 组
接下来 k 行，每行三个正整数 xi , yi , ci，表示格子 (xi , yi) 必须被涂成颜色
ci。注意 xi , yi 可能重复出现。
【输出格式】
输出共一个整数，表示答案。
【样例输入 1】
2 2 4
1 1 0
1 2 0
2 1 0
2 2 1
【样例输出 1】
0
【样例输入 2】
3 3 2
1 1 0
2 2 1
【样例输出 2】
8
【评测用例规模与约定】
对于 20% 的评测用例，n × m ≤ 20。
对于 50% 的评测用例，n, m, k ≤ 5000。
另存在 30% 的评测用例，ci = 0。
另存在 10% 的评测用例，k = 0。
对于 100% 的评测用例，1 ≤ n, m ≤ 109，1 ≤ k ≤ 3 × 105，1 ≤ xi ≤ n，
1 ≤ yi ≤ m，ci ∈ {0, 1}。
试题 J: 涂格子
19
更多推荐
4
0- 0
已为社区贡献2条内容
所有评论(0)