A

大部分同学都是用 py 过的，这里提供一个 c++的简单思路

我们先把所有 排序，这一步可以用 int128 直接相乘实现， 对于相等的，我们只保留周长最小的那一个

现在我们从小到大遍历每一个 ，找到第一个大于 的,显然最优借就是他或者他前面一个数

直接和 比较显然是不行的, 考虑到分母最大只有 , 因此我们取 的前 20 位看为

上下同时乘 将分子变为整数,这样就可以和排序时一样比较

现在只用考虑 和 哪个和 更接近

把三个分数通分, 最大为

用三个 int128 压下位即可 (口胡做法, 还没测试过

当然也可以直接高精度

B

简单模拟

C

手玩一下即可发现规律

D

我们先把连续相等的段变为一个数, 现在新数组 b 满足,

假如我们跨数操作使前面的一个数变 0 , 那么一定会出现这样一种状态:

因为操作的左边界只会越来越左,因此 ^ 的值不会改变, 即二者必定有一个不为 0

因此对于 b 中的每个元素,我们只能单独使他为 0

答案就是 b的长度减去其中 0 的个数

E

线段树求区间子段和板子题

F

发现操作完后, 最大值仅 2e6

因此预处理从 0 开始增加到 2e6 的答案

每个询问相当于前缀和减一下

G

暴力

枚举一下其中一个数的数量, 另外两个数是多少都时可以确定的

H

简单 dp

维护到每一个位置, 生命值为 h 的最小次数即可

每个位置只会向右向下更新答案, 总复杂度

I

简单图论

只有两种策略

​ 1.只走状态为 1 的边, 走到 n

​ 2.先通过状态为 1 的边到 k, 在通过所有边到 n

先在只有 1 的边的图上跑一次最短路, 再把 0 的边加入再跑一次即可

J

简单模拟

K

一个数往前最多能吃的数量就是一个贪心的 LIS, 即往前比他小的数直接吃掉然后变成这个数, 舍弃比他大的数

往后同理

对于往前和往后, 我们可以用一种左右横跳的方式,把前后的都吃掉--- 哪边大就先把哪边吃了

对于贪心的LIS, 可以 的用单调数据结构维护, 也可以用树状数组, 每次把他前面比他大的数都删除,一个数只会被加入一次,删除一次, 因此复杂度为

L

简单模拟

每个字符串都很小, 用一堆map模拟即可

M

定义 为人在 箱子在 的最小移动次数

我们不需要维护 种情况, 只要存储 30 * 30 * 4种

即对于每一个箱子的位置, 人分别在他上下左右四个位置的答案, 把每一个状态看成一个点,类似最短路更新即可

每次更新相当于箱子移动一格,枚举人可能的所有位置, 即30 * 30

总复杂度为