首页 > 代码库 > [您有新的未分配科技点]数位dp：从懵X到板子

[您有新的未分配科技点]数位dp：从懵X到板子

2024-10-23 19:46:39   209人阅读

数位dp主要用来处理一系列需要数数的问题，一般套路为“求[l,r]区间内满足要求的数/数位的个数”

要求五花八门……比如“不出现某个数字序列”，“某种数的出现次数”等等……

面对这种数数题，暴力的想法是枚举每个数，判断是否满足条件

比如这样：

#include<cstdio>
using namespace std;
typedef long long LL;
LL l,r,cnt; 
int main()
{
    scanf("%lld%lld",&l,&r);
    for(LL i=l;i<=r;i++)
        if(/*i符合条件*/)cnt++;
    printf("%lld",cnt);
}

这样很显然会T......所以我们考虑利用一些奇怪的性质来数数（一般这些性质可以用来递推、或是dp一样的转移）

比如看下面一道例题：

对于给定闭区间[L,R]，求非0数位出现的个数

sample input：23 233

sample output： 515

首先转化为calc[1~R]-calc[1~L-1](我们设数字的最低位为第1位，次低为位第2位，以此类推)

做法1：专门统计数位的方法：我们先预处理bin[i]为10的i次方,再预处理dp[i]表示在i位数的范围内（1~99...999(i个9））某种数字的个数

那么考虑dp[i]和dp[i-1]之间的转移:

首先，第i位的数字为0~9时都可以对第i位数字的dp值产生dp[i-1]的贡献

也即:[0~10...(i-1个0)...0)的末i-1位贡献+[10...(i-1个0)...0~20...(i-1个0)...0)的末i-1位贡献+……+[90...(i-1个0)...0~10...0(i个0))的末i-1位贡献

接着，后面i-1位为任意数是都会给第i位的数字产生+1的贡献,由排列组合知总共有bin[i-1]的贡献

所以转移是dp[i]=10*dp[i-1]+bin[i-1]（其实化简一下式子，也可以写成dp[i]=i*bin[i-1]）

有了这个dp数组我们考虑如何计算对于某个数字x计算[1~x]某个数位st的出现个数，这个过程和之前递推的过程很相似

我们枚举x的第i位位bit

1° bit>st 第i位取0~bit时都可以增加dp[i-1]的贡献，而0~bit里肯定会有这一位取st的情况，贡献加上bin[i-1]

因此ans+=bin[b-1]+d*dp[b-1];

2° bit==st 设tail=x%bin[i-1]（x的前i-1位数的值）第i位取0~bit时都可以增加dp[i-1]的贡献，但是当第i位取st（bit）时，只有tail+1种数比x小，因此贡献只有tail+1

此时ans+=tail+1+d*dp[b-1];

3°bit<st 第i位取0~bit时都可以增加dp[i-1]的贡献，但0~bit取不到st

所以ans+=d*dp[b-1];

但是在统计完答案之后，如果我们统计的st==0，前导0被多统计了（第i位不能取0，因此多加了bin[0]+bin[1]+...+bin[数的位数-1]），在最后减去即可

代码见下：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<cmath>
 5 using namespace std;
 6 typedef long long LL;
 7 typedef unsigned long long ULL;
 8 LL l,r,bin[20],dp[20];
 9 inline void intn()
10 {    
11     bin[0]=1;//bin[i]是10的j次方 
12     for(int i=1;i<=18;i++)
13         bin[i]=bin[i-1]*10,dp[i]=dp[i-1]*10+bin[i-1];
14             //第i位是0~9的时候，都会有+dp[i-1]的新贡献
15             //而后面i-1位任一情况时都会给第i位的数字贡献+1，一共有bin[i-1]种情况 
16 }
17 inline LL calc(LL sum,int state)
18 {
19     LL tmp=sum;
20     int b=0,d;LL ans=0;//tail是末几位的数字大小 
21     while(sum)
22     {
23         d=sum%10;sum/=10,b++;
24         if(d>state)ans+=bin[b-1]+d*dp[b-1];
25         //对本位(指第i位)有bin[b-1]（末i-1位随意选择）的贡献，第i位是0~d的时候都会有贡献 
26         else if(d==state)ans+=(tmp%bin[b-1])+1+d*dp[b-1];
27         //本位的贡献仅限于末位的数字大小+1（全0也会提供贡献） 
28         else ans+=d*dp[b-1];//本位没有贡献 
29     }
30     d=0;
31     if(state==0)
32     //前导0被重复计算了，一位数多算了一个0，两位数多算了10个零，如此我们减去多算的就好了   
33         while(tmp)  
34             ans-=bin[d++],tmp/=10;  
35     return ans; 
36 }
37 inline LL work(LL data)
38 {
39     LL ans=0;
40     for(int i=1;i<=9;i++)
41         ans+=calc(data,i);
42     return ans;
43 }
44 int main()
45 {
46     scanf("%lld%lld",&l,&r);
47     intn();
48     LL ansr=work(r);
49     if(l==0)printf("%lld",ansr);
50     else printf("%lld",ansr-work(l-1));
51 }

做法2：正经（？）dp法

我们设f[i][j]为x的前i位数并且第i位数为j时j的出现次数,依然预处理bin[i]同上

那么类别上面的做法

首先f[i][j]+=Σ(f[i-1][k],0<=k<=9)；接着，如果j不是0，我们在加上第i位对这个数的贡献bin[i-1]（其实就实现了上面统计时最后消去前导0的过程）

要注意的一点是[0~10...(i-1个0)...0)等都是一个左闭右开区间，如果计算work（R）-work（L-1)，就无法统计R的贡献

因此我们计算时也使用左闭右开区间，计算work（R+1）-work（L）就好啦

代码见下：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
LL l,r,bin[20];
LL f[30][15];//f[i][j]表示前i位，第i位数字为j的j出现次数 
int bit[20];
inline void intn()
{
    bin[0]=1;//bin[i]是10的j次方 
    for(int i=1;i<=18;i++)
        bin[i]=bin[i-1]*10;
    for(int i=1;i<=18;i++)
        for(int j=0;j<10;j++)
        {
            for(int k=0;k<10;k++)
                f[i][j]+=f[i-1][k];            
            f[i][j]+=(j==0)?0:bin[i-1];
        }
}
inline LL work(LL x){
    int cnt=0,b=0;while(x)bit[++b]=x%10,x/=10;//bit表示每一位 
    LL ans=0;
    for(int i=b;i;i--)
    {
        for(int j=0;j<bit[i];j++)
             ans+=f[i][j];//第i位是0~bit[i]-1的情况 
        ans+=bin[i-1]*bit[i]*cnt;//第i位是bit[i]的情况 
        //这里的cnt记录了“第i位以前（第i+1位到最高位）有多少个数不是0”，因为他们也算是非0数位。 
        if(bit[i])cnt++;
    }
    return ans;
}
int main()
{
    scanf("%lld%lld",&l,&r);
    intn();
    LL ansr=work(r+1);
    if(l==0)printf("%lld",ansr);
    else printf("%lld",ansr-work(l));
}

下面我们再来一道例题:[HDU2089]不要62

不要62

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Problem Description
杭州人称那些傻乎乎粘嗒嗒的人为62（音：laoer）。杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别的士司机和乘客的心理障碍，更安全地服务大众。不吉利的数字为所有含有4或62的号码。例如：62315 73418 88914都属于不吉利号码。但是，61152虽然含有6和2，但不是62连号，所以不属于不吉利数字之列。
你的任务是，对于每次给出的一个牌照区间号，推断出交管局今次又要实际上给多少辆新的士车上牌照了。
Input
输入的都是整数对n、m（0<n≤m<1000000），如果遇到都是0的整数对，则输入结束。
Output
对于每个整数对，输出一个不含有不吉利数字的统计个数，该数值占一行位置。
Sample Input
1 100 0 0
Sample Output
80
 
题解：
我们依然定义f[i][j]数组，为前i位数第i位为j时的合法数的数量
初始化时f[0][0]=1;
那么显然当且仅当j!=4&&!(j==6&&k==2)时，能有转移f[i][j]+=f[i-1][k];
统计答案时，我们还是从高位向低位统计，当我们枚举的数位j满足j!=4&&!(x的第i+1位==6&&j==2)时可以统计答案。
需要注意的是：如果我们发现原数中的某一处出现了62或者4，我们直接结束统计，因为在高位相等的前提下更低的位数一定不合法了。
代码见下：
 1 #include<cstdio>
 2 #include<cstring>
 3 using namespace std;
 4 typedef long long LL;
 5 int l,r,bit[15],f[10][15];
 6 inline void intn()
 7 {
 8     f[0][0]=1;
 9     for(int i=1;i<=8;i++)
10         for(int j=0;j<10;j++)
11         {
12             if(j==4)continue;
13             for(int k=0;k<10;k++)
14             {
15                 if(j==6&&k==2)continue;
16                 f[i][j]+=f[i-1][k];
17             }
18         }
19 }
20 inline int work(int x)
21 {
22     memset(bit,0,sizeof(bit));
23     int b=0,cnt=0,ans=0;
24     while(x)bit[++b]=x%10,x/=10;
25     for(int i=b;i;i--)
26     {
27         for(int j=0;j<bit[i];j++)
28         {
29             if(j==4||(bit[i+1]==6&&j==2))continue;
30             ans+=f[i][j];
31         }
32         if(bit[i]==4||(bit[i+1]==6&&bit[i]==2))break;
33     }
34     return ans;
35 }
36 int main()
37 {
38     intn();
39     while(scanf("%d%d",&l,&r)==2)
40     {
41         if(l==r&&r==0)break;
42         printf("%d\n",work(r+1)-work(l));
43     }
44 }
45

 

 

[您有新的未分配科技点]数位dp：从懵X到板子


联系
我们