题解 P4011 【孤岛营救问题】

# Solution 这道题目可以轻松地看出应该考虑宽搜算法来解决，其他题解中没有讲明白如何准确压位，所以本蒟蒻来讲一下。 ### 什么是压位？ 压位通俗的说就是把一个**不可**或**很难**直接标记的状态变得更好标记。 ### 如何压位？ 以本题为例，题目当中钥匙可能有10种，按照我们之前的方法，需要开一个10维的布尔数组来进行标记，但这无疑为判重带来了巨大的麻烦。于是我们观察每把钥匙的状态，发现钥匙只有两种状态：有还是没有。于是考虑二进制。用一个10位二进制数来表示每一把钥匙的状态，如``0000000000``就表示目前你一把钥匙都没有，而``0000001000``就表示你有第4把钥匙，那我们如何实现呢？ 首先你先确保你明白二进制的运算后再看下文。 假如我们现在一把钥匙都没有，来到了一个有第4把钥匙的~~风水宝地~~，我们就需要拿起这一把钥匙，使得二进制数``0000000000``变成``0000001000``，我们就只需要把数字``1``向左移动``3``个单位，下面画个图进行理解：  也就是说如果我们取了第 $q$ 把钥匙，我们需要把它压入状态只需要将它向左移动 $q-1$ 位，伪代码如下： ```cpp getk(q) x = 1 << (q-1) ``` 那么如果说我们有多把钥匙呢？ 那我们就考虑**按位或**，举个例子，如果你现在有了第三把钥匙，你又拿到了第四把，那么我们只需要把这两个二进制数按位或一下即可。 画个图：  哦对了，图上的那个**xor是按位或，不是按位异或**，打错了。 也就是说我们将两把钥匙合并只需要按位或一下即可，伪代码如下： ```cpp merge(q) p |= q //p是原来的钥匙状态，q是新来的。 ``` 那么我们现在解决了拿钥匙的问题，现在我们要解决判重的问题，怎么解决呢？ 这次我们用**按位与**，举个例子，如果你现在有了第2,3,4,7,9把钥匙，而这扇门需要第八把钥匙，我们只需要把你手中有的钥匙的状态和第八把钥匙的状态按位与，如果结果为0，则没有这一把钥匙，否则就有这把钥匙，画个图：   但是你要注意，第 $p$ 把钥匙的状态时二进制数左移 $p-1$ 位的，不能搞错。 这道题目好像难的就是状态的压缩吧，其他你应该可以自己做出来的，代码就不放了。