题意:给定 $a,b∈[1,10^9]$, 求 [a,b] 间有多少个数转换为二进制后 0 的个数比 1 多 (转换后二进制数最高位为 1)

思路:先来看几个栗子:如果求 [1xxxxx]2 有多少满足要求,那么答案 $ans=\sum\limits_{i=3}^{5}C\limits_{5}^{i}$, 因为只需在 xxxxx 中有 5 或 4 或 3 个 0 即可

那么对于任何一个二进制数,我们都可以这样求出比他小或者相等的二进制数有多少满足要求。1. 所有位数比他少的都可以。2. 与他同位的,对于他每一个是 1 的数位,这一位之前的数位不变,自己变为 0,之后的随便填,可以达到要求的可以。

对于第二类,这样讨论会补充不漏地得到所有可行数。

比如对于 1001011,属于第一类的数有:1xxxxx,1xxxx,1xxx,1xx,1x,1, 属于第二类的数有:1000xxx,100100x,1001011(←这个数就是本身,也要算进来) 然后再用例子中的组合数学方法求出有多少种填法。

#include <cstdio>
#include <cstring>
using namespace std;

int c[40][40];

void init()
{
    for(int i=0; i<=33; i++)c[i][0]=1;
    for(int i=1; i<=33; i++)
        for(int j=1; j<=i; j++)
            c[i][j]=c[i-1][j-1]+c[i-1][j];
}

int work(int x)
{
    int ans=0,one=1,len=0,s0=0;
    for(int i=31; i>=0; i--)
        if(x&(1<<i))
        {
            len=i+1;
            for(int j=2; j<len; j++)
                for(int k=0; k<=(j-2)/2; k++)
                    ans+=c[j-1][k];
            break;
        }
    for(int i=len-2; i>=0; i--)
        if(x&(1<<i))
        {
            for(int j=0; j<=len/2-one; j++)ans+=c[i][j];
            one++;
        }
    for(int i=0; i<=len-1; i++)if(!(x&(1<<i)))s0++;
    if(s0>=(len+1)/2&&x!=0&&x!=1)ans++;
    return ans;
}

int main()
{
    int a,b;
    init();
    scanf("%d%d",&a,&b);
    printf("%d\n",work(b)-work(a-1));
    return 0;
}

分类: 文章

0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注