0629 第 3 场 算法季度赛

• 比赛链接：https://www.lanqiao.cn/oj-contest/season-3/
• 题解回放：https://www.bilibili.com/video/BV1vy411z7yj/

T1. 全国科普行动日【算法赛】

问题描述

六月的微风轻拂心田，知识的光芒照亮前路。6.29 全国科普行动日，是普及科学知识的重要时刻。

探索未知，启迪智慧。正是不断的科学探索，才有了我们日新月异的生活。

让我们积极参与科普活动，开启科学的奇妙之旅，用知识武装头脑，用科学点亮未来。

对此，请你输出 6.29，投身科普行动！

输入格式

本题为填空题，无需输入即可作答。

输出格式

输出一个字符串，投身科普行动。

T2. A%B【算法赛】

问题描述

给定两个整数 $A$、$B$，请你求出 $A$ 除以 $B$ 的余数。

在本题中，“$A$ 除以 $B$ 的余数” 是指存在整数 $q$ 使得 $A = Bq + r$，并且 $r$ 是唯一的非负整数，满足 $0 \leq r < |B|$。

输入格式

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

对于每个测试用例，输入一行包含两个整数 $A$ 和 $B$（$-10^9 \leq A,B \leq 10^9$，$B \ eq 0$），以空格分隔。

输出格式

对于每个测试用例，输出一个整数，表示 $A$ 除以 $B$ 的余数。

样例输入

1
10 3

样例输出

1

样例说明

$10$ 除以 $3$ 的余数为 $1$。

T3. 能量圆盘【算法赛】

问题描述

小蓝偶然获得了一个能量圆盘，圆盘上镶嵌了 $n$ 颗宝石，每颗宝石上都有一个数字，其中第 $i$ 颗宝石上的数字为 $a_i$。

小蓝向小桥请教后得知，只有当圆盘上所有宝石的数字相同时，才能解开圆盘的秘密。

小蓝可以进行如下操作：每次选择一颗宝石，将其数字更改为与其相邻的任意一颗宝石上的数字。

请问，小蓝最少需要进行多少次操作才能解开圆盘的秘密？

注意：第 $1$ 颗宝石和第 $n$ 颗宝石也相邻。

输入格式

第一行输入一个整数 $n(1 \leq n \le 1000)$ 表示宝石的数量。

第二行输入 $n$ 个空格分割的整数 $a_1,a_2,\cdots,a_n(1 \leq a_i \le n)$ 表示宝石上的数字。

输出格式

输出一个整数表示答案。

输入样例

4
1 2 1 2

输出样例

2

T4. 植物保留【算法赛】

问题描述

在一个植物研究保护区内，有 $N$ 种珍稀植物排列成一条直线，其中第 $i$ 种植物处于位置 $Y_i$ 上。

为了保证每种植物的生长环境不被其他植物干扰，研究人员决定让每两种植物之间保留至少 $M$ 米的距离。

现在，你可以选择移除一些植物，但要求剩下植物之间的距离都大于等于 $M$ 米。请问，你最多可以保留多少种植物。

输入格式

输入包含两行：

第一行包含两个整数 $N$ 和 $M$（$1 \leq N \leq 10^5$，$1 \leq M \leq 10^9$），表示植物的数量和距离要求。

第二行包含 $N$ 个整数 $Y_1, Y_2, \dots, Y_N$（$-10^9 \leq Y_1 < Y_2 < \dots < Y_N \leq 10^9$），表示每种植物的分布位置。

输出格式

输出一个整数，表示最多可以保留的植物数量。

样例输入

3 2
1 2 3

样例输出

2

在样例中，一种最优的策略是移除第 $2$ 个，使得剩下的钉子之间的距离都大于等于 $2$。

T5. 龙骑士军团【算法赛】

问题描述

龙骑士军团是蓝桥王国战斗力最强的军团，该军团总共有 $n$ 位龙骑士，其中第 $i$ 位龙骑士的战斗力为 $a_i$。

国王想考察一下军团长小蓝对于军团的掌控能力。具体来说，国王会提出 $q$ 个询问，每次询问给定四个整数 $a, b, c, d$，并要求小蓝从区间 $[a, b]$ 中选择一个点 $L$，从区间 $[c, d]$ 中选择一个点 $R$，使得 $\sum_{i=L}^R a_i$ 的值最大化。

这些问题难倒了小蓝。作为小蓝的助手，请你帮他解决这些问题。针对每个询问，你无需找出具体的 $L$ 和 $R$，只需给出 $\sum_{i=L}^R a_i$ 的最大值即可。

输入格式

第一行输入两个整数 $n,q(1 \leq n,q \leq 2 \times 10^5)$，表示龙骑士数量和国王的询问数量。

第二行输入 $n$ 个整数 $a_1,a_2,a_3,\cdots,a_n(-10^9 \leq a_i \leq 10^9)$，依稀表示每位龙骑士的战斗力。

接下来 $q$ 行，每行四个整数 $a,b,c,d(1 \leq a\leq b < c \le d \leq n)$，表示一次询问。

输出格式

输出 $q$ 行，每行一个整数表示答案。

样例输入

8 3
-1 2 -3 4 -5 6 -7 8
1 2 3 4
1 1 2 2
1 3 5 8

样例输出

3
1
5

样例说明

对于第一个查询，$L$ 我们可以选择 $2$，$R$ 选择 $4$，区间 $[2,4]$ 的和为 $3$。

T6. 热身操领队【算法赛】

问题描述

小蓝最喜欢的学科是体育课。每节体育课都会以热身操开始。为了使热身操更有趣，也为了让学生们更加投入，体育老师会要求学生们按照身高顺序站成一排，并从中选出站在队伍中间的学生作为领队带头热身。如果有两个学生站在中间，他会选择较矮的那个。例如：

• 如果学生们的身高为 $1$、$3$、$5$、$7$、$11$，则身高为 $5$ 的学生将被选中带领热身操。
• 如果学生们的身高为 $1$、$3$、$7$、$11$，则身高为 $3$ 的学生将被选中带领热身操。

小蓝想要更好地参与体育课，对此，他希望自己能准确得知热身操领队学生的身高情况。

小蓝的朋友小桥很擅长估算人们的身高，他会给小蓝 $n$​ 条信息，每条信息的内容形式为：“有 $a_i$​ 个身高为 $v_i$​ 的学生进入了体育馆”。每当小桥说完一条信息后，小蓝都想知道，如果当前进入体育馆的学生都是来上体育课的，那么带领热身操的学生的身高会是多少。

请你帮助小蓝解答问题。

输入格式

第一行包含一个整数 $n$（$1 \leq n \leq 2\times 10^5$），表示小桥给出的信息条数。

接下来的 $n$ 行，每行包含两个整数 $v_i$ 和 $a_i$（$1 \leq v_i,a_i \leq 10^9$），其含义如题所述。

输出格式

输出 $n$ 行，每行一个整数。第 $i$ 行输出对应小桥给出第 $i$ 条信息后：在当前进入体育馆的学生都是来上体育课的情况下，带领热身操的学生的身高。

样例输入

3
2 1
3 1
1 1

样例输出

2
2
2

T7. 单词博弈【算法赛】

问题描述

夏日夜晚，小蓝和小桥在蓝桥公园散步。在蜿蜒的小路上，他们发现了一堆单词。

小蓝和小桥对这些单词饶有兴致，于是开始收集它们：小蓝收集了 $n$ 个单词，小桥收集了 $m$ 个单词。收集完单词后，他们决定玩一个游戏。

游戏规则如下：每一回合，玩家需要从自己收集到的单词中说出一个单词。所说的单词必须满足以下条件：该单词的字典序大小要比上一个单词大，并且该单词要么与上一个单词以相同的字母开头，要么以字母表中紧随其后的字母开头。

例如，如果上一个单词是 apple，那么接下来的单词可以是：

1. 以相同字母 a 开头的单词，如 apply。
2. 以字母表中紧随 a 之后的字母 b 开头的单词，如 banana。

如果某个玩家无法满足上述条件，则该玩家输掉游戏。

小蓝和小桥轮流进行，由小蓝率先开始。

已知小蓝第一次会说出自己单词堆中按字典序排列最小的单词。请问，如果小蓝和小桥都按照最优策略进行游戏，谁会获胜？

输入格式

第一行包含整数 $n$ 和 $m$ $(1 \leq n, m \leq {10}^{5})$，分别表示小蓝和小桥收集到的单词数量。

接下来的 $n$ 行，每行包含一个字符串，表示小蓝收集到的单词。

再接下来的 $m$ 行，每行包含一个字符串，表示小桥收集到的单词。

单词只包含小写英文字母。所有单词互不相同，且它们的总长度不超过 ${10}^{6}$。小蓝和小桥的单词都按字典顺序给出。

输出格式

如果小蓝获胜了，输出 L。否则输出 Q。

样例输入

2 1
apple
echo
banana

样例输出

Q

样例说明

小蓝以单词 apple 开始，接着小桥说出她唯一的单词 banana。小蓝无法继续了，因此她输了。

T8. 升级电缆【算法赛】

问题描述

市长小蓝致力于改善城市的电力传输网络。这个城市由 $n$ 个节点组成，每两个节点之间通过 $n-1$ 条不同的双向电缆连接，这使得从任何一个节点都可以到达其他任意节点。

小蓝希望升级一些电缆以提高电力传输效率。对于每条电缆，我们知道当前的传输速度 $v_{i}$，升级所需的费用 $c_{i}$（单位：元） 以及升级后的传输速度 $s_{i}$。

城市中有 $q$ 位市民提出了各自的升级建议。第 $i$ 位市民的建议是：“我们应该投资 $e_{i}$ 元来升级节点 $a_{i}$ 和节点 $b_{i}$ 之间的电缆。”

对于每一个建议，小蓝想知道，如果他最多花费 $e_{i}$ 元来升级节点 $a_i$ 和 $b_i$ 之间的电缆，那么节点 $a_{i}$ 和节点 $b_{i}$ 之间的电缆的最小传输速度的最大可能值会是多少？

小蓝很快意识到计算这个问题并不容易，因此他聘请了你来帮助他！

输入格式

第一行包含一个整数 $n$（$2 \leq n \leq 10^5$），表示节点的数量。

接下来的 $n - 1$ 行中，每行包含五个整数 $x_i,y_i,v_i,c_i,s_i$（$1 \leq x_i,y_i \leq n, 1 \leq v_i < s_i \leq 10^{9}, 1 \leq c_i \leq 10^{9}$），表示节点 $x_i$ 和 $y_i$ 之间有一条电缆，当前传输速度是 $v_i$，升级这条电缆的费用是 $c_i$，升级后的传输速度是 $s_i$。

接下来的第一行包含一个整数 $q$（$1 \leq q \leq 10^5$），表示提出建议的市民的数量。

接下来的 $q$ 行中，每行包含三个整数 $a_i,b_i,e_i$（$1 \leq a_i,b_i \leq n, a_i \ eq b_i, 1 \leq e_i \leq 10^{18}$），表示了第 $i$ 名市民的建议。

输出格式

对于每个建议，输出一行，包含一个整数，表示在最多花费 $e_{i}$ 元来升级节点 $a_i$ 和 $b_i$ 之间的电缆时，节点 $a_{i}$ 和节点 $b_{i}$ 之间的电缆的最小传输速度的最大可能值。

样例输入

3
1 2 3 5 4
2 3 4 5 5
1
1 3 5

样例输出

4

样例说明

在给定样例中：

• $1\leftrightarrow 2$ 的传输速率是 $3$，升级费用是 $5$ 元，升级后的传输速率是 $4$。
• $2\leftrightarrow 3$ 的传输速率是 $4$，升级费用是 $5$ 元，升级后的传输速率是 $5$。

市民建议投资 $5$ 元来升级节点 $1$、$3$ 之间的电缆。

对此，小蓝可以用这 $5$ 元升级 $1\leftrightarrow 2$，使其传输速率变为 $4$。

升级之后，节点 $1$、$3$ 之间的电缆的最小传输速率的最大值为 $4$。