C语言蓝桥杯2023年省赛真题

持续更新中…

第一题

题目描述

小蓝正在玩一款游戏。游戏中魏蜀吴三个国家各自拥有一定数量的士兵X, Y, Z (一开始可以认为都为 0 )。游戏有 n 个可能会发生的事件，每个事件之间相互独立且最多只会发生一次，当第 i 个事件发生时会分别让 X, Y, Z 增加Ai , Bi ,Ci 。
当游戏结束时 (所有事件的发生与否已经确定)，如果 X, Y, Z 的其中一个大于另外两个之和，我们认为其获胜。例如，当 X > Y + Z 时，我们认为魏国获胜。小蓝想知道游戏结束时如果有其中一个国家获胜，最多发生了多少个事件?
如果不存在任何能让某国获胜的情况，请输出 −1 。

输入格式

输入的第一行包含一个整数 n 。
第二行包含 n 个整数表示 Ai，相邻整数之间使用一个空格分隔。
第三行包含 n 个整数表示 Bi，相邻整数之间使用一个空格分隔。
第四行包含 n 个整数表示 Ci，相邻整数之间使用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。
样例输入
3
1 2 2
2 3 2
1 0 7

样例输出

2

提示

发生两个事件时，有两种不同的情况会出现获胜方。
发生 1, 2 事件时蜀国获胜。
发生 1, 3 事件时吴国获胜。

对于 40% 的评测用例，n ≤ 500 ；
对于 70% 的评测用例，n ≤ 5000 ；
对于所有评测用例，1 ≤ n ≤ 105，1 ≤ Ai , Bi ,Ci ≤ 109 。

2 第二题

题目描述

有一个长度为 n 的 01 串，其中有一些位置标记为 ?，这些位置上可以任意填充 0 或者 1，请问如何填充这些位置使得这个 01 串中出现互不重叠的 00 和 11 子串最多，输出子串个数。
输入格式
输入一行包含一个字符串。
输出格式
输出一行包含一个整数表示答案。
样例输入
1110?0
样例输出
2
提示
如果在问号处填 0 ，则最多出现一个 00 和一个 11：111000 。

对于所有评测用例，1 ≤ n ≤ 1000000 。

第三题

题目描述

小蓝用黑白棋的 n 个棋子排成了一行，他在脑海里想象出了一个长度为 n 的 01 串 T，他发现如果把黑棋当做 1，白棋当做 0，这一行棋子也是一个长度为 n 的 01 串 S。
小蓝决定，如果在 S 中发现一个棋子和它两边的棋子都不一样，就可以将其翻转变成另一个颜色。也就是说，如果 S 中存在子串 101 或者 010，就可以选择将其分别变为 111 和 000，这样的操作可以无限重复。
小蓝想知道最少翻转多少次可以把 S 变成和 T 一模一样。

输入格式

输入包含多组数据。
输入的第一行包含一个正整数 D 表示数据组数。
后面 2D 行每行包含一个 01 串，每两行为一组数据，第 2i − 1 行为第 i 组
数据的 Ti，第 2i 行为第 i 组数据的 Si，Si 和 Ti 长度均为 ni。

输出格式

对于每组数据，输出一行包含一个整数，表示答案，如果答案不存在请输出 −1。

样例输入

2
1000111
1010101
01000
11000

样例输出

2
-1
提示
对于 20% 的评测用例，1 ≤∑D1 ni ≤ 10 ；
对于所有评测用例，保证 1 ≤∑D1 ni ≤ 106 ，ni > 0 。

第四题

题目描述

给定一个 n × m （n 行 m 列）的矩阵。
设一个矩阵的价值为其所有数中的最大值和最小值的乘积。求给定矩阵的所有大小为 a × b （a 行 b 列）的子矩阵的价值的和。
答案可能很大，你只需要输出答案对 998244353 取模后的结果。

输入格式

输入的第一行包含四个整数分别表示 n, m, a, b ，相邻整数之间使用一个空格分隔。
接下来 n 行每行包含 m 个整数，相邻整数之间使用一个空格分隔，表示矩阵中的每个数 Ai, j 。

输出格式

输出一行包含一个整数表示答案。

样例输入

2 3 1 2
1 2 3
4 5 6

样例输出

58

提示

1×2+2×3+4×5+5×6 = 58 。

对于 40% 的评测用例，1 ≤ n, m ≤ 100 ；
对于 70% 的评测用例，1 ≤ n, m ≤ 500 ；
对于所有评测用例，1 ≤ a ≤ n ≤ 1000 1 ≤ b ≤ m ≤ 1000 1 ≤ Ai, j ≤ 109 。

第四题

题目描述

给定 a, b，求 1 ≤ x < ab 中有多少个 x 与 ab 互质。由于答案可能很大，你只需要输出答案对 998244353 取模的结果。

输入格式

输入一行包含两个整数分别表示 a, b，用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。

样例输入

2 5

样例输出

16

提示

对于 30% 的评测用例，ab ≤ 106 ；
对于 70% 的评测用例，a ≤ 106，b ≤ 109 ；
对于所有评测用例，1 ≤ a ≤ 109，1 ≤ b ≤ 1018 。

第五题

题目描述

给定一个含有 n 个元素的数组 Ai，你可以选择两个不相交的子段。求出这两个子段内的数的异或和的差值的最大值。

输入格式

输入的第一行包含一个整数 n 。
第二行包含 n 个整数 Ai ，相邻整数之间使用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。

样例输入

6
1 2 4 9 2 7

样例输出

14

提示

两个子段可以分别选 1 和 4，9，2，差值为 15 − 1 = 14 。

对于 40% 的评测用例，n ≤ 5000 ；
对于所有评测用例，2 ≤ n ≤ 2 × 105，0 ≤ Ai ≤ 220 。

第6题

题目描述

给定 n 个正整数 Ai，请找出两个数 i, j 使得 i < j 且 Ai 和 Aj 存在大于 1 的公因数。
如果存在多组 i, j，请输出 i 最小的那组。如果仍然存在多组 i, j，请输出 i 最小的所有方案中 j 最小的那组。

输入格式

输入的第一行包含一个整数 n。
第二行包含 n 个整数分别表示 A1 A2 · · · An，相邻整数之间使用一个空格分隔。

输出格式

输出一行包含两个整数分别表示题目要求的 i, j，用一个空格分隔。
样例输入
5
5 3 2 6 9

样例输出

2 4

提示

对于 40% 的评测用例，n ≤ 5000 ；
对于所有评测用例，1 ≤ n ≤ 105，1 ≤ Ai ≤ 106 。

第七题

题目描述

给定一棵包含 n 个结点的完全 m 叉树，结点按从根到叶、从左到右的顺序依次编号。
例如下图是一个拥有 11 个结点的完全 3 叉树。
蓝桥杯2023年第十四届省赛真题-子树的大小
你需要求出第 k 个结点对应的子树拥有的结点数量。

输入格式

输入包含多组询问。
输入的第一行包含一个整数 T ，表示询问次数。
接下来 T 行，每行包含三个整数 n, m, k 表示一组询问。

输出格式

输出 T 行，每行包含一个整数表示对应询问的答案。

样例输入

3
1 2 1
11 3 4
74 5 3

样例输出

1
2
24

提示

对于 40% 的评测用例，T ≤ 50，n ≤ 106，m ≤ 16 ；
对于所有评测用例，1 ≤ T ≤ 105，1 ≤ k ≤ n ≤ 109，2 ≤ m ≤ 109 。

第八题

题目描述

给定 n 个数 Ai，问能满足 m! 为∑ni=1(Ai!) 的因数的最大的 m 是多少。其中 m! 表示 m 的阶乘，即 1 × 2 × 3 × · · · × m。

输入格式

输入的第一行包含一个整数 n 。
第二行包含 n 个整数，分别表示 Ai，相邻整数之间使用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。

样例输入

3
2 2 2

样例输出

3
提示
对于 40% 的评测用例，n ≤ 5000 ；
对于所有评测用例，1 ≤ n ≤ 105 1 ≤ Ai ≤ 109 。

第九题

题目描述

小蓝最近在找一些奇怪的数，其奇数数位上是奇数，而偶数数位上是偶数。同时，这些数的任意 5 个连续数位的和都不大于 m 。
例如当 m = 9 时，10101 和 12303 就是奇怪的数，而 12345 和 11111 则不是。
小蓝想知道一共有多少个长度为 n 的上述的奇怪的数。你只需要输出答案对 998244353 取模的结果。

输入格式

输入一行包含两个整数 n, m ，用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。

样例输入

5 5

样例输出

6

提示

对于 30% 的评测用例，n ≤ 12 ；
对于 60% 的评测用例，n ≤ 5000 ；
对于所有评测用例，5 ≤ n ≤ 2 × 105，0 ≤ m ≤ 50 。

第十题

题目描述

这天，小蓝在二维坐标系的点 (X, Y) 上放了一个太阳，看做点光源。
他拿来了 n 条线段，将它们平行于 x 轴放置在了坐标系中，第 i 条线段的左端点在 xi , yi，长度为 li。线段之间不会有重合或部分重合的情况（但可能出现端点相交）。小蓝想知道有多少条线段能被太阳照亮（一条线段有长度大于 0的部分被照亮就算）

输入格式

输入的第一行包含三个正整数 n, X, Y，相邻整数之间使用一个空格分隔。
接下来 n 行，第 i 行包含三个整数 xi , yi , li，相邻整数之间使用一个空格分隔。

输出格式

输出一行包含一个正整数表示答案。

样例输入

3 10 2000000
5 3 5
6 2 4
0 1 10

样例输出

2

提示

第一条线段在最上面被照亮，第二条线段被第一条完全挡住，第三条线段左边的一段能被照亮。

对于 30% 的评测用例，n ≤ 1000 ；

对于所有评测用例，1 ≤ n ≤ 100000, 0 ≤ xi , X ≤ 107 , 0 < yi ≤ 105 , 0 < li ≤ 100, 106 < Y ≤ 107 。

跟点时间,后续统一出答案，最近太忙罗.