题面 https://www.luogu.org/problemnew/show/U64804
解析
这题确实有些难度..
首先, 暴力做法, 就直接二分 + bfs,
然而, 时间, 空间都会炸掉!!!.
因此, 考虑优化.
step 1
首先, 我们可以用差分的思想,
设最终达到的状态是全部为零.
那么初始时 k 个需要打开的开关就设为 1,
因为锁的取反也可以表示为加 1 后模 2,
所以用 a[i]记录第 i 个锁异或第 i-1 个锁的状态,
这样, 对于一个区间 [l,r], 我们只需要修改 a[l] 和 a[r+1]就行了.
关于前面处理的代码:
step 2
之前我们已经讲到了, 能用差分记录状态,
并且实际上,
因为只修改 l 和 r+1,
所以就相当于 l 的状态向右移了 (r-l+1) 位(题目中就是 size[i]),
那么, 如果 l 和 r+1 都是 0 的话, 就没必要修改了.
而且, 如果状态 1 右移后的位置的状态也是 1,
那么这两个 1 就会被消掉.
比如说, 当前状态为:
1 1 1 0 1 1 1 1 1 0,
则差分后的数组为:
1 0 0 1 1 0 0 0 0 1 0 (注意, 差分要记录到 n+1).
那么, 如果我们把区间 [1,3] 取反,
则状态为:
0 0 0 0 1 1 1 1 1 0
差分数组就为:
0 0 0 0 1 0 0 0 0 1 0,
因此, 问题转化为, 用最少的步数消掉所有的 1.
所以, 首先我们可以用 bfs 求出每个 1 到其他各个 1 的最少步数,
具体看代码:
step 3
最后, 我们就要求消掉所有点的最少步数了!
注意, 费用流在这里似乎不行(因为有无解的情况)
但是, 我们还可以用 DP,
因为 k<=10, 所以最多有 20 个 1,
因此从(1<<cnt)-1 开始步数,
递归求解消掉其中两个点的状态的最小步数,
当状态为 0 时, 就返回 0 就行了.
看代码吧:
最后上全篇代码:
来源: http://www.bubuko.com/infodetail-2982147.html