6 月 6 日闲话

有些问题形如每一次变化一次数列，新数列与原数列相邻两项有关。这种一般考虑一下打表，多半能从中看出规律。

对连续的 $n$ 个数进行某种操作，有很好的性质：每次下标模 $n$ 相同的位置只会有一个被操作到，从这里切入会很方便。

然后我发现我打表这方面一直做的不是很好。总的来说有两个因素，一个是没有这个意识，另一个是没有思考过哪些东西可以打表。比如一些特殊形态矩阵的高斯消元，这个可以打表。还有一些转化后的模型，分析可能有点难，也可以尝试打表。比如今天考试的时候我采用了枚举字符串观察性质的这样的形式，但是没有观察变化的过程，就没有找到很有用的规律。可能还是浪费了一些时间在无用的思考上，如果能及时打个表分析也许能加速思考的过程。然后就是写暴力这件事，感觉今天还是做的挺不错，在刚 T2 之前及时把其他两题暴力写好了。不过最终 T2 挂分了，原因是有两种情况应该分别处理，其中一种情况我看答案差不多就以为是对的，其实如果用已经写好的 checker 检查一下就会发现其实寄了。这就损失了 20 分。但是考场上的检查还是做的比较好。最后抽了十多分钟来看代码有没有问题，最后发现自己输出方案的时候忘加一了。还有就是专门写了一个 checker 来检查还是挺对，虽然没用好这个 checker。但其实这个 checker 写的有点大胆了，忽略了自己线段树写挂的可能性，但事实证明我线段树写的还是可以。总之就是要做好暴力工作和检查工作阿！后面也要坚持。

另外今天做了一个很有意思的总结，虽然可能对做题没什么帮助，但感觉挺对的：

dp 的本质是合并同类状态。我们所说的无后效性其实是指若两个状态在后续情形中能被区分，他们就不能合并在一起。

这个的方法其实还挺多的，有些 dp 需要结合到贪心的思想在里面，比如两个状态有用的肯定是更小的那个这种。所以 dp 的这个压缩状态还是可以说带了一点点贪心在里面，不好说。

区间子区间问题还得是转二维平面然后扫描线。扫描线的过程中可能会用到吉老师树，比较常用的一般是 区间历史和 和 区间历史最小值个数。前者对应的是啥我不知道，后者对应的是区间询问未被矩形包含的数的数量。这种东西一般最需要考虑的是标记的传递顺序。历史最小值个数可能还好说一点，区间历史和一定要搞清楚加法标记和时间标记的覆盖顺序，不要忘记 pushdown 了。