请输入文本

复仇者_帅童

2025-08-15 21:58:58

发布于：浙江

31阅读

0回复

0点赞

T1. 中考前的复习

帅童正在黑板上复习数学知识点。他写下了若干数字，这些数字只能是 $1$ 、 $2$ 或 $3$ 。其中数字 $1$ 有 $a$ 个，数字 $2$ 有 $b$ 个，数字 $3$ 有 $c$ 个。老师告诉他可以进行如下操作：

• 选择两个不同的数字并将它们擦除，然后写下与这两个数字都不同的第三个数字。

例如，假设黑板上写着 $1$ 、 $1$ 、 $1$ 、 $2$ 、 $3$ 、 $3$ 。他可以选择数字 $1$ 和 $3$ 擦除，此时黑板变为 $1$ 、 $1$ 、 $2$ 、 $3$ 。接着他需要再写一个数字 $2$ ，最终黑板上的数字变为 $1$ 、 $1$ 、 $2$ 、 $3$ 、 $2$ 。

老师问帅童：是否可以通过若干次操作，使得黑板上最终只剩下同一种数字？如果可能，会是哪些数字？

帅童一时想不出来，请你帮他解决这个问题。作为回报，他会说服老师给你加分。

输入格式

输入包含多个测试用例。第一行包含测试用例的数量 $t$ ( $1 \leq t \leq 10^5$ )。每个测试用例的描述如下：

每个测试用例的第一行也是唯一一行包含三个整数 $a$ 、 $b$ 、 $c$ ( $1 \leq a, b, c \leq 100$ ) —— 分别表示数字 $1$ 、数字 $2$ 和数字 $3$ 的数量。

输出格式

对于每个测试用例，输出一行包含 $3$ 个整数。

第一个整数为 $1$ 表示可以通过操作使得最终只剩下数字 $1$ ，否则为 $0$ 。
第二个整数为 $1$ 表示可以通过操作使得最终只剩下数字 $2$ ，否则为 $0$ 。
第三个整数为 $1$ 表示可以通过操作使得最终只剩下数字 $3$ ，否则为 $0$ 。

样例输入

样例输出

1 1 1
0 1 0
1 0 0

样例解释

在第一个测试用例中，帅童可以擦除数字 $2$ 和 $3$ 并写下数字 $1$ 。这样黑板上就会有 $2$ 个数字 $1$ 。通过类似操作，他也可以让黑板上只剩数字 $2$ 或数字 $3$ 。

在第二个测试用例中，他可以擦除数字 $1$ 和 $3$ 并写下数字 $2$ 。执行两次这样的操作后，黑板上将只剩下数字 $2$ 。可以证明无法让黑板上只剩数字 $1$ 或数字 $3$ 。

在第三个测试用例中，存在一系列操作可以让黑板上只剩数字 $1$ 。可以证明无法让黑板上只剩数字 $2$ 或数字 $3$ 。

T2. 考前小游戏

明天才考试，因此帅童只能考前玩一款无聊的MMORPG游戏。游戏中有 $n$ 个编号从 $1$ 到 $n$ 的任务，完成这些任务可以获得经验值。任务完成规则如下：

任务 $1$ 总是可以直接完成
任务 $i$ ( $i > 1$ ) 只有在所有编号比它小的任务都至少完成过一次后才能解锁

帅童可以重复完成同一个任务多次。每次完成任务获得的经验值为：

第一次完成任务 $i$ ：获得 $a_i$ 点经验值
之后每次完成任务 $i$ ：获得 $b_i$ 点经验值

帅童最多只愿意完成 $k$ 个任务。请你计算他最多能获得多少经验值。

输入格式

第一行包含整数 $t$ ( $1 \leq t \leq 10^4$ ) —— 测试用例数量

每个测试用例包含：

第一行两个整数 $n$ 和 $k$ ( $1 \leq n \leq 2 \cdot 10^5$ ; $1 \leq k \leq 2 \cdot 10^5$ ) —— 任务数量和最多可完成任务数
第二行 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ( $1 \leq a_i \leq 10^3$ )
第三行 $n$ 个整数 $b_1, b_2, \ldots, b_n$ ( $1 \leq b_i \leq 10^3$ )

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$

输出格式

对于每个测试用例，输出一个整数表示可获得的最大经验值

样例输入

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

样例输出

样例解释

第一个测试用例：

最优任务顺序：1, 1, 2, 3, 2, 4, 4
获得经验： $4 + 1 + 3 + 1 + 1 + 2 + 1 = 13$

第二个测试用例：

最优任务顺序：1, 1
获得经验： $1 + 3 = 4$

第三个测试用例：

最优任务顺序：1, 2, 2, 2, 3
获得经验： $3 + 2 + 3 + 3 + 4 = 15$

T3. 走在中考的小路上

走在中考的小路上

帅童要从家出发前往考场。因为一些意义不明的原因，帅童竟然住在一棵二叉树上。而帅童的家就是这个二叉树的根节点。

这条路上有 $n$ 个节点，编号从 1 开始，其中 1 号是帅童的家。每个节点都有以下特点：

可能可以往左走，到达左边的节点
可能可以往右走，到达右边的节点

帅童想要前往考场，他知道考场一定设置在树上的叶子结点（无法向左走和向右走的节点）

但是现在这棵树上正在施工，每个节点 $i$ 都有一个指示牌，指示牌上有一个字符。每个节点只能指示牌上标注的方向是可以走的。具体规则为：

字符 'U'：只能返回上一个节点
字符 'L'：只能向左走
字符 'R'：只能向右走

但是帅童非常有权力。因此，他可以提前修改任意路口的指示牌为任意字符。

请计算他最少需要修改多少个指示牌，才能确保从家出发一定能到达某个考场。

输入格式

第一行 $t$ ( $1 \leq t \leq 5 \cdot 10^4$ ) —— 测试用例数量

每个测试用例：

第一行包含一个整数 $n$ ( $2 \leq n \leq 3 \cdot 10^5$ ) —— 表示节点总数

第二行包含一个长度为 $n$ 的字符串 $s$ —— 表示每个节点的指示牌上的字符。

接下来 $n$ 行，每行两个整数 $l_i$ 和 $r_i$ $(0\leq l_i, r_i \leq n) $ — 第 $i$ 个点往左走和往右走可以到达的节点编号。如果 $l_i = 0$ ，表示节点 $i$ 无法向左走；如果 $r_i = 0$ 表示节点 $i$ 无法向右走。

保证所有测试用例 $n$ 之和不超过 $3 \cdot 10^5$

输出格式

对于每个测试用例，输出一个整数表示最少需要修改的指示牌数量

样例输入

样例输出

样例解释

第一个测试用例：1号路口（家）的往左走可以到达2号节点，往右走可以到达3号节点。2号和3号路口都无法往左走和往右走，因此是考场。由于1号路口的指示牌是'L'，帅童会直接前往2号考场，无需修改任何指示牌。

第二个测试用例：1号路口（家）的往左走可以到达2号节点，往右走可以到达3号节点。2号和3号路口都无法往左走和往右走，因此是考场。但是1号路口的指示牌是'U'。但1号是家没有上一个路口，因此需要改为'L'或'R'才能到达考场。

第三个测试用例：节点1只能往右走到达2，但是1上面写成L，所以帅童需要把它改成R，否则他会一直停在节点1。

第四个测试用例：需要修改3个节点的指示牌，使得最终的指示牌序列为"LURL"，这样才能确保帅童能到达2号考场。

第五个测试用例：考场位于3号、6号和7号节点。如果要将帅童引导至6号或7号考场，需要修改2个指示牌。但只需将1号路口的指示牌改为'R'，就能直接到达3号考场，因此最少只需修改1个指示牌。

T4. 突然出现了一条河

过河建桥问题

帅童在去考场的路上遇到了一条河，这条河可以看作一个 $n$ 行 $m$ 列的网格。每个格子 $(i,j)$ 有一个深度值 $a_{i,j}$ 。河的两岸（第一列和最后一列）的深度都是 0。

帅童可以在第 $i $ 行建造桥梁，但这需要建造一些桥墩，因此，需要花钱。具体规则如下：

必须在行的起点 $(i,1)$ 和终点 $(i,m)$ 安装桥墩
相邻桥墩之间的距离不能超过 $d$ （距离定义为 $|j_1-j_2|-1$ ）
在格子 $(i,j)$ 安装桥墩的成本为 $a_{i,j}+1$

为了使得帅童能从桥上走过去，他需要选择连续的 $k$ 行建造桥梁。即帅童需要选择一个 $i(1\leq i \leq n - k + 1)$ ，然后分别独立地在第 $i, i+1, \dots,i + k - 1$ 行建造桥梁。

帅童希望你帮他算一下建造 $k$ 座连续的桥梁的最小总成本。

输入格式

第一行 $t$ ( $1 \leq t \leq 10^3$ ) —— 测试用例数量

每个测试用例包含：

第一行四个整数 $n,m,k,d(1\leq k\leq n \leq 100, 3\leq m \leq 2 \cdot 10^5, 1\leq d \leq m )$ $n, m, k, d (1 \leq k \leq n \leq 100, 3 \leq m \leq 2 \cdot 1 0^{5}, 1 \leq d \leq m)$ ：
- $n$ ：行数
- $m$ ：列数
- $k$ ：需要建造的连续桥梁数
- $d$ ：最大允许桥墩间距
接下来 $n$ $n$ 行，每行 $m$ $m$ 个整数 $a_{i,j}$ $a_{i, j}$ ，表示各格子深度
- 保证 $a_{i,1}=a_{i,m}=0$
- $0 \leq a_{i,j} \leq 10^6$

保证所有测试用例的 $n \cdot m$ 之和不超过 $2 \cdot 10^5$

输出格式

对于每个测试用例，输出一个整数表示最小总成本

样例输入

5
3 11 1 4
0 1 2 3 4 5 4 3 2 1 0
0 1 2 3 2 1 2 3 3 2 0
0 1 2 3 5 5 5 5 5 2 0
4 4 2 1
0 3 3 0
0 2 1 0
0 1 2 0
0 3 3 0
4 5 2 5
0 1 1 1 0
0 2 2 2 0
0 2 1 1 0
0 3 2 1 0
1 8 1 1
0 10 4 8 4 4 2 0
4 5 3 2
0 8 4 4 0
0 3 4 8 0
0 8 1 10 0
0 10 1 5 0

样例输出

样例解释

第一个测试用例：最优方案是在第二行建桥，总成本为4

注：图示说明（原Note中的描述）：

灰色格子表示桥梁，白色格子为空，黑色格子为桥墩，蓝色格子为水，棕色格子为河底

第二个测试用例：最优方案是在第二和第三行建桥，桥墩分别安装在(2,3)和(3,2)等位置

第三个测试用例：最优方案是只在两岸安装桥墩

T5. 算了还是去玩吧

由于造桥实在是太麻烦了，帅童决定不去中考了。他打算在接下来的 $n$ 个小时里和朋友一起玩。他想在这 $n$ 个小时中分别尝试以下三个不同的活动，每个活动各玩一次：

滑雪
看电影
玩桌游

帅童知道，在第 $i$ 个小时：

有 $a_i$ 个朋友愿意和他去滑雪
有 $b_i$ 个朋友愿意和他去看电影
有 $c_i$ 个朋友愿意和他玩桌游

由于不能在一个小时内进行多个活动，请你帮帅童选择三个不同的小时 $x, y, z$ ，使得参与活动的朋友总数 $(a_x + b_y + c_z)$ 最大。

输入格式

第一行包含整数 $t$ ( $1 \leq t \leq 10^4$ ) —— 测试用例数量

每个测试用例包含：

第一行 $n$ ( $3 \leq n \leq 10^5$ ) —— 总小时数
第二行 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ( $1 \leq a_i \leq 10^8$ ) —— 第 $i$ 小时可以滑雪的朋友数
第三行 $n$ 个整数 $b_1, b_2, \ldots, b_n$ ( $1 \leq b_i \leq 10^8$ ) —— 第 $i$ 小时可以电影的朋友数
第四行 $n$ 个整数 $c_1, c_2, \ldots, c_n$ ( $1 \leq c_i \leq 10^8$ ) —— 第 $i$ 小时可以玩桌游的朋友数

保证所有测试用例的 $n$ 之和不超过 $10^5$

输出格式

对于每个测试用例，输出一个整数表示最多能参与活动的朋友总数

样例输入

4
3
1 10 1
10 1 1
1 1 10
4
30 20 10 1
30 5 15 20
30 25 10 10
10
5 19 12 3 18 18 6 17 10 13
15 17 19 11 16 3 11 17 17 17
1 17 18 10 15 8 17 3 13 12
10
17 5 4 18 12 4 11 2 16 16
8 4 14 19 3 12 6 7 5 16
3 4 8 11 10 8 10 2 20 3

样例输出

样例解释

第一个测试用例：帅童可以选择：第 $2$ 小时滑雪（ $10$ 人），第 $1$ 小时看电影（ $10$ 人），第 $3$ 小时玩桌游（ $10$ 人）。朋友总数为 $10 + 10 + 10 = 30$ 。

第二个测试用例：帅童可以选择：第 $1$ 小时滑雪（ $30$ 人），第 $4$ 小时看电影（ $20$ 人），第 $2$ 小时玩桌游（ $25$ 人）。朋友总数为 $30 + 20 + 25 = 75$ 。注意不能选择同一个小时进行多个活动。

第三个测试用例：帅童可以选择：第 $2$ 小时滑雪（ $19$ 人），第 $3$ 小时看电影（ $19$ 人），第 $7$ 小时玩桌游（ $17$ 人）。朋友总数为 $19 + 19 + 17 = 55$ 。

第四个测试用例：帅童可以选择：第 $1$ 小时滑雪（ $17$ 人），第 $4$ 小时看电影（ $19$ 人），第 $9$ 小时玩桌游（ $20$ 人）。朋友总数为 $17 + 19 + 20 = 56$ 。

T6. 竟然有补考？

帅童因为没学上了，被麻麻赶出来了。但是他在路上遇到了小牛王高级中学的招生主任，他遇到了一些问题。他答应帅童，如果能帮他解决这个问题，就可以给帅童补考的机会。他现在有一堆数字，他想让这些数字变得更加美丽，但是他不知道他需要如何更高效率地完成这件事。

招生主任有给定一个长度为 $n$ 的整数数组 $a_1, a_2, \ldots, a_n$ 和一个整数 $k$ 。

在进行操作前，你可以随意重新排列数组元素。

每次操作可以选择一个元素，将其增加 $k$ 。

一个数组 $b$ 被称为"美丽"的，当且仅当对于所有 $1 \leq i \leq n$ ，都满足 $b_i = b_{n-i+1}$ 。

帅童需要用最少的操作次数使数组变得"美丽"，或判断这个数组这辈子都不可能美丽了。

输入格式

第一行 $t$ ( $1 \leq t \leq 10^4$ ) —— 测试用例数量

每个测试用例包含：

第一行两个整数 $n$ 和 $k$ ( $1 \leq n \leq 10^5$ , $1 \leq k \leq 10^9$ ) —— 数组长度和每次可以增加的数字
第二行 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ( $1 \leq a_i \leq 10^9$ ) —— 数组元素

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$

输出格式

对于每个测试用例，输出使数组美丽所需的最小操作次数，如果不可能则输出 -1。

样例输入

11
1 1000000000
1
2 1
624323799 708290323
3 1
3 2 1
4 1
7 1 5 3
5 1
11 2 15 7 10
7 1
1 8 2 16 8 16 31
13 1
2 1 1 3 3 11 12 22 45 777 777 1500 74
10 2
1 2 1 2 1 2 1 2 1 2
11 2
1 2 1 2 1 2 1 2 1 2 1
13 3
2 3 9 14 17 10 22 20 18 30 1 4 28
5 1
2 3 5 3 5

样例输出

样例解释

第一个测试用例：数组已经是美丽的，不需要操作。

第二个测试用例：可以随意重新排列数组后对原数组的第一个元素进行 83966524 次操作。

第三个测试用例：先重新排列数组使其等于 $[2,3,1]$ 。然后对第三个元素进行一次操作得到 $[2,3,2]$ 。

第八个测试用例：无论如何重排和操作都无法使数组美丽，开摆！。

第九个测试用例：数组已经是美丽的。

Ex. 亿百昏！

补考智力测试题

帅童终于通过智力测试获得了补考机会。试卷上只有这一道题，帅童不想没学上，所以他来寻求了你的帮助。

对于一个数组 $c$ 中的某个值 $x$ ，定义其距离 $d_x(c)$ 为该值在数组中任意两次出现位置的最大间隔。具体来说：

$d_x(c) = \max(j - i)$ ，其中 $c_i = c_j = x$ 且 $i < j$
如果 $x$ 只出现一次或未出现，则 $d_x(c) = 0$

数组的美观度定义为所有不同值的距离之和：$\sum\limits_{1 \leq x \leq n} d_x(c) $

给定一个长度为 $n$ 的数组 $a$ ，定义一个长度为 $n$ 的数组 $b$ 为"合格数组"当且仅当：对于所有 $1 \leq i \leq n$ ，满足 $1 \leq b_i \leq a_i$ 。

你需要找到在所有"合格数组"中，美观值最大的数组的美观值是多少。

输入格式

第一行 $t$ ( $1 \leq t \leq 10^4$ ) —— 测试用例数量。

每个测试用例包含：

第一行 $n$ ( $1 \leq n \leq 2 \cdot 10^5$ ) —— 数组长度。
第二行 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ( $1 \leq a_i \leq n$ ) —— 数组中的每个元素。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$

输出格式

对于每个测试用例，输出一个整数表示最大可能的美观度

样例输入

4
4
1 2 1 2
2
2 2
10
1 2 1 5 1 2 2 1 1 2
8
1 5 2 8 4 1 4 2

样例输出

样例解释

第一个测试用例：当 $b = [1,2,1,2]$ 时， $d_1(b)=2$ ， $d_2(b)=2$ ，美观度为 $4$ 。可以证明这是最大可能值。

第二个测试用例： $b = [1,1]$ 或 $b = [2,2]$ 都能得到美观度 $1$ 。

第三个测试用例：当 $b = [1,2,1,4,1,2,1,1,1,2]$ 时， $d_1(b)= 9 - 1 = 8$ ， $d_2(b)= 10 - 2 = 8,d_4(b) = 0$ ，因此美观度为 $16$ 。# T1. 中考前的复习

• 选择两个不同的数字并将它们擦除，然后写下与这两个数字都不同的第三个数字。

老师问帅童：是否可以通过若干次操作，使得黑板上最终只剩下同一种数字？如果可能，会是哪些数字？

帅童一时想不出来，请你帮他解决这个问题。作为回报，他会说服老师给你加分。

输入格式

输入包含多个测试用例。第一行包含测试用例的数量 $t$ ( $1 \leq t \leq 10^5$ )。每个测试用例的描述如下：

每个测试用例的第一行也是唯一一行包含三个整数 $a$ 、 $b$ 、 $c$ ( $1 \leq a, b, c \leq 100$ ) —— 分别表示数字 $1$ 、数字 $2$ 和数字 $3$ 的数量。

输出格式

对于每个测试用例，输出一行包含 $3$ 个整数。

样例输入

样例输出

1 1 1
0 1 0
1 0 0

样例解释

在第三个测试用例中，存在一系列操作可以让黑板上只剩数字 $1$ 。可以证明无法让黑板上只剩数字 $2$ 或数字 $3$ 。

T2. 考前小游戏

明天才考试，因此帅童只能考前玩一款无聊的MMORPG游戏。游戏中有 $n$ 个编号从 $1$ 到 $n$ 的任务，完成这些任务可以获得经验值。任务完成规则如下：

任务 $1$ 总是可以直接完成
任务 $i$ ( $i > 1$ ) 只有在所有编号比它小的任务都至少完成过一次后才能解锁

帅童可以重复完成同一个任务多次。每次完成任务获得的经验值为：

第一次完成任务 $i$ ：获得 $a_i$ 点经验值
之后每次完成任务 $i$ ：获得 $b_i$ 点经验值

帅童最多只愿意完成 $k$ 个任务。请你计算他最多能获得多少经验值。

输入格式

第一行包含整数 $t$ ( $1 \leq t \leq 10^4$ ) —— 测试用例数量

每个测试用例包含：

第一行两个整数 $n$ 和 $k$ ( $1 \leq n \leq 2 \cdot 10^5$ ; $1 \leq k \leq 2 \cdot 10^5$ ) —— 任务数量和最多可完成任务数
第二行 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ( $1 \leq a_i \leq 10^3$ )
第三行 $n$ 个整数 $b_1, b_2, \ldots, b_n$ ( $1 \leq b_i \leq 10^3$ )

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$

输出格式

对于每个测试用例，输出一个整数表示可获得的最大经验值

样例输入

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

样例输出

样例解释

第一个测试用例：

最优任务顺序：1, 1, 2, 3, 2, 4, 4
获得经验： $4 + 1 + 3 + 1 + 1 + 2 + 1 = 13$

第二个测试用例：

最优任务顺序：1, 1
获得经验： $1 + 3 = 4$

第三个测试用例：

最优任务顺序：1, 2, 2, 2, 3
获得经验： $3 + 2 + 3 + 3 + 4 = 15$

T3. 走在中考的小路上

走在中考的小路上

帅童要从家出发前往考场。因为一些意义不明的原因，帅童竟然住在一棵二叉树上。而帅童的家就是这个二叉树的根节点。

这条路上有 $n$ 个节点，编号从 1 开始，其中 1 号是帅童的家。每个节点都有以下特点：

可能可以往左走，到达左边的节点
可能可以往右走，到达右边的节点

帅童想要前往考场，他知道考场一定设置在树上的叶子结点（无法向左走和向右走的节点）

但是现在这棵树上正在施工，每个节点 $i$ 都有一个指示牌，指示牌上有一个字符。每个节点只能指示牌上标注的方向是可以走的。具体规则为：

字符 'U'：只能返回上一个节点
字符 'L'：只能向左走
字符 'R'：只能向右走

但是帅童非常有权力。因此，他可以提前修改任意路口的指示牌为任意字符。

请计算他最少需要修改多少个指示牌，才能确保从家出发一定能到达某个考场。

输入格式

第一行 $t$ ( $1 \leq t \leq 5 \cdot 10^4$ ) —— 测试用例数量

每个测试用例：

第一行包含一个整数 $n$ ( $2 \leq n \leq 3 \cdot 10^5$ ) —— 表示节点总数

第二行包含一个长度为 $n$ 的字符串 $s$ —— 表示每个节点的指示牌上的字符。

保证所有测试用例 $n$ 之和不超过 $3 \cdot 10^5$

输出格式

对于每个测试用例，输出一个整数表示最少需要修改的指示牌数量

样例输入

样例输出

样例解释

第三个测试用例：节点1只能往右走到达2，但是1上面写成L，所以帅童需要把它改成R，否则他会一直停在节点1。

第四个测试用例：需要修改3个节点的指示牌，使得最终的指示牌序列为"LURL"，这样才能确保帅童能到达2号考场。

T4. 突然出现了一条河

过河建桥问题

帅童可以在第 $i $ 行建造桥梁，但这需要建造一些桥墩，因此，需要花钱。具体规则如下：

必须在行的起点 $(i,1)$ 和终点 $(i,m)$ 安装桥墩
相邻桥墩之间的距离不能超过 $d$ （距离定义为 $|j_1-j_2|-1$ ）
在格子 $(i,j)$ 安装桥墩的成本为 $a_{i,j}+1$

帅童希望你帮他算一下建造 $k$ 座连续的桥梁的最小总成本。

输入格式

第一行 $t$ ( $1 \leq t \leq 10^3$ ) —— 测试用例数量

每个测试用例包含：

第一行四个整数 $n,m,k,d(1\leq k\leq n \leq 100, 3\leq m \leq 2 \cdot 10^5, 1\leq d \leq m )$ $n, m, k, d (1 \leq k \leq n \leq 100, 3 \leq m \leq 2 \cdot 1 0^{5}, 1 \leq d \leq m)$ ：
- $n$ ：行数
- $m$ ：列数
- $k$ ：需要建造的连续桥梁数
- $d$ ：最大允许桥墩间距
接下来 $n$ $n$ 行，每行 $m$ $m$ 个整数 $a_{i,j}$ $a_{i, j}$ ，表示各格子深度
- 保证 $a_{i,1}=a_{i,m}=0$
- $0 \leq a_{i,j} \leq 10^6$

保证所有测试用例的 $n \cdot m$ 之和不超过 $2 \cdot 10^5$

输出格式

对于每个测试用例，输出一个整数表示最小总成本

样例输入

5
3 11 1 4
0 1 2 3 4 5 4 3 2 1 0
0 1 2 3 2 1 2 3 3 2 0
0 1 2 3 5 5 5 5 5 2 0
4 4 2 1
0 3 3 0
0 2 1 0
0 1 2 0
0 3 3 0
4 5 2 5
0 1 1 1 0
0 2 2 2 0
0 2 1 1 0
0 3 2 1 0
1 8 1 1
0 10 4 8 4 4 2 0
4 5 3 2
0 8 4 4 0
0 3 4 8 0
0 8 1 10 0
0 10 1 5 0

样例输出

样例解释

第一个测试用例：最优方案是在第二行建桥，总成本为4

注：图示说明（原Note中的描述）：

灰色格子表示桥梁，白色格子为空，黑色格子为桥墩，蓝色格子为水，棕色格子为河底

第二个测试用例：最优方案是在第二和第三行建桥，桥墩分别安装在(2,3)和(3,2)等位置

第三个测试用例：最优方案是只在两岸安装桥墩

T5. 算了还是去玩吧

滑雪
看电影
玩桌游

帅童知道，在第 $i$ 个小时：

有 $a_i$ 个朋友愿意和他去滑雪
有 $b_i$ 个朋友愿意和他去看电影
有 $c_i$ 个朋友愿意和他玩桌游

由于不能在一个小时内进行多个活动，请你帮帅童选择三个不同的小时 $x, y, z$ ，使得参与活动的朋友总数 $(a_x + b_y + c_z)$ 最大。

输入格式

第一行包含整数 $t$ ( $1 \leq t \leq 10^4$ ) —— 测试用例数量

每个测试用例包含：

第一行 $n$ ( $3 \leq n \leq 10^5$ ) —— 总小时数
第二行 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ( $1 \leq a_i \leq 10^8$ ) —— 第 $i$ 小时可以滑雪的朋友数
第三行 $n$ 个整数 $b_1, b_2, \ldots, b_n$ ( $1 \leq b_i \leq 10^8$ ) —— 第 $i$ 小时可以电影的朋友数
第四行 $n$ 个整数 $c_1, c_2, \ldots, c_n$ ( $1 \leq c_i \leq 10^8$ ) —— 第 $i$ 小时可以玩桌游的朋友数

保证所有测试用例的 $n$ 之和不超过 $10^5$

输出格式

对于每个测试用例，输出一个整数表示最多能参与活动的朋友总数

样例输入

4
3
1 10 1
10 1 1
1 1 10
4
30 20 10 1
30 5 15 20
30 25 10 10
10
5 19 12 3 18 18 6 17 10 13
15 17 19 11 16 3 11 17 17 17
1 17 18 10 15 8 17 3 13 12
10
17 5 4 18 12 4 11 2 16 16
8 4 14 19 3 12 6 7 5 16
3 4 8 11 10 8 10 2 20 3

样例输出

样例解释

T6. 竟然有补考？

招生主任有给定一个长度为 $n$ 的整数数组 $a_1, a_2, \ldots, a_n$ 和一个整数 $k$ 。

在进行操作前，你可以随意重新排列数组元素。

每次操作可以选择一个元素，将其增加 $k$ 。

一个数组 $b$ 被称为"美丽"的，当且仅当对于所有 $1 \leq i \leq n$ ，都满足 $b_i = b_{n-i+1}$ 。

帅童需要用最少的操作次数使数组变得"美丽"，或判断这个数组这辈子都不可能美丽了。

输入格式

第一行 $t$ ( $1 \leq t \leq 10^4$ ) —— 测试用例数量

每个测试用例包含：

第一行两个整数 $n$ 和 $k$ ( $1 \leq n \leq 10^5$ , $1 \leq k \leq 10^9$ ) —— 数组长度和每次可以增加的数字
第二行 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ( $1 \leq a_i \leq 10^9$ ) —— 数组元素

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$

输出格式

对于每个测试用例，输出使数组美丽所需的最小操作次数，如果不可能则输出 -1。

样例输入

11
1 1000000000
1
2 1
624323799 708290323
3 1
3 2 1
4 1
7 1 5 3
5 1
11 2 15 7 10
7 1
1 8 2 16 8 16 31
13 1
2 1 1 3 3 11 12 22 45 777 777 1500 74
10 2
1 2 1 2 1 2 1 2 1 2
11 2
1 2 1 2 1 2 1 2 1 2 1
13 3
2 3 9 14 17 10 22 20 18 30 1 4 28
5 1
2 3 5 3 5

样例输出

样例解释

第一个测试用例：数组已经是美丽的，不需要操作。

第二个测试用例：可以随意重新排列数组后对原数组的第一个元素进行 83966524 次操作。

第三个测试用例：先重新排列数组使其等于 $[2,3,1]$ 。然后对第三个元素进行一次操作得到 $[2,3,2]$ 。

第八个测试用例：无论如何重排和操作都无法使数组美丽，开摆！。

第九个测试用例：数组已经是美丽的。

Ex. 亿百昏！

补考智力测试题

帅童终于通过智力测试获得了补考机会。试卷上只有这一道题，帅童不想没学上，所以他来寻求了你的帮助。

对于一个数组 $c$ 中的某个值 $x$ ，定义其距离 $d_x(c)$ 为该值在数组中任意两次出现位置的最大间隔。具体来说：

$d_x(c) = \max(j - i)$ ，其中 $c_i = c_j = x$ 且 $i < j$
如果 $x$ 只出现一次或未出现，则 $d_x(c) = 0$

数组的美观度定义为所有不同值的距离之和：$\sum\limits_{1 \leq x \leq n} d_x(c) $

给定一个长度为 $n$ 的数组 $a$ ，定义一个长度为 $n$ 的数组 $b$ 为"合格数组"当且仅当：对于所有 $1 \leq i \leq n$ ，满足 $1 \leq b_i \leq a_i$ 。

你需要找到在所有"合格数组"中，美观值最大的数组的美观值是多少。

输入格式

第一行 $t$ ( $1 \leq t \leq 10^4$ ) —— 测试用例数量。

每个测试用例包含：

第一行 $n$ ( $1 \leq n \leq 2 \cdot 10^5$ ) —— 数组长度。
第二行 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ( $1 \leq a_i \leq n$ ) —— 数组中的每个元素。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$

输出格式

对于每个测试用例，输出一个整数表示最大可能的美观度

样例输入

4
4
1 2 1 2
2
2 2
10
1 2 1 5 1 2 2 1 1 2
8
1 5 2 8 4 1 4 2

样例输出

样例解释

第一个测试用例：当 $b = [1,2,1,2]$ 时， $d_1(b)=2$ ， $d_2(b)=2$ ，美观度为 $4$ 。可以证明这是最大可能值。

第二个测试用例： $b = [1,1]$ 或 $b = [2,2]$ 都能得到美观度 $1$ 。

第三个测试用例：当 $b = [1,2,1,4,1,2,1,1,1,2]$ 时， $d_1(b)= 9 - 1 = 8$ ， $d_2(b)= 10 - 2 = 8,d_4(b) = 0$ ，因此美观度为 $16$ 。

有帮助，赞一个

去预览

0/2000

全部评论 2

复仇者_澜（不处不加团队）
被做局了哈哈哈

2025-08-16 来自广东
1
复仇者_澜（不处不加团队）
qp

2025-08-16 来自广东
0