dustland

dustball in dustland

动态规划-数位DP

Posted on

数位DP

P2602 数字计数

给定正整数a,b,求\([a,b]\)所有的整数中,0到9每个数码各自总共出现多少次

由前缀和的思想,设\(sum[n]\)表示\([0,n]\)中0到9各个数码各自出现了多少次

那么\(sum[b]-sum[a-1]\)就是所求值

问题转化为如何求\(sum[n]\)即\([0,n]\)中0到9各个数码各自出现了多少次

设计状态\(dp[i]\)表示"当范围涵盖了完整的i位时,前i位中每个数字出现的次数."

啥意思呢?

比如对于\([1000,1999]\)显然能够找出i=1的完整区间,比如\([1000,1009]\)等等

显然也能够找出i=2的完整区间,比如\([1900,1999]\)等等

显然也能够找出i=3的完整区间,比如\([1000,1999]\),只有这一个

找不出i=4的完整区间了

如果对于[10,2000000],这就可以找到i=4的完整区间,也就是低四位能够遍历[0,9999]这个范围的区间,比如

\([10000,19999]\)

这样设计dp有一个隐患就是,忽略了前导0的区别.比如给定区间[0,999],显然最大可以找到i=3的区间[0,999]

但是正常情况下,0不能作为前导,也就是说不能有012或001或000或020这种数字,可以有210或100这种数字

最后再考虑去除前导零的情况,现在先不考虑

状态转移方程为: \[ dp[i]=10\times dp[i-1]+10^{i-1} \] 如何考虑这个方程呢?排列组合问题

第i位假设放了一个X(先不管到底放了啥),考虑他对低i-1位的影响,

X有0,1,2,...,9十种可能,于是之前计算得到的dp[i-1]就得乘以10,

也就是说,1在低i-1上出现过\(10\times dp[i-1]\)次

okk,现在看低i-1位给第i位造成的影响,第i位假如放一个1,低i-1位随便放有\(10^{i-1}\)种放法

因此1就在第i位上出现过\(10^{i-1}\)次

举个实际例子,以[0,999]为例,前导零的情况也计算在内

\(dp[1]=1\),边界条件,意思是区间为[0,9]的时候,一个数字显然只出现一次

\(dp[2]=10\times dp[1]+10^{1}=20\)

假设个位上放一个X,十位有十种可能,0X,1X,2X,3X,...,9X,也就是说,十位对个位计数的贡献就是\(10\times dp[1]\)

假设十位上放一个X,个位有十种可能,X0,X1,X2,X3,...,X9.也就是说,个位对十位计数的贡献就是\(10^{1}\)

笑死,只有两位,要不你影响我,要不我影响你,怎么贡献方式还不一样?

再多一位就可以体现了

\(dp[3]=10\times dp[2]+10^{2}=300\)

这时候发现貌似不容易计算百位对于前两位的贡献了,如何解释\(10\times dp[2]\)怎么来的呢?

可以这样想:

原来在计算\(dp[2]\)时,这样只有一个[0,99]区间,而考虑了百位之后,就有

\([0,99],[100,199],[200,299],...,[900,999]\)这10个区间了,每个区间内数字的出现个数都是\(dp[2]\)现在有十个相同区间,因此当有三位的时候,从前两位计算得到的数字出现个数就是\(10\times dp[2]\)

假设百位上放一个X,前两位稍微一动就是一个新数,X就得多记录一次

比如X23,X24,X25,这样百位上的X就记了3次.那么前两位一共有多少种可能的排列呢?\(10^2\)那么X在第三位上出现的次数就是\(10^2\)

然后考虑如何去除前导0

去除前导零,也就是给0的计数中去掉0出现在最高位的情况

去除前导0,只会对0的计数有影响,对其他数字没有影响,因为

012345去除前导0不是说把012345给去掉,而是保留12345,12345这五个数字各自统计一次,0此时不应计数

要去除i=6上的前导零计数,也就是去除

0XXXXX这种情况对0计数的贡献,显然有\(10^5\)种

去除i=5上的前导零计数,也就是去除

0XXXX这种情况对0计数的贡献,显然有\(10^4\)种

也就是去除第i位上的前导0影响,就是去除\(10^{i-1}\)次0的计数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn=15;
long long dp[maxn];
long long pow_10[maxn];

vector<long long> solve(long long n){
    long long temp=n;
    int length=0;
    int top[maxn];
    vector<long long> result(10);
    while(n){
        top[++length]=n%10;
        n/=10;
    }
    for(int i=length;i>=1;--i){
        for(int j=0;j<10;++j){
            result[j]+=dp[i-1]*top[i];
        }
        for(int j=0;j<top[i];++j){
            result[j]+=pow_10[i-1];
        }
        temp-=pow_10[i-1]*top[i];
        result[top[i]]+=temp+1;
        result[0]-=pow_10[i-1];
    }
    return result;
}
long long l,r;
int main(){
    cin>>l>>r;
    pow_10[0]=1;
    for(int i=1;i<maxn;++i){
        dp[i]=dp[i-1]*10+pow_10[i-1];
        pow_10[i]=10*pow_10[i-1];
    }
    vector<long long>left=solve(l-1);
    vector<long long>right=solve(r);
    for(int i=0;i<=9;++i){
        cout<<right[i]-left[i]<<" ";
    }
    return 0;
}

其中比较抽象的是后面这个循环,他里面都干了什么呢?

1
for(auto j=0;j<10;++j)result[j]+=dp[i-1]*top[i];

计算当前位i随便安排时,对前i位中,数位统计的贡献

使用\(top[i]\)因为第i位上只有\([0,top[i]-1]\)共\(top[i]\)种情况

为什么不是\([0,top[i]]\)共\(top[i]+1\)种情况?假如对于\([0,6524]\)

当前i=4,top[4]=6,可以找到区间[0,999],[1000,1999]

[2000,2999],[3000,3999],[4000,4999],[5000,5999]

共6个=top[4]

没有包括[6000,6999],因为最大到6524,即top[i]作为最高位时前i位找不出完整的区间来

1
for(auto j=0;j<top[i];++j)result[j]+=pow(10,i-1);

计算前i位随便安排时,对第i位数位统计的贡献

由于最高位上只可能出现\([0,top[i]-1]\),再高top[i]没有完全区间,再高\(top[i]+1\)不可能出现,因此不能统计对\([top[i],9]\)这些数字的贡献

比如当n=6524

i=6,也就是说存在1XXX,2XXX,3XXX,4XXX,5XXX这些完整区间(XXX表示[0,999])

6XXX没有完全区间,只有[6000,6524]

更不存在7XXX了

1
2
3
       
temp-=pow(10,i-1)*top[i];//去掉最高位
result[top[i]]+=temp+1;//之前统计贡献时,i位的最高数字总是不满区间,现在单独处理

啥意思呢?还是n=6524举例子

temp=n=6524

然后temp=6524-6000=524

这524就是对top[4]=6统计次数的贡献,也就是6在i=4位上出现了524+1=525次

加一的原因是,524表示[0,524]共525种情况

1
result[0]-=pow(10,i-1);//去除前导零

前导零有多种情况,比如0524,0024,0004,0000

这里每次只会处理一种情况,i=4时只会消除0999,0998,...,0000这种前导0.

P8764 二进位问题

\([1,n]\)这些整数中,二进制表示有k个1的有多少个

如果问题变成:m个二进制位,其中有k个1的有多少个数

显然是\(C_m^k\)

假设n表示成二进制形式之后,最高位是\(bit[len]=1\),最低位是\(bit[1]\)

显然前\(len-1\)位所有状态都包含在内了,因此首先有\(C_{len-1}^k\),也就是最高位位0时,低\(len-1\)位任意安排

下面考虑最高位为1的情况,

从次高位\(bit[len-1]\)往低位bit[1]方向看

如果\(bit[i]\)为0则跳过,否则加上\(C_{i-1}^{k-t}\)

其中t表示\([i+1,len]\)这些位上的1个数

比如\(n=101000,len=6\)

i bit[i] 操作
5 0 跳过
4 1 \(+C_{4-1}^{k-1}\)

为啥加上这个数呢?第4位上有一个1,这表明存在

\([100000b,100111b]\),低三位存在完整区间,从这个完整区间中统计有\(k-1\)个1的数,是因为之前已经有一个1了,需要在剩下的位中找出k-1个1即可

现在的主要问题是如何快速求解\(C_m^k\)

\(C_m^0=1\)

\(C_m^k=C_{m-1}^{k-1}+C_{m-1}^k\)

用\(c[m][k]\)数组预处理即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
//c[m][k]
const int maxm=100;
const int maxk=100;
long long c[maxm][maxk];


void init(){
    // c[1][0]=c[1][1]=1;
    c[0][0]=1;
    for(int i=1;i<maxm;i++){
        c[i][0]=1;
        for(int j=1;j<i;++j){
            c[i][j]=c[i-1][j-1]+c[i-1][j];
        }
        c[i][i]=1;
    }
}
void print(){
    for(int i=1;i<20;i++){
        for(int j=0;j<=i;j++){
            cout<<c[i][j]<<" ";
        }
        cout<<endl;
    }
}

long long n;
int k;
long long bit[maxm];
long long len;

int main(){
    init();
    cin>>n>>k;
    long long temp=n;
    while(temp){
        bit[++len]=temp&1;
        temp>>=1;
    }
    long long result=0;
    result+=c[len-1][k];
    int t=1;
    for(int i=len-1;i>=1;--i){
        if(bit[i]==0){
            continue;
        }
        if(k-t<0)break;
        result+=c[i-1][k-t];
        ++t;

    }
    cout<<result<<endl;

    return 0;
}

P2657 windy数

定义windy数:相邻两个十进制位必须至少差2,比如135,2597等等

给定区间[l,r]求这之间的windy数有多少

问题转化为[1,n]中的windy数有多少

设计状态: \[ dp[i][j]表示i个10进制位,最高位第i位上是j的windy数的个数 \] 边界条件显然是只有一位的时候,\(dp[1][j]=1\)

转移方程: \[ dp[i][j]=\sum_{|k-j|\ge2}dp[i-1][k] \]

下面考虑[1,n]中有多少windy数

首先划分成十进位

dec[len],dec[len-1],...,dec[1],最高位是dec[len]

那么显然有低len-1位的完整区间,全算上

第len位上,从1到dec[len]-1这些dp[len][i]也是都有的

只剩下len位上放dec[len]的情况了,这是最贴近上边界的情况,如何考虑?

i从len-1往1遍历

对于当前位i,尝试放置\(0\le j<dec[i]\),因为第i位最高可以为dec[i],比他小的数都存在

然后判断j是否合法,依据就是j和dec[i+1]距离是否大于等于2,

如果是,则加上\(dp[i][j]\)

这样第i位就统计完毕,尝试往更低位统计,第i位最终放置的是dec[i]

如果dec[i+1]和dec[i]相差小于2,就不能继续往低位统计了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
const int maxn=20;
long long dp[maxn][10];
void init(){
    for(int j=0;j<10;++j){
        dp[1][j]=1;
    }
    for(int i=2;i<maxn;i++){
        for(int j=0;j<10;++j){
            for(int k=0;k<10;k++){
                if(abs(j-k)>=2){
                    dp[i][j]+=dp[i-1][k];
                }
            }
        }
    }
}
long long solve(int n){
    if(n==0){
        return 0;
    }
    long long result=0;
    long long temp=n;
    long long dec[maxn];
    memset(dec,0,sizeof(dec));
    int len=0;
    while(temp){
        dec[++len]=temp%10;
        temp/=10;
    }
    // cout<<"actived"<<endl;
    for(int i=1;i<=len-1;++i){
        for(int j=1;j<=9;++j){
            result+=dp[i][j];
        }
    }
    for(int j=1;j<dec[len];++j){
        result+=dp[len][j];
    }
    for(int i=len-1;i>=1;--i){
        // cout<<"in loop"<<endl;
        for(int j=0;j<=dec[i]-1;++j){
            if(abs(j-dec[i+1])>=2){
                result+=dp[i][j];
            }
        }
        if(abs(dec[i]-dec[i+1])<2){
            break;
        }
    }



    return result;
}


int l,r;

int main(){
    cin>>l>>r;
    init();
    // cout<<solve(r+1)<<endl<<solve(l)<<endl;
    cout<<solve(r)-solve(l-1)<<endl;


    return 0;
}

P4999 烦人的数学作业

给定区间[l,r],求每个数各个十进制位的数字和

比如[123,125],就有1+2+3+1+2+4+1+2+5

首先问题转化为[1,n]区间上拆分数字和P1836 数页码

然后问题还可以转化为P2602求每个数字出现的次数

最终累计i×i的出现次数即可