首页 > 其他 > 详细

题解 密码锁

时间:2019-03-09 23:53:46      阅读:105      评论:0      收藏:0      [点我收藏+]

标签:get   记录   如果   位置   注意   https   代码   开关   解析   

 

题面

解析

这题确实有些难度。。

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

看代码吧:

 

 

 

最后上全篇代码:

题解 密码锁

标签:get   记录   如果   位置   注意   https   代码   开关   解析   

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

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号