主题

主题

 
   

关于超级小的数字的背包

给出多次询问,每一个询问给出x,x<=1e9,求x的所有位上的数字是否可以凑成一个sum。

我们可以背包,然后复杂度可以变为O(sumlgx)。

然后常数炒鸡大。

我们可以采用一种位运算的方法。由于我们只需要知道能不能凑成sum,所以我们可以采用一个进制数的状压思想:

我们把一个数字v,视为2的v次幂。比方说如果v=3,那么在状态中他就是2^3。

我们用一个数字con来记录状态。对于每一个数字v,相当于con可以往右边移动v位。那么新的con就是原来的con|移动后的con。

最后我们只需要判断是con&1<<sum为0还是1即可。

代码如下:

https://code.csdn.net/snippets/2217553

理论复杂度没有变化很多,但是位运算在的地方自然炒鸡快。

 
 
评论