三月测试

T1

• 考时思路：直接用递推实现，结果会造成大量重复计算超时

正解

T2

• 考时想法：直接暴力枚举

正解

1. 对于每次的询问，枚举所有盔甲模拟过程判断其合法性直至找到合法盔甲。
2. $K_{i,j}$ 的效果均为整数，从而不会对盔甲造成损害，每次一定会选取生命值最小的盔甲。枚举得到最小生命值的盔甲。
3. 设 $res = 0$，模拟（枚举）盔甲收到 $K_{i,j}$ 的效果，其最小值的绝对值 +1 即为盔甲的最小生命值。二分查找合法的盔甲。

T3

正解

1. 暴力：对于每次询问，对以每个片区为中心双向枚举判断得到最大的合法的基础E值，通过计算后累加得到答案即可。
2. 特殊性质：S仅包含0
3. 性质：连续相同字符子串的基础E值一定为先递增后递减。
4. 对于不同连续子串按长度奇偶性分类讨论构造出原串的基础E值数组。
5. 前缀和预处理即可。

T4

• 考时思路：进行暴力枚举，但是没做出来。

正解

1. 暴力：枚举出所有区间和，排序后输出答案即可。
2. 等价于寻找一个数值等于所有的子区间的区间和，从小到大排序后的第 $K$ 个数值。
3. 该过程可以二分，判断时使用双指针优化至 $O(n)$ 。