三月测试
T1
- 考时思路:直接用递推实现,结果会造成大量重复计算超时
正解
是使用记忆化搜索。直接把算好的值记录下来,下次直接用。
T2
- 考时想法:直接暴力枚举
正解
- 对于每次的询问,枚举所有盔甲模拟过程判断其合法性直至找到合法盔甲。
-
- 设
res = 0 ,模拟(枚举)盔甲收到K_{i,j} 的效果,其最小值的绝对值 +1 即为盔甲的最小生命值。二分查找合法的盔甲。T3
正解
- 暴力:对于每次询问,对以每个片区为中心双向枚举判断得到最大的合法的基础E值,通过计算后累加得到答案即可。
- 特殊性质:S仅包含0
- 性质:连续相同字符子串的基础E值一定为先递增后递减。
- 对于不同连续子串按长度奇偶性分类讨论构造出原串的基础E值数组。
- 前缀和预处理即可。
T4
- 考时思路:进行暴力枚举,但是没做出来。
正解
- 暴力:枚举出所有区间和,排序后输出答案即可。
- 等价于寻找一个数值等于所有的子区间的区间和,从小到大排序后的第
K 个数值。 - 该过程可以二分,判断时使用双指针优化至
O(n) 。