题解 密码锁

题面

解析

这题确实有些难度。。

首先，暴力做法，就直接二分+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就行了。

看代码吧：

最后上全篇代码：

题解 密码锁

原文：https://www.cnblogs.com/zsq259/p/10503663.html