常用技巧精选(1)三题 POJ3061 POJ3320 POJ3276

POJ 3061 (追逐法)

这题先由二分法引出, 然后给出追逐法(尺取法). 符合追逐法是因为在该题中, 对于区间[s, t]来说如果t向前移动, 那么满足条件的新区间[s’, t’] 必然有在 s <= s’ 的时候的解.

 

POJ 3320 (追逐法 + 数据结构)

这题是追逐法的扩展版, 处理的数据不是一个个的int, 而是总共有几个不同的知识点以及每个知识点读了多少次, 因此用上set和map就可以轻松解决问题.

 

POJ 3276 (开关问题)

开关问题有两个性质

  1. 交换翻转的顺序对结果是没有影响的;
  2. 对同一个翻转单位进行两次以上的翻转是多余的

因此问题常常可以转化为求需要进行翻转的单位的集合. 集合中的单位只翻转一次, 其余单位不翻转.

对于本题来说, 第一头牛是切入点. 因为通过第一头牛的状态可以立即得出第一个区间是否需要翻转. 当第一个区间是否需要翻转确定下来的时候, 那么第二个区间就可以通过同样的方式(不用再考虑第一头牛)进行判断是否需要翻转. 由数学归纳知这样求就是对的.

然后如果直接用模拟的方法来翻转和查是否翻转的话, 会超时, 所以用了一个数组来加速, 类似前缀和数组之类的.

这道题WA了半天, 原因在于数组加速的地方, 边界总是搞错. 我最心烦边界搞错了, 看都不想再看一眼..