炼石计划
- T1:https://www.cnblogs.com/yanbinmu/articles/19122547
- T2:https://www.cnblogs.com/yanbinmu/articles/19122718
D3 作业
A. 关于整除分块
B. 题解:ABC192F Potion
最开始的想法遍历 k 判断可行,然后再想办法把时间求出来。
判断可行是很简单的,我们只需要满足 \(\sum_{i=1}^k a_{e_i} \equiv x \pmod k\)。
这个是好算的,我们做一个模 k 的可行性 01 背包。
然后去向如何找那个加起来的时间,发现可以将这个时间放到 dp 值里面存着,维护模 k 是 j 的最大加和就做完了。
C.Vanya and Treasure
显然的,我们按照开箱子的顺序,记录 \(f_{x, y, p}\) 表示我开某一个 p 类型的箱子后,我站在 \((x, y)\) 上。
这个的转移是我去枚举我下一个类型的箱子开哪个。
然后这个东西发现他的转移会被卡到 \(O(nm)\) 就烂掉了。
我们考虑一个经典的东西,我们看到这种曼哈顿距离可以考虑四个象限来想,分别维护四个象限的前缀最小值。
这个东西用二维前缀和维护不了,但是我们可以扫描线或者二位树状数组来做,注意初始化的手法,不要忘记抹去最开始写的一些东西。
D.ABC134F Permutation Oddness
简单说说题面,问你 \(a\) 是一个长度为 \(n\) 的排列, 问有多少个怪异值,即 \(\sum_{i=1}^{n} |i - a_i| = k\) 的 \(a\)。
对于这种绝对值形式的东西,我们可以考虑拆贡献,其中 \(i\) 或者 \(a_i\) 是较小的时,那么贡献是 -1,否则是 +1。
那么这就是将 \(i\) 与 \(a_i\) 配对。
考虑一个朴素的 DP,\(\displaystyle f_{i, x, y, k}\) 是遍历到第 i 对,前面有 x 个下标没配对,y 个值没配对,已经有 k 个贡献的方案数。
显然的,如果我确定一个值或者下标是向后或向前匹配了,那么他对怪异值的贡献就确定了。
然后我们推导转移时可以发现,如果互相指,那么都不变,而后分析,如果两个都向前或都向后,那么 x,y 均加一或减一,如果一个向前一个向后,x,y 是不变的。
这样 x 和 y 的值就是一样的,我们可以将状态砍掉一维。
转移就很好推了。