本篇更新蓝桥杯省赛真题的后5道。

6.试题 F: 公因数匹配

时间限制: 10.0s 内存限制: 512.0MB 本题总分：15 分

【问题描述】 给定 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 。

7.试题 G: 小蓝的旅行计划 时间限制: 15.0s 内存限制: 512.0MB 本题总分：20 分

【问题描述】 小蓝正计划进行一次漫长的旅行。小蓝计划开车完成这次旅行。显然他在 途中需要加油，否则可能无法完成这次旅行。 小蓝要依次经过 n 个地点，其中从第 i − 1 个地点到达第 i 个地点需要消耗 Disi 升油。小蓝经过的每个地点都有一个加油站，但每个加油站的规定也不同。 在第 i 个加油站加 1 升油需要 Costi 的费用，且在这个加油站最多只能加 Limi 升油。 小蓝的车的油箱也有容量限制，他的车上最多只能装载 m 升油。 一开始小蓝的油箱是满的，请问小蓝需要准备多少钱才能顺利完成他的旅 行计划。如果小蓝按给定条件无论准备多少钱都不能完成他的旅行计划，请输 出 −1 。

【输入格式】 输入的第一行包含两个整数 n m ，用一个空格分隔。 接下来 n 行每行包含 3 个整数 Disi Costi Limi，相邻整数之间使用一个空 格分隔。

【输出格式】 输出一行包含一个整数表示答案。

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

【样例输出】 38

【评测用例规模与约定】 对于 30% 的评测用例，n Disi Costi Limi m ≤ 300 ； 对于 60% 的评测用例，n Disi Costi Limi m ≤ 5000 ； 对于所有评测用例，1 ≤ n ≤ 2 × 105，1 ≤ Disi Limi m ≤ 109，1 ≤ Costi ≤ 40000 。

8.试题 H: 子树的大小 时间限制: 15.0s 内存限制: 512.0MB 本题总分：20 分

【问题描述】 给定一棵包含 n 个结点的完全 m 叉树，结点按从根到叶、从左到右的顺序 依次编号。 例如下图是一个拥有 11 个结点的完全 3 叉树。 你需要求出第 k 个结点对应的子树拥有的结点数量。

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

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

【样例输入】 3 1 2 1 11 3 4 74 5

【样例输出】 1 2 24 【评测用例规模与约定】 对于 40% 的评测用例，T ≤ 50，n ≤ 106，m ≤ 16 ； 对于所有评测用例，1 ≤ T ≤ 105，1 ≤ k ≤ n ≤ 109，2 ≤ m ≤ 109 。

9.试题 I: 高塔 时间限制: 10.0s 内存限制: 512.0MB 本题总分：25 分

【问题描述】 小蓝正在玩一个攀登高塔的游戏。高塔的层数是无限的，但游戏最多只有 n 回合。 小蓝一开始拥有 m 点能量，在每个回合都有一个值 Ai 表示小蓝的角色状 态。小蓝每回合可以选择消费任意点能量 Ci (最低消费 1 点，没有上限)，他在 这回合将最多可以向上攀爬 Ai · Ci 层。实际攀爬的层数取决于小蓝自己在这回 合的表现，不过最差也会向上爬一层。 当某回合小蓝的能量点数耗尽，那么在完成这个回合后，游戏结束。n 回 合结束后，不管能量还有没有剩余，游戏都会直接结束。 给出小蓝每回合的 Ai 和自己一开始的能量点数 m。小蓝想知道有多少种不 同的可能出现的游玩过程。如果小蓝在两种游玩过程中的任一对应回合花费的 能量点数不同或该回合结束时所处层数不同，那么这两种游玩过程就被视为不 同。

【输入格式】 输入的第一行包含两个整数 n, m，用一个空格分隔。 第二行包含 n 个整数 Ai，相邻整数之间使用一个空格分隔，表示小蓝每回 合的状态值。

【输出格式】 输出一行包含一个整数表示给定条件下不同游玩过程的数量。由于答案可 能很大，你只需要输出答案对 998244353 取模的结果

【样例输入】 9 15 3 2 5 7 1 4 6 8

【样例输出】 392149233

【评测用例规模与约定】 对于 40% 的评测用例，n ≤ 300，m ≤ 500 ； 对于所有评测用例，1 ≤ n ≤ 2 × 105，n ≤ m ≤ 1018，1 ≤ Ai ≤ 109 。

10.试题 J: 反异或 01 串 时间限制: 10.0s 内存限制: 512.0MB 本题总分：25 分

【问题描述】 初始有一个空的 01 串，每步操作可以将 0 或 1 添加在左侧或右侧。也可 以对整个串进行反异或操作: 取 s ′ = s ⊕ rev(s)，其中 s 是目前的 01 串，⊕ 表示 逐位异或，rev(s) 代表将 s 翻转，也就是说取中心位置并交换所有对称的两个 位置的字符。例如，rev(0101) = 1010 rev(010) = 010 rev(0011) = 1100。 反异或操作最多使用一次（可以不用，也可以用一次）。 给定一个 01 串 T，问最少需要添加多少个 1 才能从一个空 01 串得到 T。 在本题中 0 可以添加任意个。

【输入格式】 输入一行包含一个 01 串表示给定的 T 。

【输出格式】 输出一行包含一个整数，表示需要最少添加多少个 1 。

【样例输入】 00111011

【样例输出】 3

【评测用例规模与约定】 对于 20% 的评测用例，|T| ≤ 10 ； 对于 40% 的评测用例，|T| ≤ 500 ；

对于 60% 的评测用例，|T| ≤ 5000 ； 对于 80% 的评测用例，|T| ≤ 105 ； 对于所有评测用例，1 ≤ |T| ≤ 106，保证 T 中仅含 0 和 1 。