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;
}
分类: 文章

0 条评论

发表评论

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