Amount of Degrees


题意:给你两个数X,Y(X<=Y<2^31-1),以及k,b,求所有的i∈[X,Y]的数目,i在b进制下只由b个1和若干个0组成。注意有多组数据。

如X=15,Y=20,k=2,b=2,则会有:

17 = 24+20,
18 = 24+21,
20 = 24+22.

所以答案为3


分析:由于X,Y的范围较大,且数据组数较多,所以我们应该考虑有没有复杂度在logn级别的算法。

先来看看朴素算法:我们可以枚举每一个由k个1组成的b进制数,由于X最多有logbX位,每一位可以选择取0或者1,所以我们可以做到O(2logbX)左右的复杂度。但是当b比较小,如2或者3时,这种算法的弊端就显露出来了:我们对于每一位放1还是0都做了很多次判断。

所以我们想到了用动态规划。

先考虑二进制的1情况:如果用f[i][j]表示i位二进制数中出现j个1的数的数量,则f[i][j]=f[i-1][j]+f[i-1][j-1],分别为第i位放0和放1的状态转移。所以我们可以很轻松地预处理出f数组,f数组只需要有32*32个元素即可满足题目的数据要求。接着对于X每一位为1的,ans加上对应的f的值。过程大概是这样的:

比如对于二进制数100110,求小于他的有2个1的数的个数
如果左数第一位为0,则ans+=f[5][2]
如果第一位为1,那么继续讨论1xxxxx
->如果第二位为0(第二位只能为0)那么继续讨论10xxxx
->->如果第三位为0(第三位只能为0)那么继续讨论100xxx
->->->如果第四位为0,由于现在在讨论1000xx,所以xx中只需要有1个x为1,100xx都可以构成与之前讨论得出的答案不同的答案,所以ans+=f[2][1]
->->->如果第四位为1,那么继续讨论1001xx,
->->->->如果第5位为0,那么ans+=f[1][0],
->->->->由于第5不可以为1(为1的话就是10011x,永远无法满足题意),所以直接略过,至此ans为所求。

代码大概是这样的:

ll work()
{
    int tot=0,one=0;
    for(int i=MX-1;i>=0;i--)            //从高位向低位推进
    {
        if(num[i+1])                            //num即为处理中的数
        {
            tot+=f[i][k-one],one++; //one是已经出现了几个1
            if(one>k)break;                 //如果已经出现了k个以上的1,不用继续累加了
        }
        if(i==0&&k==one)tot++;  //如果num自己就是一个满足要求的数,则tot自加
    }
    return tot;

由于本人第一次打数位Dp,代码又臭又长,已自裱千遍

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

#define MX 32
typedef long long ll;

using namespace std;

long long k,b;
int f[MX+1][MX+1], num[MX+1];

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

ll work()
{
    int tot=0,one=0;
    for(int i=MX-1;i>=0;i--)
    {
        if(num[i+1])
        {
            //cout<<i<<" "<<k-one<<endl;
            tot+=f[i][k-one],one++;
            if(one>k)break;
        }
        if(i==0&&k==one)tot++;
    }
    return tot;
}

void convert(ll x)
{
    ll tot=0;
    memset(num,0,sizeof(num));
    for(int i=1;i<=MX;i++)num[i]=x%b,x/=b;
    for(int i=MX;i>=1;i--)if(num[i]>=2)for(int j=i;j>=1;j--)num[j]=1;
}

int main()
{
    ll x,y;
    init();
    while(~scanf("%lld%lld%lld%lld",&x,&y,&k,&b))
    {
        int ans1,ans2;
        convert(x-1);
        ans1=work();
        convert(y);
        ans2=work();
        cout<<ans2-ans1<<endl;
    }
    return 0;
}
分类: 所有

发表评论

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

你是机器人吗? =。= *