数位统计DP

· · 算法·理论

返回母本《动态规划》

1.数位DP入门

数位统计是指对数字数据进行数位上各个数字的统计，基于动态规划的核心思想，数位统计DP可以很大程度上优化数位统计。

数位DP的一般形式是，要求在某个区间具有某种性质的数的个数，并且这种性质的DP考虑可以按照数位以树的形式展开。

例题1

乍一看，这道题并不算DP，因为它的题设太简单，一个统计有什么好DP的？

越简单的题，越有其精妙所在，本题的DP难点是分类讨论（在动态规划理论中，就是状态计算）。

这暂且不提，现在，我们要用最原始的思想去做这道题，忘掉学过的一切。

统计类题型，有一种很好的找优化的方法——随心模拟。

给你一串从 1 到 20 有序数列，来找找 1 出现了几次：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

我们发现， 1 出现了 12 次。我们是怎么得来的呢？数出来的。

现在延长到 100 ：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 ……

相信聪明的你一定会得到答案—— 21 次。

你当然不会把所有数字写出来一个一个看，但是你知道，假如每十个数为一个区域，从 1 到 10 ，从 11 到 20 ，从 21 到 30 ，……一共十个区域，他们的个位上的数是不相同的，所以， 1 在个位上会出现 10 次。

你还知道，在 1 到 100 中，十位上为 1 的只有 10~19 ，所以 1 在十位上只会出现 10 次。

然而 100 是唯一一个百位上有 1 的数字。

所以总共 10+10+1=21 （次）。

回味这个过程，我们从三个角度考虑了数字 1 的出现次数——个位、十位、百位，所以考虑任何数，从数位的角度考虑，会不会是一种高效的方法？

利用 n 从数位的角度考虑某个数 x 的出现次数。

不慌，这个问题放一放，现在我想知道从 21~100 中，1 出现了几次？

借助上面的结论，可以得到答案： 21-12=9 （次）。

思路逐渐清晰，前缀和。

重拾上面的问题，现在我想知道从 1 到数 abcdefg 中 1 出现的次数。

那我们会考虑各个数位上 1 的出现次数，再求他们的和，即得答案。

现在来考虑第四数位上 1 的出现次数，设考虑的数为 xxx1yyy，从 xxx 与 abc 、 yyy 与 efg 、1 与 d 的大小关系考虑：

可得，在第四数位上 1 的出现次数为 1000\times (abc)+\begin{cases}1000&d>1\\dfg+1&d=1\\0&d<1\end{cases} 。

还要考虑细节，当统计最高数位和最低数位时，要舍弃部分情况；考虑 0 时，同样要舍弃部分情况。

（思考的空间）

……
……
……
……
……
……

回顾整个过程，我们设count(i,j)表示从 1 到 i 中数字 j 出现的个数，count(i,j) 的计算如上述。

其实确实没有多少DP的影子，前缀和的使用也不明显。

笔者认为这是道大模拟。有没有可能数位DP都是模拟

那么，

Theory is feasible, practice begins.

注意！上述思路只是一个大方向，并不能作为模板

请务必仔细看代码，很多细节是需要在编码过程中通过调试发现的

代码：

#include<bits/stdc++.h>
using namespace std;

int gt(int x){
    int res=1;
    while(x--)  res*=10;
    return res;
}//由于在数位处理时总是要取n的某位数，为了方便%/，写了此函数

int count(int n,int x){
    if(n==0)    return 0;//从1到0没有任何数字
    //a-1是有可能使n为0的

    int res=n,nu=0,d;
    while(res){
        res/=10;
        nu++;
    }
    res=0;
    //借用res得到n 的位数

    //当查到最高数位
    if(x!=0){
        d=n/gt(nu-1);//最高数位的数字
        if(d==x){//相等，只能去efg+1
            res+=n%gt(nu-1)+1;
        }else if(d>x){//大于，都可以取，1000
            res+=gt(nu-1);
        }//小于，无解
    }//若x=0，则没必要查最高位数，那是前导0

    //以下代指的xxx与x不是同一个东西，xxx指的是上述例子中的xxx；x是指当前函数的x

    //当查到最低数位
    res+=n/gt(1);//此时xxx=000~abc-1，最低位相同

    d=n%10;//此时xxx=abc，分对应位置数字与x的大小分类讨论
    if(nu>1 && d>=x && x!=0)    res++;
    //前提是x不为0；当nu=0时，由于只有一位，所以会在最高最低数位算两遍
    //无论 d>x 还是 d=x，由于是最低位，所以只有一个

    //注意一个问题：你会发现，当x=0时，上述的“查最低数位”是不严谨的
    //但由于在xxx=000~abc-1时多算一个，在xxx=abc时少算了一个，这不影响答案正确性

    for(int i=2;i<nu;i++){//开始常规操作
        //xxx=000~abc-1
        if(x!=0)    res+=n/gt(i)*gt(i-1);
        else    res+=(n/gt(i)-1)*gt(i-1);
        //xxx=abc
        d=n%gt(i)/gt(i-1);
        if(d==x){
            res+=n%gt(i-1)+1;
        }else if(d>x){
            res+=gt(i-1);
        }
    }
    return res;
}

int main(){
    while(1){
        int a,b;
        scanf("%d%d",&a,&b);
        if(a!=0 && b!=0){
            if(a>b) swap(a,b);
            for(int i=0;i<=9;i++)
                printf("%d ",count(b,i)-count(a-1,i));
            puts("");
        }else{
            break;
        }
    }
    return 0;
}

由于笔者是个蒟蒻，只能写上述的复杂难记代码，在实际应用中，相信下面两种好记的代码模板会有更大帮助。

模板

2.数位DP一般通解

由上述可知，数位DP一般需要用到两个技巧：

  1. 按数位树形分类讨论
  2. 按照类似前缀和的思想使得区间 [l,r] 的答案为 f(r)-f(l-1)

以例题1为例，实际上上述题解思路可以看作下面的树形分析：

当然，在这例题1中，是每个数位上一棵小树。

例题2

求给定区间 [X,Y] 中满足下列条件的整数个数：这个数恰好等于 K 个互不相等的 B 的整数次幂之和。

例如，设 X=15,Y=20,K=2,B=2，则有且仅有下列三个数满足题意：

17=2^4+2^0 18=2^4+2^1 20=2^4+2^2

第一行包含两个整数 X 和 Y，接下来两行包含整数 K 和 B。

只包含一个整数，表示满足条件的数的个数。

1≤X≤Y≤2^{31}−1,1≤K≤20,2≤B≤10 
15 20
2
2
3

考虑 B 进制表示，即在 1~n 中，有多少个数的 B 进制表示上只由 K 个 1 和多个 0 组成。

其树形考虑如下

返回母本《动态规划》