当前位置: 代码迷 >> 综合 >> AOJ 2539 Counting 1's
  详细解决方案

AOJ 2539 Counting 1's

热度:37   发布时间:2024-01-12 05:17:25.0


Aizu 2539

题意:询问是否存在区间[A,B],使得[A,B]之间,从后往前二进制第i位为1的数个数为k[i]。(1<=A,B<=1e18)

要求判断无解,多解或者确定唯一解。


非常有趣的思想题,我们设区间大小W=B-A+1,注意到k[0],也就是最后一位二进制可以将W的范围约束住。

一共有三种情况:

W=2*k[0]-1

W=2*k[0]

W=2*k[0]+1

所以我们分别对三种W进行判断即可。

如何计算:从最高位开始往低位走,显然对于确定的W,k[i]有四种可能性:

k[i]=0

k[i]=W

0<k[i]<W

k[i]>W

第一种情况,在[A,B]之间没有任何数第i位为1,所以显然A,B在这一位上都是0。

第二种情况,所有[A,B]之间的数都是1,所以A,B在这一位上都是1。

第三种情况,表示了A在这一位上是0,而B在这一位上是1。

第四种情况,情况不合法。


现在我们单独讨论第三种情况:

假设当前

A=0b0001010