T1

100%

题目中的过滤条件是字符串长度严格大于阈值，因此判断 $|s|>k$ 即可。

• 若 $|s|>k$，输出 Yes；
• 否则输出 No。

注意长度恰好等于 $k$ 时不会被过滤。

时间复杂度为 $O(|s|)$。

T2

100%

枚举被移动的位置 $i$。删除 $s_i$ 后，将它接到剩余字符串末尾，得到一个候选字符串；再扫描候选字符串，统计满足相邻两个字符相同的位置数量，并取所有候选方案的最大值。

题目要求恰好操作一次，但选择原串最后一个字符时字符串不变，所以原串的得分也自然包含在枚举范围内。$n=1$ 时唯一方案的得分为 $0$。

时间复杂度为 $O(n^2)$。

T3

100%

坐标值域只有 $0$ 到 $1000$，可以直接枚举完整的移动方案。

依次枚举：

1. 被移动的点 $i$，其中 $2\le i\le n-1$；
2. 新坐标 $x$，其中 $a_1<x<a_n$。

如果 $x$ 等于任意一个原坐标，则该方案不符合题意，直接跳过。否则删去 $a_i$、加入 $x$，将所有点重新排序，并检查每一对相邻点的距离是否都不超过 $k$。检查通过时答案加一。

枚举恰好覆盖所有允许的二元组 $(i,x)$，检查条件与题目对合法移动的是一样的。

记坐标跨度为 $V=a_n-a_1$。时间复杂度为 $O(n^2V\log n)$。

T4

100%

考虑记忆化搜索。

鱼在某一位置、朝向某一方向时，下一碗白饭并不需要选择：如果该射线上还有白饭，它一定会吃掉距离最近的一碗；真正的选择只发生在吃完以后，即左转或右转。

用二进制集合 $mask$ 表示已经被吃掉的白饭，并进行深度优先搜索。搜索状态还记录鱼的当前位置以及当前朝向。处理一个状态时：

1. 扫描所有不在 $mask$ 中的白饭，找出当前方向射线上距离最近的一碗 $j$；
2. 如果不存在这样的白饭，本条路线结束；
3. 否则吃掉 $j$，将它加入 $mask$，并分别递归搜索左转、右转两种后继状态；
4. 两种后继取最大值，再加上当前吃掉的这一碗。

当前坐标只可能是初始位置或最后吃掉的白饭位置，因此可以用一个编号表示。也可以对 $(mask,pos,dir)$ 记忆化；即使不记忆化，每吃一碗以后也只有两个转向分支，搜索树的结点数仍为 $O(2^n)$。

每个状态用 $O(n)$ 时间寻找最近的白饭，所以时间复杂度为 $O(n2^n)$。不记忆化时递归栈空间为 $O(n)$；使用记忆化时空间复杂度为 $O(2^n)$ 个实际到达的状态。

注意实现的时候判断“在前方”需要同时检查共线和方向符号，例如朝上要求 $x_j=x$ 且 $y_j>y$；白饭被吃掉后必须先转向，不能保持原方向。

T5

40%

当所有测试用例中的 $\sum n\le 200$ 时，可以枚举三根木棒，检查其长度能否组成三角形，并用三根木棒的最大、最小强度更新答案。

时间复杂度为 $O(n^3)$。

100%

将木棒按照强度从小到大排序。这样，选中木棒的最大强度与最小强度之差，就是它们所在强度区间的宽度。问题转化为：寻找宽度最小的连续强度区间，使其中至少存在三根长度能够组成三角形的木棒。

对于一个长度多重集合，将长度排序为

$$x_1\le x_2\le\cdots\le x_m.$$

集合中存在三根木棒能够组成三角形，当且仅当存在某个 $i$ 满足

$$x_i+x_{i+1}>x_{i+2}.$$

充分性显然。对于必要性，若 $x_a,x_b,x_c$（$a<b<c$）能够组成三角形，则 $x_{c-2}\ge x_a$、$x_{c-1}\ge x_b$，所以 $x_{c-2}+x_{c-1}>x_c$，必然也存在一组三个连续长度满足条件。

下面给出两种做法。

方法一

二分最小不稳定度。对于一个给定的强度差上限，按照强度顺序使用滑动窗口，维护所有强度差不超过该上限的木棒，并判断窗口内是否存在合法三角形。

窗口中的长度存入一个 multiset 中。加入一根新木棒时，原有长度之间的相邻关系基本不变，只有新长度附近的连续三元组可能新满足三角形不等式，因此只需检查新长度及其前后邻近位置。若某个窗口中出现合法三角形，则当前强度差上限可行。

可行性具有单调性：一个强度差上限可行时，更大的上限也一定可行。因此可以二分得到最小可行值。若所有可能的强度差都不可行，则输出 $-1$。

每次判定中，每根木棒至多加入、删除一次，时间复杂度为 $O(n\log n)$。总时间复杂度为 $O(n\log n\log 10^9)$。

方法二

也可以直接使用双指针寻找最短的可行强度区间。固定区间左端后，不断扩大右端，直到区间中第一次出现合法三角形；此时用当前区间宽度更新答案，然后删除最左侧的木棒并继续。右端点始终不回退。

判断一个窗口是否合法时，将其中所有长度按升序取出，扫描连续三元组，判断是否存在

$$x_i+x_{i+1}>x_{i+2}.$$

这种做法看似会反复扫描较大的窗口，但长度上界 $10^9$ 保证了窗口实际上并不大。设一个不含三角形的窗口中，排序后的长度为

$$x_1\le x_2\le\cdots\le x_m.$$

因为不存在合法的连续三元组，所以对所有 $i$ 都有

$$x_{i+2}\ge x_i+x_{i+1}.$$

又因为 $x_1,x_2\ge1$，所以 $x_i$ 至少按照斐波那契数列增长。取 $F_1=F_2=1$，有 $x_i\ge F_i$，而

$$F_{45}=1134903170>10^9.$$

因此不含三角形的窗口最多只有 $44$ 根木棒。双指针每次刚找到三角形时，只比前一个不合法窗口多加入一根木棒，所以需要扫描的窗口至多约有 $45$ 个元素。

每根木棒至多加入、删除一次，有序集合操作的总时间复杂度为 $O(n\log n)$；每次合法性判断只需扫描常数级数量的元素。因此总时间复杂度为 $O(n\log n)$，空间复杂度为 $O(n)$。

T6

30%

当 $n\le 2000$ 时，对每个阈值 $t$ 独立模拟一遍栈即可。

时间复杂度为 $O(n^2)$，空间复杂度为 $O(n)$。

20%（特殊性质 A）

当 $p_i=i$ 时，前 $t$ 个数依次入栈，后面的 $n-t$ 个数依次弹栈。最终留下前 $\max(0,2t-n)$ 个数，答案为

$$\frac{q(q+1)}2,\qquad q=\max(0,2t-n).$$

所有阈值可以在 $O(n)$ 时间内求出。

100%

把“小于等于阈值”看作一次入栈，把“大于阈值”看作一次弹栈。一次入栈与之后第一次能够删除它的弹栈相匹配，最终栈中留下的就是所有没有被匹配的入栈元素。

考虑将阈值从 $n$ 逐步减小到 $1$。阈值为 $n$ 时，排列中的所有数都会入栈，因此最终栈中包含全部元素，答案为

$$1+2+\cdots+n=\frac{n(n+1)}2.$$

当阈值从 $t$ 减小到 $t-1$ 时，只有数值 $t$ 对应的操作发生变化：它原本是入栈，现在变成弹栈。设这个数在排列中的位置为 $x$，根据它在原匹配关系中的状态分两种情况。

1. 如果位置 $x$ 原本最终留在栈中，那么先删除 $x$。它变成弹栈后，还会删除 $x$ 左侧距离最近的一个剩余入栈元素。
2. 如果位置 $x$ 原本已经被右侧某次弹栈删除，那么改变操作后，原来的匹配关系会向左移动两次：新出现的弹栈会删除一个更早的剩余元素，原先与 $x$ 匹配的弹栈也会继续删除下一个更早的剩余元素。因此需要删除 $x$ 左侧距离最近的两个剩余入栈元素。

如果左侧剩余元素不足，需要删除多少个就删除多少个。

上述变化可以从栈匹配关系理解。弹栈总是与左侧最近的未匹配入栈配对。将一个入栈改成弹栈后，右侧其余操作的相对顺序没有变化，受影响的匹配只会沿着栈顶向左传递。因此，除上述至多两个位置外，其余最终留下的元素完全不变。

用 set 维护当前最终留在栈中的所有位置，同时维护这些位置对应数值之和。每次降低阈值时：

• 先判断发生变化的位置当前是否仍在集合中；
• 按照上述两种情况，删除它本身以及它左侧最近的一个或两个位置；
• 删除完成后的数值和，就是新阈值对应的答案。

时间复杂度为 $O(n\log n)$。