题意:给定$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;
}


分享至ヾ(≧∇≦*)ゝ:
分类: 所有

发表评论

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

你是机器人吗? =。= *