T1. 中考前的复习
帅童正在黑板上复习数学知识点。他写下了若干数字，这些数字只能是 111、222 或 333。其中数字 111 有 aaa 个，数字 222 有 bbb 个，数字 333 有 ccc 个。老师告诉他可以进行如下操作：
• 选择两个不同的数字并将它们擦除，然后写下与这两个数字都不同的第三个数字。
例如，假设黑板上写着 111、111、111、222、333、333。他可以选择数字 111 和 333 擦除，此时黑板变为 111、111、222、333。接着他需要再写一个数字 222，最终黑板上的数字变为 111、111、222、333、222。
老师问帅童：是否可以通过若干次操作，使得黑板上最终只剩下同一种数字？如果可能，会是哪些数字？
帅童一时想不出来，请你帮他解决这个问题。作为回报，他会说服老师给你加分。
输入格式
输入包含多个测试用例。第一行包含测试用例的数量 ttt (1≤t≤1051 \leq t \leq 10^51≤t≤105)。每个测试用例的描述如下：
每个测试用例的第一行也是唯一一行包含三个整数 aaa、bbb、ccc (1≤a,b,c≤1001 \leq a, b, c \leq 1001≤a,b,c≤100) —— 分别表示数字 111、数字 222 和数字 333 的数量。
输出格式
对于每个测试用例，输出一行包含 333 个整数。
第一个整数为 111 表示可以通过操作使得最终只剩下数字 111，否则为 000。
第二个整数为 111 表示可以通过操作使得最终只剩下数字 222，否则为 000。
第三个整数为 111 表示可以通过操作使得最终只剩下数字 333，否则为 000。
样例输入
样例输出
样例解释
在第一个测试用例中，帅童可以擦除数字 222 和 333 并写下数字 111。这样黑板上就会有 222 个数字 111。通过类似操作，他也可以让黑板上只剩数字 222 或数字 333。
在第二个测试用例中，他可以擦除数字 111 和 333 并写下数字 222。执行两次这样的操作后，黑板上将只剩下数字 222。可以证明无法让黑板上只剩数字 111 或数字 333。
在第三个测试用例中，存在一系列操作可以让黑板上只剩数字 111。可以证明无法让黑板上只剩数字 222 或数字 333。
T2. 考前小游戏
明天才考试，因此帅童只能考前玩一款无聊的MMORPG游戏。游戏中有 nnn 个编号从 111 到 nnn 的任务，完成这些任务可以获得经验值。任务完成规则如下：
* 任务 111 总是可以直接完成
* 任务 iii (i>1i > 1i>1) 只有在所有编号比它小的任务都至少完成过一次后才能解锁
帅童可以重复完成同一个任务多次。每次完成任务获得的经验值为：
* 第一次完成任务 iii ：获得 aia_iai 点经验值
* 之后每次完成任务 iii ：获得 bib_ibi 点经验值
帅童最多只愿意完成 kkk 个任务。请你计算他最多能获得多少经验值。
输入格式
第一行包含整数 ttt (1≤t≤1041 \leq t \leq 10^41≤t≤104) —— 测试用例数量
每个测试用例包含：
1. 第一行两个整数 nnn 和 kkk (1≤n≤2⋅1051 \leq n \leq 2 \cdot 10^51≤n≤2⋅105; 1≤k≤2⋅1051 \leq k \leq 2 \cdot 10^51≤k≤2⋅105) —— 任务数量和最多可完成任务数
2. 第二行 nnn 个整数 a1,a2,…,ana_1, a_2, \ldots, a_na1 ,a2 ,…,an (1≤ai≤1031 \leq a_i \leq 10^31≤ai ≤103)
3. 第三行 nnn 个整数 b1,b2,…,bnb_1, b_2, \ldots, b_nb1 ,b2 ,…,bn (1≤bi≤1031 \leq b_i \leq 10^31≤bi ≤103)
保证所有测试用例的 nnn 之和不超过 2⋅1052 \cdot 10^52⋅105
输出格式
对于每个测试用例，输出一个整数表示可获得的最大经验值
样例输入
样例输出
样例解释
第一个测试用例：
* 最优任务顺序：1, 1, 2, 3, 2, 4, 4
* 获得经验：4+1+3+1+1+2+1=134 + 1 + 3 + 1 + 1 + 2 + 1 = 134+1+3+1+1+2+1=13
第二个测试用例：
* 最优任务顺序：1, 1
* 获得经验：1+3=41 + 3 = 41+3=4
第三个测试用例：
* 最优任务顺序：1, 2, 2, 2, 3
* 获得经验：3+2+3+3+4=153 + 2 + 3 + 3 + 4 = 153+2+3+3+4=15
T3. 走在中考的小路上
走在中考的小路上
帅童要从家出发前往考场。因为一些意义不明的原因，帅童竟然住在一棵二叉树上。而帅童的家就是这个二叉树的根节点。
这条路上有 nnn 个节点，编号从 1 开始，其中 1 号是帅童的家。每个节点都有以下特点：
* 可能可以往左走，到达左边的节点
* 可能可以往右走，到达右边的节点
帅童想要前往考场，他知道考场一定设置在树上的叶子结点（无法向左走和向右走的节点）
但是现在这棵树上正在施工，每个节点 iii 都有一个指示牌，指示牌上有一个字符。每个节点只能指示牌上标注的方向是可以走的。具体规则为：
* 字符 'U'：只能返回上一个节点
* 字符 'L'：只能向左走
* 字符 'R'：只能向右走
但是帅童非常有权力。因此，他可以提前修改任意路口的指示牌为任意字符。
请计算他最少需要修改多少个指示牌，才能确保从家出发一定能到达某个考场。
输入格式
第一行 ttt (1≤t≤5⋅1041 \leq t \leq 5 \cdot 10^41≤t≤5⋅104) —— 测试用例数量
每个测试用例：
第一行包含一个整数 nnn (2≤n≤3⋅1052 \leq n \leq 3 \cdot 10^52≤n≤3⋅105) —— 表示节点总数
第二行包含一个长度为 nnn 的字符串 sss —— 表示每个节点的指示牌上的字符。
接下来 nnn 行，每行两个整数 lil_ili 和 rir_iri $(0\leq l_i, r_i \leq n) $ — 第 iii 个点往左走和往右走可以到达的节点编号。如果 li=0l_i = 0li =0，表示节点 iii 无法向左走；如果 ri=0r_i = 0ri =0 表示节点 iii 无法向右走。
保证所有测试用例 nnn 之和不超过 3⋅1053 \cdot 10^53⋅105
输出格式
对于每个测试用例，输出一个整数表示最少需要修改的指示牌数量
样例输入
样例输出
样例解释
第一个测试用例：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. 突然出现了一条河
过河建桥问题
帅童在去考场的路上遇到了一条河，这条河可以看作一个 nnn 行 mmm 列的网格。每个格子 (i,j)(i,j)(i,j) 有一个深度值 ai,ja_{i,j}ai,j 。河的两岸（第一列和最后一列）的深度都是 0。
帅童可以在第 $i $ 行建造桥梁，但这需要建造一些桥墩，因此，需要花钱。具体规则如下：
1. 必须在行的起点 (i,1)(i,1)(i,1) 和终点 (i,m)(i,m)(i,m) 安装桥墩
2. 相邻桥墩之间的距离不能超过 ddd（距离定义为 ∣j1−j2∣−1|j_1-j_2|-1∣j1 −j2 ∣−1）
3. 在格子 (i,j)(i,j)(i,j) 安装桥墩的成本为 ai,j+1a_{i,j}+1ai,j +1
为了使得帅童能从桥上走过去，他需要选择连续的 kkk 行建造桥梁。即帅童需要选择一个 i(1≤i≤n−k+1)i(1\leq i \leq n - k + 1)i(1≤i≤n−k+1)， 然后分别独立地在第 i,i+1,…,i+k−1i, i+1, \dots,i + k - 1i,i+1,…,i+k−1 行建造桥梁。
帅童希望你帮他算一下建造 kkk 座连续的桥梁的最小总成本。
输入格式
第一行 ttt (1≤t≤1031 \leq t \leq 10^31≤t≤103) —— 测试用例数量
每个测试用例包含：
1. 第一行四个整数 n,m,k,d(1≤k≤n≤100,3≤m≤2⋅105,1≤d≤m)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≤k≤n≤100,3≤m≤2⋅105,1≤d≤m)：
* nnn：行数
* mmm：列数
* kkk：需要建造的连续桥梁数
* ddd：最大允许桥墩间距
2. 接下来 nnn 行，每行 mmm 个整数 ai,ja_{i,j}ai,j ，表示各格子深度
* 保证 ai,1=ai,m=0a_{i,1}=a_{i,m}=0ai,1 =ai,m =0
* 0≤ai,j≤1060 \leq a_{i,j} \leq 10^60≤ai,j ≤106
保证所有测试用例的 n⋅mn \cdot mn⋅m 之和不超过 2⋅1052 \cdot 10^52⋅105
输出格式
对于每个测试用例，输出一个整数表示最小总成本
样例输入
样例输出
样例解释
第一个测试用例：最优方案是在第二行建桥，总成本为4
注：图示说明（原Note中的描述）：
<img src="/Users/regen/Library/Application Support/typora-user-images/image-20250614015316712.png" alt="image-20250614015316712" style="zoom:50%;" />
灰色格子表示桥梁，白色格子为空，黑色格子为桥墩，蓝色格子为水，棕色格子为河底
第二个测试用例：最优方案是在第二和第三行建桥，桥墩分别安装在(2,3)和(3,2)等位置
第三个测试用例：最优方案是只在两岸安装桥墩
T5. 算了还是去玩吧
由于造桥实在是太麻烦了，帅童决定不去中考了。他打算在接下来的 nnn 个小时里和朋友一起玩。他想在这 nnn 个小时中分别尝试以下三个不同的活动，每个活动各玩一次：
* 滑雪
* 看电影
* 玩桌游
帅童知道，在第 iii 个小时：
* 有 aia_iai 个朋友愿意和他去滑雪
* 有 bib_ibi 个朋友愿意和他去看电影
* 有 cic_ici 个朋友愿意和他玩桌游
由于不能在一个小时内进行多个活动，请你帮帅童选择三个不同的小时 x,y,zx, y, zx,y,z，使得参与活动的朋友总数 (ax+by+cz)(a_x + b_y + c_z)(ax +by +cz ) 最大。
输入格式
第一行包含整数 ttt (1≤t≤1041 \leq t \leq 10^41≤t≤104) —— 测试用例数量
每个测试用例包含：
1. 第一行 nnn (3≤n≤1053 \leq n \leq 10^53≤n≤105) —— 总小时数
2. 第二行 nnn 个整数 a1,a2,…,ana_1, a_2, \ldots, a_na1 ,a2 ,…,an (1≤ai≤1081 \leq a_i \leq 10^81≤ai ≤108) —— 第 iii 小时可以滑雪的朋友数
3. 第三行 nnn 个整数 b1,b2,…,bnb_1, b_2, \ldots, b_nb1 ,b2 ,…,bn (1≤bi≤1081 \leq b_i \leq 10^81≤bi ≤108) —— 第 iii 小时可以电影的朋友数
4. 第四行 nnn 个整数 c1,c2,…,cnc_1, c_2, \ldots, c_nc1 ,c2 ,…,cn (1≤ci≤1081 \leq c_i \leq 10^81≤ci ≤108) —— 第 iii 小时可以玩桌游的朋友数
保证所有测试用例的 nnn 之和不超过 10510^5105
输出格式
对于每个测试用例，输出一个整数表示最多能参与活动的朋友总数
样例输入
样例输出
样例解释
第一个测试用例：帅童可以选择：第 222 小时滑雪（101010 人），第 111 小时看电影（101010 人），第 333 小时玩桌游（101010 人）。朋友总数为 10+10+10=3010 + 10 + 10 = 3010+10+10=30。
第二个测试用例：帅童可以选择：第 111 小时滑雪（303030 人），第 444 小时看电影（202020 人），第 222 小时玩桌游（252525 人）。朋友总数为 30+20+25=7530 + 20 + 25 = 7530+20+25=75。注意不能选择同一个小时进行多个活动。
第三个测试用例：帅童可以选择：第 222 小时滑雪（191919 人），第 333 小时看电影（191919 人），第 777 小时玩桌游（171717 人）。朋友总数为 19+19+17=5519 + 19 + 17 = 5519+19+17=55。
第四个测试用例：帅童可以选择：第 111 小时滑雪（171717 人），第 444 小时看电影（191919 人），第 999 小时玩桌游（202020 人）。朋友总数为 17+19+20=5617 + 19 + 20 = 5617+19+20=56。
T6. 竟然有补考？
帅童因为没学上了，被麻麻赶出来了。但是他在路上遇到了小牛王高级中学的招生主任，他遇到了一些问题。他答应帅童，如果能帮他解决这个问题，就可以给帅童补考的机会。他现在有一堆数字，他想让这些数字变得更加美丽，但是他不知道他需要如何更高效率地完成这件事。
招生主任有给定一个长度为 nnn 的整数数组 a1,a2,…,ana_1, a_2, \ldots, a_na1 ,a2 ,…,an 和一个整数 kkk。
在进行操作前，你可以随意重新排列数组元素。
每次操作可以选择一个元素，将其增加 kkk。
一个数组 bbb 被称为"美丽"的，当且仅当对于所有 1≤i≤n1 \leq i \leq n1≤i≤n，都满足 bi=bn−i+1b_i = b_{n-i+1}bi =bn−i+1 。
帅童需要用最少的操作次数使数组变得"美丽"，或判断这个数组这辈子都不可能美丽了。
输入格式
第一行 ttt (1≤t≤1041 \leq t \leq 10^41≤t≤104) —— 测试用例数量
每个测试用例包含：
1. 第一行两个整数 nnn 和 kkk (1≤n≤1051 \leq n \leq 10^51≤n≤105, 1≤k≤1091 \leq k \leq 10^91≤k≤109) —— 数组长度和每次可以增加的数字
2. 第二行 nnn 个整数 a1,a2,…,ana_1, a_2, \ldots, a_na1 ,a2 ,…,an (1≤ai≤1091 \leq a_i \leq 10^91≤ai ≤109) —— 数组元素
保证所有测试用例的 nnn 之和不超过 2⋅1052 \cdot 10^52⋅105
输出格式
对于每个测试用例，输出使数组美丽所需的最小操作次数，如果不可能则输出 -1。
样例输入
样例输出
样例解释
第一个测试用例：数组已经是美丽的，不需要操作。
第二个测试用例：可以随意重新排列数组后对原数组的第一个元素进行 83966524 次操作。
第三个测试用例：先重新排列数组使其等于 [2,3,1][2,3,1][2,3,1]。然后对第三个元素进行一次操作得到 [2,3,2][2,3,2][2,3,2]。
第八个测试用例：无论如何重排和操作都无法使数组美丽，开摆！。
第九个测试用例：数组已经是美丽的。
EX. 亿百昏！
补考智力测试题
帅童终于通过智力测试获得了补考机会。试卷上只有这一道题，帅童不想没学上，所以他来寻求了你的帮助。
对于一个数组 ccc 中的某个值 xxx，定义其距离 dx(c)d_x(c)dx (c) 为该值在数组中任意两次出现位置的最大间隔。具体来说：
* dx(c)=max(j−i)d_x(c) = \max(j - i)dx (c)=max(j−i)，其中 ci=cj=xc_i = c_j = xci =cj =x 且 i<ji < ji<j
* 如果 xxx 只出现一次或未出现，则 dx(c)=0d_x(c) = 0dx (c)=0
数组的美观度定义为所有不同值的距离之和：$\sum\limits_{1 \leq x \leq n} d_x(c) $
给定一个长度为 nnn 的数组 aaa，定义一个长度为 nnn 的数组 bbb 为"合格数组"当且仅当：对于所有 1≤i≤n1 \leq i \leq n1≤i≤n，满足 1≤bi≤ai1 \leq b_i \leq a_i1≤bi ≤ai 。
你需要找到在所有"合格数组"中，美观值最大的数组的美观值是多少。
输入格式
第一行 ttt (1≤t≤1041 \leq t \leq 10^41≤t≤104) —— 测试用例数量。
每个测试用例包含：
1. 第一行 nnn (1≤n≤2⋅1051 \leq n \leq 2 \cdot 10^51≤n≤2⋅105) —— 数组长度。
2. 第二行 nnn 个整数 a1,a2,…,ana_1, a_2, \ldots, a_na1 ,a2 ,…,an (1≤ai≤n1 \leq a_i \leq n1≤ai ≤n) —— 数组中的每个元素。
保证所有测试用例的 nnn 之和不超过 2⋅1052 \cdot 10^52⋅105
输出格式
对于每个测试用例，输出一个整数表示最大可能的美观度
样例输入
样例输出
样例解释
第一个测试用例：当 b=[1,2,1,2]b = [1,2,1,2]b=[1,2,1,2] 时，d1(b)=2d_1(b)=2d1 (b)=2，d2(b)=2d_2(b)=2d2 (b)=2，美观度为 444。可以证明这是最大可能值。
第二个测试用例：b=[1,1]b = [1,1]b=[1,1] 或 b=[2,2]b = [2,2]b=[2,2] 都能得到美观度 111。
第三个测试用例：当 b=[1,2,1,4,1,2,1,1,1,2]b = [1,2,1,4,1,2,1,1,1,2]b=[1,2,1,4,1,2,1,1,1,2] 时，d1(b)=9−1=8d_1(b)= 9 - 1 = 8d1 (b)=9−1=8，d2(b)=10−2=8,d4(b)=0d_2(b)= 10 - 2 = 8,d_4(b) = 0d2 (b)=10−2=8,d4 (b)=0，因此美观度为 161616。# T1. 中考前的复习
帅童正在黑板上复习数学知识点。他写下了若干数字，这些数字只能是 111、222 或 333。其中数字 111 有 aaa 个，数字 222 有 bbb 个，数字 333 有 ccc 个。老师告诉他可以进行如下操作：
• 选择两个不同的数字并将它们擦除，然后写下与这两个数字都不同的第三个数字。
例如，假设黑板上写着 111、111、111、222、333、333。他可以选择数字 111 和 333 擦除，此时黑板变为 111、111、222、333。接着他需要再写一个数字 222，最终黑板上的数字变为 111、111、222、333、222。
老师问帅童：是否可以通过若干次操作，使得黑板上最终只剩下同一种数字？如果可能，会是哪些数字？
帅童一时想不出来，请你帮他解决这个问题。作为回报，他会说服老师给你加分。
输入格式
输入包含多个测试用例。第一行包含测试用例的数量 ttt (1≤t≤1051 \leq t \leq 10^51≤t≤105)。每个测试用例的描述如下：
每个测试用例的第一行也是唯一一行包含三个整数 aaa、bbb、ccc (1≤a,b,c≤1001 \leq a, b, c \leq 1001≤a,b,c≤100) —— 分别表示数字 111、数字 222 和数字 333 的数量。
输出格式
对于每个测试用例，输出一行包含 333 个整数。
第一个整数为 111 表示可以通过操作使得最终只剩下数字 111，否则为 000。
第二个整数为 111 表示可以通过操作使得最终只剩下数字 222，否则为 000。
第三个整数为 111 表示可以通过操作使得最终只剩下数字 333，否则为 000。
样例输入
样例输出
样例解释
在第一个测试用例中，帅童可以擦除数字 222 和 333 并写下数字 111。这样黑板上就会有 222 个数字 111。通过类似操作，他也可以让黑板上只剩数字 222 或数字 333。
在第二个测试用例中，他可以擦除数字 111 和 333 并写下数字 222。执行两次这样的操作后，黑板上将只剩下数字 222。可以证明无法让黑板上只剩数字 111 或数字 333。
在第三个测试用例中，存在一系列操作可以让黑板上只剩数字 111。可以证明无法让黑板上只剩数字 222 或数字 333。
T2. 考前小游戏
明天才考试，因此帅童只能考前玩一款无聊的MMORPG游戏。游戏中有 nnn 个编号从 111 到 nnn 的任务，完成这些任务可以获得经验值。任务完成规则如下：
* 任务 111 总是可以直接完成
* 任务 iii (i>1i > 1i>1) 只有在所有编号比它小的任务都至少完成过一次后才能解锁
帅童可以重复完成同一个任务多次。每次完成任务获得的经验值为：
* 第一次完成任务 iii ：获得 aia_iai 点经验值
* 之后每次完成任务 iii ：获得 bib_ibi 点经验值
帅童最多只愿意完成 kkk 个任务。请你计算他最多能获得多少经验值。
输入格式
第一行包含整数 ttt (1≤t≤1041 \leq t \leq 10^41≤t≤104) —— 测试用例数量
每个测试用例包含：
1. 第一行两个整数 nnn 和 kkk (1≤n≤2⋅1051 \leq n \leq 2 \cdot 10^51≤n≤2⋅105; 1≤k≤2⋅1051 \leq k \leq 2 \cdot 10^51≤k≤2⋅105) —— 任务数量和最多可完成任务数
2. 第二行 nnn 个整数 a1,a2,…,ana_1, a_2, \ldots, a_na1 ,a2 ,…,an (1≤ai≤1031 \leq a_i \leq 10^31≤ai ≤103)
3. 第三行 nnn 个整数 b1,b2,…,bnb_1, b_2, \ldots, b_nb1 ,b2 ,…,bn (1≤bi≤1031 \leq b_i \leq 10^31≤bi ≤103)
保证所有测试用例的 nnn 之和不超过 2⋅1052 \cdot 10^52⋅105
输出格式
对于每个测试用例，输出一个整数表示可获得的最大经验值
样例输入
样例输出
样例解释
第一个测试用例：
* 最优任务顺序：1, 1, 2, 3, 2, 4, 4
* 获得经验：4+1+3+1+1+2+1=134 + 1 + 3 + 1 + 1 + 2 + 1 = 134+1+3+1+1+2+1=13
第二个测试用例：
* 最优任务顺序：1, 1
* 获得经验：1+3=41 + 3 = 41+3=4
第三个测试用例：
* 最优任务顺序：1, 2, 2, 2, 3
* 获得经验：3+2+3+3+4=153 + 2 + 3 + 3 + 4 = 153+2+3+3+4=15
T3. 走在中考的小路上
走在中考的小路上
帅童要从家出发前往考场。因为一些意义不明的原因，帅童竟然住在一棵二叉树上。而帅童的家就是这个二叉树的根节点。
这条路上有 nnn 个节点，编号从 1 开始，其中 1 号是帅童的家。每个节点都有以下特点：
* 可能可以往左走，到达左边的节点
* 可能可以往右走，到达右边的节点
帅童想要前往考场，他知道考场一定设置在树上的叶子结点（无法向左走和向右走的节点）
但是现在这棵树上正在施工，每个节点 iii 都有一个指示牌，指示牌上有一个字符。每个节点只能指示牌上标注的方向是可以走的。具体规则为：
* 字符 'U'：只能返回上一个节点
* 字符 'L'：只能向左走
* 字符 'R'：只能向右走
但是帅童非常有权力。因此，他可以提前修改任意路口的指示牌为任意字符。
请计算他最少需要修改多少个指示牌，才能确保从家出发一定能到达某个考场。
输入格式
第一行 ttt (1≤t≤5⋅1041 \leq t \leq 5 \cdot 10^41≤t≤5⋅104) —— 测试用例数量
每个测试用例：
第一行包含一个整数 nnn (2≤n≤3⋅1052 \leq n \leq 3 \cdot 10^52≤n≤3⋅105) —— 表示节点总数
第二行包含一个长度为 nnn 的字符串 sss —— 表示每个节点的指示牌上的字符。
接下来 nnn 行，每行两个整数 lil_ili 和 rir_iri $(0\leq l_i, r_i \leq n) $ — 第 iii 个点往左走和往右走可以到达的节点编号。如果 li=0l_i = 0li =0，表示节点 iii 无法向左走；如果 ri=0r_i = 0ri =0 表示节点 iii 无法向右走。
保证所有测试用例 nnn 之和不超过 3⋅1053 \cdot 10^53⋅105
输出格式
对于每个测试用例，输出一个整数表示最少需要修改的指示牌数量
样例输入
样例输出
样例解释
第一个测试用例：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. 突然出现了一条河
过河建桥问题
帅童在去考场的路上遇到了一条河，这条河可以看作一个 nnn 行 mmm 列的网格。每个格子 (i,j)(i,j)(i,j) 有一个深度值 ai,ja_{i,j}ai,j 。河的两岸（第一列和最后一列）的深度都是 0。
帅童可以在第 $i $ 行建造桥梁，但这需要建造一些桥墩，因此，需要花钱。具体规则如下：
1. 必须在行的起点 (i,1)(i,1)(i,1) 和终点 (i,m)(i,m)(i,m) 安装桥墩
2. 相邻桥墩之间的距离不能超过 ddd（距离定义为 ∣j1−j2∣−1|j_1-j_2|-1∣j1 −j2 ∣−1）
3. 在格子 (i,j)(i,j)(i,j) 安装桥墩的成本为 ai,j+1a_{i,j}+1ai,j +1
为了使得帅童能从桥上走过去，他需要选择连续的 kkk 行建造桥梁。即帅童需要选择一个 i(1≤i≤n−k+1)i(1\leq i \leq n - k + 1)i(1≤i≤n−k+1)， 然后分别独立地在第 i,i+1,…,i+k−1i, i+1, \dots,i + k - 1i,i+1,…,i+k−1 行建造桥梁。
帅童希望你帮他算一下建造 kkk 座连续的桥梁的最小总成本。
输入格式
第一行 ttt (1≤t≤1031 \leq t \leq 10^31≤t≤103) —— 测试用例数量
每个测试用例包含：
1. 第一行四个整数 n,m,k,d(1≤k≤n≤100,3≤m≤2⋅105,1≤d≤m)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≤k≤n≤100,3≤m≤2⋅105,1≤d≤m)：
* nnn：行数
* mmm：列数
* kkk：需要建造的连续桥梁数
* ddd：最大允许桥墩间距
2. 接下来 nnn 行，每行 mmm 个整数 ai,ja_{i,j}ai,j ，表示各格子深度
* 保证 ai,1=ai,m=0a_{i,1}=a_{i,m}=0ai,1 =ai,m =0
* 0≤ai,j≤1060 \leq a_{i,j} \leq 10^60≤ai,j ≤106
保证所有测试用例的 n⋅mn \cdot mn⋅m 之和不超过 2⋅1052 \cdot 10^52⋅105
输出格式
对于每个测试用例，输出一个整数表示最小总成本
样例输入
样例输出
样例解释
第一个测试用例：最优方案是在第二行建桥，总成本为4
注：图示说明（原Note中的描述）：
<img src="/Users/regen/Library/Application Support/typora-user-images/image-20250614015316712.png" alt="image-20250614015316712" style="zoom:50%;" />
灰色格子表示桥梁，白色格子为空，黑色格子为桥墩，蓝色格子为水，棕色格子为河底
第二个测试用例：最优方案是在第二和第三行建桥，桥墩分别安装在(2,3)和(3,2)等位置
第三个测试用例：最优方案是只在两岸安装桥墩
T5. 算了还是去玩吧
由于造桥实在是太麻烦了，帅童决定不去中考了。他打算在接下来的 nnn 个小时里和朋友一起玩。他想在这 nnn 个小时中分别尝试以下三个不同的活动，每个活动各玩一次：
* 滑雪
* 看电影
* 玩桌游
帅童知道，在第 iii 个小时：
* 有 aia_iai 个朋友愿意和他去滑雪
* 有 bib_ibi 个朋友愿意和他去看电影
* 有 cic_ici 个朋友愿意和他玩桌游
由于不能在一个小时内进行多个活动，请你帮帅童选择三个不同的小时 x,y,zx, y, zx,y,z，使得参与活动的朋友总数 (ax+by+cz)(a_x + b_y + c_z)(ax +by +cz ) 最大。
输入格式
第一行包含整数 ttt (1≤t≤1041 \leq t \leq 10^41≤t≤104) —— 测试用例数量
每个测试用例包含：
1. 第一行 nnn (3≤n≤1053 \leq n \leq 10^53≤n≤105) —— 总小时数
2. 第二行 nnn 个整数 a1,a2,…,ana_1, a_2, \ldots, a_na1 ,a2 ,…,an (1≤ai≤1081 \leq a_i \leq 10^81≤ai ≤108) —— 第 iii 小时可以滑雪的朋友数
3. 第三行 nnn 个整数 b1,b2,…,bnb_1, b_2, \ldots, b_nb1 ,b2 ,…,bn (1≤bi≤1081 \leq b_i \leq 10^81≤bi ≤108) —— 第 iii 小时可以电影的朋友数
4. 第四行 nnn 个整数 c1,c2,…,cnc_1, c_2, \ldots, c_nc1 ,c2 ,…,cn (1≤ci≤1081 \leq c_i \leq 10^81≤ci ≤108) —— 第 iii 小时可以玩桌游的朋友数
保证所有测试用例的 nnn 之和不超过 10510^5105
输出格式
对于每个测试用例，输出一个整数表示最多能参与活动的朋友总数
样例输入
样例输出
样例解释
第一个测试用例：帅童可以选择：第 222 小时滑雪（101010 人），第 111 小时看电影（101010 人），第 333 小时玩桌游（101010 人）。朋友总数为 10+10+10=3010 + 10 + 10 = 3010+10+10=30。
第二个测试用例：帅童可以选择：第 111 小时滑雪（303030 人），第 444 小时看电影（202020 人），第 222 小时玩桌游（252525 人）。朋友总数为 30+20+25=7530 + 20 + 25 = 7530+20+25=75。注意不能选择同一个小时进行多个活动。
第三个测试用例：帅童可以选择：第 222 小时滑雪（191919 人），第 333 小时看电影（191919 人），第 777 小时玩桌游（171717 人）。朋友总数为 19+19+17=5519 + 19 + 17 = 5519+19+17=55。
第四个测试用例：帅童可以选择：第 111 小时滑雪（171717 人），第 444 小时看电影（191919 人），第 999 小时玩桌游（202020 人）。朋友总数为 17+19+20=5617 + 19 + 20 = 5617+19+20=56。
T6. 竟然有补考？
帅童因为没学上了，被麻麻赶出来了。但是他在路上遇到了小牛王高级中学的招生主任，他遇到了一些问题。他答应帅童，如果能帮他解决这个问题，就可以给帅童补考的机会。他现在有一堆数字，他想让这些数字变得更加美丽，但是他不知道他需要如何更高效率地完成这件事。
招生主任有给定一个长度为 nnn 的整数数组 a1,a2,…,ana_1, a_2, \ldots, a_na1 ,a2 ,…,an 和一个整数 kkk。
在进行操作前，你可以随意重新排列数组元素。
每次操作可以选择一个元素，将其增加 kkk。
一个数组 bbb 被称为"美丽"的，当且仅当对于所有 1≤i≤n1 \leq i \leq n1≤i≤n，都满足 bi=bn−i+1b_i = b_{n-i+1}bi =bn−i+1 。
帅童需要用最少的操作次数使数组变得"美丽"，或判断这个数组这辈子都不可能美丽了。
输入格式
第一行 ttt (1≤t≤1041 \leq t \leq 10^41≤t≤104) —— 测试用例数量
每个测试用例包含：
1. 第一行两个整数 nnn 和 kkk (1≤n≤1051 \leq n \leq 10^51≤n≤105, 1≤k≤1091 \leq k \leq 10^91≤k≤109) —— 数组长度和每次可以增加的数字
2. 第二行 nnn 个整数 a1,a2,…,ana_1, a_2, \ldots, a_na1 ,a2 ,…,an (1≤ai≤1091 \leq a_i \leq 10^91≤ai ≤109) —— 数组元素
保证所有测试用例的 nnn 之和不超过 2⋅1052 \cdot 10^52⋅105
输出格式
对于每个测试用例，输出使数组美丽所需的最小操作次数，如果不可能则输出 -1。
样例输入
样例输出
样例解释
第一个测试用例：数组已经是美丽的，不需要操作。
第二个测试用例：可以随意重新排列数组后对原数组的第一个元素进行 83966524 次操作。
第三个测试用例：先重新排列数组使其等于 [2,3,1][2,3,1][2,3,1]。然后对第三个元素进行一次操作得到 [2,3,2][2,3,2][2,3,2]。
第八个测试用例：无论如何重排和操作都无法使数组美丽，开摆！。
第九个测试用例：数组已经是美丽的。
EX. 亿百昏！
补考智力测试题
帅童终于通过智力测试获得了补考机会。试卷上只有这一道题，帅童不想没学上，所以他来寻求了你的帮助。
对于一个数组 ccc 中的某个值 xxx，定义其距离 dx(c)d_x(c)dx (c) 为该值在数组中任意两次出现位置的最大间隔。具体来说：
* dx(c)=max(j−i)d_x(c) = \max(j - i)dx (c)=max(j−i)，其中 ci=cj=xc_i = c_j = xci =cj =x 且 i<ji < ji<j
* 如果 xxx 只出现一次或未出现，则 dx(c)=0d_x(c) = 0dx (c)=0
数组的美观度定义为所有不同值的距离之和：$\sum\limits_{1 \leq x \leq n} d_x(c) $
给定一个长度为 nnn 的数组 aaa，定义一个长度为 nnn 的数组 bbb 为"合格数组"当且仅当：对于所有 1≤i≤n1 \leq i \leq n1≤i≤n，满足 1≤bi≤ai1 \leq b_i \leq a_i1≤bi ≤ai 。
你需要找到在所有"合格数组"中，美观值最大的数组的美观值是多少。
输入格式
第一行 ttt (1≤t≤1041 \leq t \leq 10^41≤t≤104) —— 测试用例数量。
每个测试用例包含：
1. 第一行 nnn (1≤n≤2⋅1051 \leq n \leq 2 \cdot 10^51≤n≤2⋅105) —— 数组长度。
2. 第二行 nnn 个整数 a1,a2,…,ana_1, a_2, \ldots, a_na1 ,a2 ,…,an (1≤ai≤n1 \leq a_i \leq n1≤ai ≤n) —— 数组中的每个元素。
保证所有测试用例的 nnn 之和不超过 2⋅1052 \cdot 10^52⋅105
输出格式
对于每个测试用例，输出一个整数表示最大可能的美观度
样例输入
样例输出
样例解释
第一个测试用例：当 b=[1,2,1,2]b = [1,2,1,2]b=[1,2,1,2] 时，d1(b)=2d_1(b)=2d1 (b)=2，d2(b)=2d_2(b)=2d2 (b)=2，美观度为 444。可以证明这是最大可能值。
第二个测试用例：b=[1,1]b = [1,1]b=[1,1] 或 b=[2,2]b = [2,2]b=[2,2] 都能得到美观度 111。
第三个测试用例：当 b=[1,2,1,4,1,2,1,1,1,2]b = [1,2,1,4,1,2,1,1,1,2]b=[1,2,1,4,1,2,1,1,1,2] 时，d1(b)=9−1=8d_1(b)= 9 - 1 = 8d1 (b)=9−1=8，d2(b)=10−2=8,d4(b)=0d_2(b)= 10 - 2 = 8,d_4(b) = 0d2 (b)=10−2=8,d4 (b)=0，因此美观度为 161616。
