0419 第 28 场 蓝桥月赛

• 比赛链接：https://www.lanqiao.cn/oj-contest/senior-28/
• 题解回放：https://www.bilibili.com/video/BV12LLTzJEAQ/

T1. 发射火箭【算法赛】

问题描述

在“银河系最奇葩航天局”，实习生小明被派去发射一枚超级火箭。控制室里有个花里胡哨的仪表盘，上面有红、黄、蓝、绿四个按钮。局长叉着腰，得意洋洋地说：“小蓝，发射火箭超级简单！按红按钮 $123$ 次，黄按钮 $456$ 次，蓝按钮 $789$ 次，顺序随便，火箭就能嗖嗖飞上天！”

小明一听，摩拳擦掌，心想：“这不就是体力活嘛？我小时候玩跳舞机都没这么带劲！”可就在他准备大干一场时，同事小刚一脸坏笑地凑过来：“小明，别急！局长忘了告诉你，黄按钮昨天被他按坏了哈哈。不过别慌，咱们还有个绿按钮，它可厉害了！按一次绿按钮，等于同时按了一次黄按钮和一次蓝按钮！”

现在，请你帮小明分析，要想成功发射火箭，他最少需要按多少次按钮？

输入格式

无。

输出格式

输出一个整数，表示绿按钮需要按的次数。

T2. 燃油交换【算法赛】

问题描述

小蓝是一名宇宙飞船的航行舰长，正执行从星球 $X$ 飞往星球 $Y$ 的任务。根据预计的行程时间，他需要在 $N$ 天内完成这次航行。飞船的动力来源于两种燃油：$A$ 和 $B$。然而，每一天的路况不同，导致燃油的消耗量也有所变化。

对于每一天 $i$，使用燃油 $A$ 的消耗量为 $A_i$，而使用燃油 $B$ 的消耗量则为 $B_i$。小蓝可以在旅程开始前随意选择一种燃油，并且在航行的某一天进行一次燃油替换。

现在，小蓝希望计算出在这趟旅程中，飞船最少需要消耗多少燃油。

注意：替换操作最多只能进行一次。

输入说明

第一行包含一个整数 $N(1\leq N \leq 10^5)$，表示航行的天数。

第二行包含 $N$ 个整数 $A_1, A_2, \ldots, A_N( 1\leq A_i \leq 10^9)$，表示使用燃油 $A$ 的每日消耗量。

第三行包含 $N$ 个整数 $B_1, B_2, \ldots, B_N(1\leq B_i \leq 10^9)$，表示使用燃油 $B$ 的每日消耗量。

输出格式

输出一个整数，表示飞船在这趟旅程中最少需要消耗的燃油量。

输入样例 1

5
1 2 3 4 5
5 4 3 2 1

输出样例 1

9

说明

在这个样例中，小蓝可以选择在第 $1,2,3$ 天使用燃油 $A$，第 $4,5$ 天使用燃油 $B$。这样，燃油消耗量为 $1 + 2 + 3 + 2 + 1 = 9$，这是最少的消耗量。

T3. 训练反应力【算法赛】

问题描述

小蓝正在努力成为一名航空员，这需要他锻炼出足够的反应力。

他来到一台用来训练反应力的机器前，训练的规则如下：小蓝可以选择在 $N$ 个时间节点进行攻击。在某个时间节点 $X$ 攻击机器后，机器将在 $X+D$ 节点反击小蓝。此时，小蓝需要躲避，如果被机器击中，任务将失败。

小蓝无法在同一时间节点同时进行攻击和躲避。他想知道，在确保任务成功的前提下，自己最多能攻击机器多少次。

输入格式

第一行包含两个整数 $N,D(1, \leq N \leq 10^5,1 \leq D \leq 10^9)$，分别表示时间节点的数量和机器反击的延迟。

第二行包含 $N$ 个整数 $A_i(1 \leq A_1<A_2<A_3<\cdots<A_N \le 10^9)$，表示时间节点的具体值。

输出格式

输出一个整数，表示小蓝在确保任务成功的前提下，最多能攻击机器的次数。

样例输入

5 2
1 3 4 6 8

样例输出

3

说明

在样例中，小蓝可以在时间节点 $1、4$ 和 $8$ 进行攻击。具体步骤如下：

1. 在时间节点 $1$ 攻击，机器将在时间节点 $3$ 反击，小蓝可以躲避。
2. 在时间节点 $4$ 攻击，机器将在时间节点 $6$ 反击，小蓝可以躲避。
3. 在时间节点 $8$ 攻击，机器将在时间节点 $10$ 反击，小蓝可以躲避。

因此，小蓝最多可以攻击机器 $3$ 次。

T4. 最佳航线【算法赛】

问题描述

航天工程师小蓝正在为月球探测器设计最佳航线。地球到月球的航程被分为 $N$ 个阶段，地球位于第 1 阶段，月球位于第 $N$ 阶段。在第 $i$ 个阶段（$1 \le i < N$），探测器可以进行一次“空间跳跃”，跳跃到 $i+1, i+2, \ldots, A_i$ 中的任意一个阶段。

为了节省燃料，小蓝希望用最少的跳跃次数抵达月球。现在，请你帮助小蓝计算出探测器从地球（阶段 $1$）到月球（阶段 $N$）所需的最少跳跃次数。

输入格式

第一行包含一个整数 $N$（$2\leq N \leq 10^5$），表示航程的阶段数。

第二行包含 $N-1$ 个整数 $A_1, A_2, \ldots, A_{N-1}$（$i < A_i \le N$），其中 $A_i$ 表示在第 $i$ 个阶段，探测器最多可以跳跃到的阶段。

输出格式

输出一个整数，表示探测器从地球到月球所需的最少跳跃次数。

样例输入

6
5 6 6 6 6

样例输出

2

T5. 航天梦【算法赛】

问题描述

小蓝从小梦想成为宇航员，但因体质原因未能实现梦想。他转而钻研编程，最终成为航天总局的程序员，负责为火箭设计轨道计算程序。近期，他接到一项关键任务：火箭在飞行过程中记录了 $N$ 个实验数据，反映不同阶段的轨道参数。为了优化火箭控制系统，小蓝需要计算这些数据两两异或（XOR）值的乘积。

具体来说，给定一个长度为 $N$ 的整数数组 $A$，其中 $A_i$ 表示第 $i$ 个实验数据的数值。你需要计算所有可能的两两数据组合的异或值乘积，即：

$$\prod_{1 \leq i < j \leq N} (A_i \oplus A_j)$$

由于答案可能很大，请你将答案对 $10^9+7$ 取模后输出。

输入说明

第一行包含一个整数 $N$（$2 \leq N \leq 10^5$），表示实验数据的数量。

第二行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$（$1 \leq A_i \leq 3\times 10^3$），表示每个实验数据的数值。

输出格式

输出一个整数表示答案，答案需要对 $10^9+7$ 取模后输出。

输入样例 1

3
1 2 3

输出样例 1

6

说明

两两异或值为：$(1 \oplus 2) = 3$，$(1 \oplus 3) = 2$，$(2 \oplus 3) = 1$，乘积为：$3 \times 2 \times 1 = 6$。

T6. 吃零食训练【算法赛】

问题描述

小蓝是一名航天工程师，同时也是一名狂热的算法竞赛爱好者。最近，他正在为即将到来的星际航天竞赛做准备。为了更好地模拟太空中的复杂环境，小蓝设计了一套独特的训练方案。他准备了三种不同类型的太空零食：能量棒、压缩饼干和蛋白质胶囊，分别用 $0$、$1$ 和 $2$ 来表示。其中，能量棒有 $A$ 个，压缩饼干有 $B$ 个，蛋白质胶囊有 $C$ 个。每次训练，小蓝会从剩余的零食中选择两种吃掉，并根据吃掉的零食类型计算训练得分。如果吃掉的两种零食分别是 $x$ 和 $y$，那么本次训练的得分就是 $(x + y) \bmod 3$。小蓝需要不断地进行训练，直到剩余的零食数量小于等于 $1$。

由于太空任务的特殊性，小蓝必须尽可能地提高训练效率，以适应各种突发情况。因此，他希望在训练过程中获得的总得分尽可能高。

现在，请你帮助小蓝计算，在最优的训练策略下，他能够获得的最高总得分是多少？

输入格式

第一行包含一个整数 $T$（$1\leq T \leq 10^5$），表示测试用例的数量。

接下来 $T$ 行，每行包含三个整数 $A$、$B$ 和 $C$（$1\leq A,B,C \leq 10^9$），分别表示能量棒、压缩饼干和蛋白质胶囊的数量。整数之间用空格分隔。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示小蓝在最优训练策略下能够获得的最高总得分。

样例输入

2
1 2 3
4 5 6

样例输出

5
13