三月测试

x1007 · 2025-02-11 17:54:09 · 个人记录

T1

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

  正解

  是使用记忆化搜索。直接把算好的值记录下来，下次直接用。

  T2

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

  正解

  1. 对于每次的询问，枚举所有盔甲模拟过程判断其合法性直至找到合法盔甲。
  3. 设 res = 0，模拟（枚举）盔甲收到 K_{i,j} 的效果，其最小值的绝对值 +1 即为盔甲的最小生命值。二分查找合法的盔甲。

     T3

     正解

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

     T4

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

  正解

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