BOZJ1833详细题解

逃离我推掉我的手 2022-10-02 12:56 79阅读 0赞

# BOZJ1833详细题解 #

## 1.题目 ##

[BOZJ1833][]

## Description ##

给定两个正整数a和b，求在\[a,b\]中的所有整数中，每个数码(digit)各出现了多少次。

## Input ##

输入文件中仅包含一行两个整数a、b，含义如上所述。

## Output ##

输出文件中包含一行10个整数，分别表示0-9在\[a,b\]中出现了多少次。

## Sample Input ##

1 99

## Sample Output ##

9 20 20 20 20 20 20 20 20 20

说是一道典型的数位dp的问题．首先我们解决什么是数位dp的问题．现在有一个题目，就是要求你求出\[l,r\]区间内满足一定条件的数的个数，这时我们很容易想到暴力求解的方案，但是一旦数据范围过大这种方法就行不通了，这个时候就用数位dp来解决，把数位拆成一个一个的进位，然后逐一比较看是否满足题目要求．

那么针对这个问题，如何求解呢．

首先我们要做的事情是找到从0-r所含0-9的个数，再用它减去0-l-1的0-9的个数．因为题目要求我们求得是\[l,r\]必须包括l,这样相减得到的区间恰为\[l,r\]．那么现在我们需要求解的问题是一样的即求某个数ｘ，从\[0-x\]中所含0-9的个数．

我们用f\[i\]\[j\]\[k\]来表示长度为i，首位为j，所含k的个数为多少．那么f\[i\]\[j\]\[k\]是要等于f\[i-1\]\[0-9\]\[k\],注意我们所要求的是长度为i,首位为j，所含k的个数是多少．举个例子的话就是求200-299所含k的个数是多少．我们抛开首位来看的话，首先我们是不是就要求出00-99所含k的个数是多少再往下推，得到我们需要的递推式．

f\[i\]\[j\]\[k\] = f\[i\]\[j\]\[k\] + f\[i-1\]\[j\]\[k\]，这里我们是枚举了从00-99对于之后的首位，从200-299出现100次，所以首位出现的次数就是10i次方，我们再加上即可，此时j == k

那么初始化的函数为

public static void gen() {
        
            pow[1] = 1L;
            for (int i = 2; i < 14; i++) {
        
                pow[i] = pow[i - 1] * 10;
            }//算10^i
            //14是因为题目给的范围就只有那么大
            for (int j = 0; j < 10; j++) {
        
                f[1][j][j] = 1L;
            }
            for (int i = 2; i < 14; i++) {
        
                for (int j = 0; j < 10; j++) {
        
                    for (int k = 0; k < 10; k++) {
        
                        for (int in = 0; in < 10; in++) {
        
                            f[i][j][k] += f[i - 1][in][k];
                        }
                        if (j == k) {
        
                            f[i][j][k] += pow[i];
                        }
                    }
                }
            }
        }

现在我们开始找\[0-l-1\]的值了

首先我们要求出l-1的长度s

接着由于是从\[0-l-1\]所以我们首先要求的就是长度从1-s-1首位从\[1-9\]的各个位置的和注意此时没有０

举个例子的话就是我们现在求０-475，我们先求0-99的各个位置的和，之后我们再求100-199 200-299 300-399的各个位置的和，此时我们想要接着求400－475的值对吧？这个时候我们考虑每一位的情况，前面的4需要出现76次对吧，这里是不用计算的，接着是考虑400 - 409 410-419 420-429 430-439 440-449 450-459 460-469注意此时我们枚举的首位开始出现0,在考虑下一位的话跟之前考虑的一样7会出现6次 ．76 = 475%100+1 6 = 473%10+1

代码的理解的话，建议参照上面的解释，自己也是理解了好长一段时间

public static void solve(Long s,int lam){
        
            if(s == 0){
        
                ans[0] += lam;
                return;
            }
            long os = s;
            Long[] dat = new Long[14];
            int len = 0;
            while (s > 0){
        //求出s的位数
                dat[++len] = s%10;
                s /= 10;
            }
            for (int i = 1;i < len;i++){
        
                for(int j = 0;j < 10;j++){
        
                    for(int k = 1;k < 10;k++){
        
                        ans[j] += f[i][k][j] * lam;//得到少一位之前的所有数的和
                    }
                }
            }
            for(int i = len;i > 0;i--){
        //如上面所说的400-409部分
                for(int j = 0;j < dat[i];j++){
        
                    if(i == len && j ==0){
        
                        continue;
                    }
                    for(int k = 0;k < 10;k++){
        
                        ans[k] += f[i][j][k] * lam;
                    }
                }
                int t = dat[i].intValue();
                ans[t] += (long)(((os % pow[i]) + 1) * lam);
            }
        }

希望对你能够有所帮助?

[BOZJ1833]: https://www.lydsy.com/JudgeOnline/problem.php?id=1833