Voldemort's blog

Voldemort's blog

我好菜啊

题解 P4011 【孤岛营救问题】

posted on 2020-07-09 10:15:28 | under 题解 |

Solution

这道题目可以轻松地看出应该考虑宽搜算法来解决,其他题解中没有讲明白如何准确压位,所以本蒟蒻来讲一下。

什么是压位?

压位通俗的说就是把一个不可很难直接标记的状态变得更好标记。

如何压位?

以本题为例,题目当中钥匙可能有10种,按照我们之前的方法,需要开一个10维的布尔数组来进行标记,但这无疑为判重带来了巨大的麻烦。于是我们观察每把钥匙的状态,发现钥匙只有两种状态:有还是没有。于是考虑二进制。用一个10位二进制数来表示每一把钥匙的状态,如0000000000就表示目前你一把钥匙都没有,而0000001000就表示你有第4把钥匙,那我们如何实现呢?
首先你先确保你明白二进制的运算后再看下文。
假如我们现在一把钥匙都没有,来到了一个有第4把钥匙的风水宝地,我们就需要拿起这一把钥匙,使得二进制数0000000000变成0000001000,我们就只需要把数字1向左移动3个单位,下面画个图进行理解:

也就是说如果我们取了第 $q$ 把钥匙,我们需要把它压入状态只需要将它向左移动 $q-1$ 位,伪代码如下:

getk(q)
    x = 1 << (q-1)

那么如果说我们有多把钥匙呢?
那我们就考虑按位或,举个例子,如果你现在有了第三把钥匙,你又拿到了第四把,那么我们只需要把这两个二进制数按位或一下即可。
画个图:


哦对了,图上的那个xor是按位或,不是按位异或,打错了。

也就是说我们将两把钥匙合并只需要按位或一下即可,伪代码如下:

merge(q) 
    p |= q  //p是原来的钥匙状态,q是新来的。

那么我们现在解决了拿钥匙的问题,现在我们要解决判重的问题,怎么解决呢?
这次我们用按位与,举个例子,如果你现在有了第2,3,4,7,9把钥匙,而这扇门需要第八把钥匙,我们只需要把你手中有的钥匙的状态和第八把钥匙的状态按位与,如果结果为0,则没有这一把钥匙,否则就有这把钥匙,画个图:


但是你要注意,第 $p$ 把钥匙的状态时二进制数左移 $p-1$ 位的,不能搞错。

这道题目好像难的就是状态的压缩吧,其他你应该可以自己做出来的,代码就不放了。