题目描述
给定两个整数 $a$ 和 $b$，求 $a$ 和 $b$ 之间的所有数字中0~9的出现次数。
例如，$a$=1024，$b$=1032，则 $a$ 和 $b$ 之间共有9个数如下：
1024 1025 1026 1027 1028 1029 1030 1031 1032
其中‘0’出现10次，‘1’出现10次，‘2’出现7次，‘3’出现3次等等…
输入格式
输入包含多组测试数据。
每组测试数据占一行，包含两个整数 $a$ 和 $b$。
当读入一行为0 0时，表示输入终止，且该行不作处理。
输出格式
每组数据输出一个结果，每个结果占一行。
每个结果包含十个用空格隔开的数字，第一个数字表示‘0’出现的次数，第二个数字表示‘1’出现的次数，以此类推。
数据范围
$0<a,b<100000000$
样例
输入样例：
1 10
44 497
346 542
1199 1748
1496 1403
1004 503
1714 190
1317 854
1976 494
1001 1960
0 0
输出样例：
1 2 1 1 1 1 1 1 1 1
85 185 185 185 190 96 96 96 95 93
40 40 40 93 136 82 40 40 40 40
115 666 215 215 214 205 205 154 105 106
16 113 19 20 114 20 20 19 19 16
107 105 100 101 101 197 200 200 200 200
413 1133 503 503 503 502 502 417 402 412
196 512 186 104 87 93 97 97 142 196
398 1375 398 398 405 499 499 495 488 471
294 1256 296 296 296 296 287 286 286 247
算法1
(基础课代码)
关键在与分类讨论
对于这个问题，我们枚举0-9的每个数字在哪一位来分类讨论，这里拿2来写一下，数字为abcdefg，计算2在第4位的所有的种类
首先要明确的一点是无论我们的2在哪一位，它所构成的那个数字一定是要在[1,abcdefg]之间的
第一种情况 形如xxx2xxx，如果2前面的xxx是小于abc的，那么2后面的xxx只要是000-999就都可以，这就对应了abc*1000种情况
第二种情况 形如xxx2xxx，如果2前面的xxx恰好为abc，那么此时又要分类讨论了
①如果d<2 那么此时情况数位0
②如果d=2 那么此时2后面的xxx只要在000-edg就可以了，有edg+1种情况
③如果d>2 那么此时2后面的xxx只要在000-999就可以，有1000种情况
这里要考虑一个特殊的值0，首先最高位不能是0，其次如果0出现在某一位，这里拿第4位说，对于第一种情况，0前面的xxx就只能从001-abc，因为如果还有000，此时的这个0就相当于没有，所以对于0，它的第一种情况的方案数为(abc-1)*1000
时间复杂度
这种做法的时间复杂度为$O(n ^ 2)$,n为数字的位数
参考文献
算法基础课
java代码
import java.io.*;
import java.util.*;
class Main{
static int get(List<Integer> list, int l, int r){
int res = 0;
for(int i=l; i>=r; i--){
res = res * 10 + list.get(i);
}
return res;
}
static int power10(int x){
int res = 1;
while(x!=0){
res *= 10;
x--;
}
return res;
}
//统计从1-n，x出现的次数
static int count(int n, int x){
if(n==0) return 0; //如果n为0，那直接返回0就行了
List<Integer> l = new ArrayList<Integer>();
//将n的每一位加入到l中
while(n!=0){
l.add(n % 10);
n /= 10;
}
int len = l.size();
//对于0,不需要枚举最高位
int res = 0;
for(int i=len-1-(x==0?1:0); i>=0; i--){
if(i < len-1){
res += get(l, len-1, i+1) * power10(i);
if(x == 0) res -= power10(i);
}
if(l.get(i) > x) res += power10(i);
else if(l.get(i) == x) res += get(l, i-1, 0) + 1;
}
return res;
}
public static void main(String[] args) throws IOException{
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String[] arr = in.readLine().split(" ");
int a = Integer.parseInt(arr[0]);
int b = Integer.parseInt(arr[1]);
while(a!=0 || b!=0){
if(a > b){
int tmp = a;
a = b;
b = tmp;
}
//枚举每一个数字
for(int i=0; i<=9; i++){
System.out.print(count(b, i)-count(a-1, i)+" ");
}
System.out.println();
String[] cur = in.readLine().split(" ");
a = Integer.parseInt(cur[0]);
b = Integer.parseInt(cur[1]);
}
}
}
算法2
(提高课yxc数位dp分析法)
这道题的分析树为:
这里要预处理出来左子树的值，首先一个很明显的状态表示为f[i, j, x]表示i位且最高位为j，数字x出现的次数，具体的分析如下：
在上图的分析中我们可以看出，在求f函数之前，还要求一个g函数,其中g[i][j]表示i位，且最高位为j的所有数字的个数，状态转移方程为g[i][j] += g[i-1][k] (k = [0, 9])，至此，对于左子树的预处理操作就做完了。
对于数位DP部分，首先如果当前数字为0，直接返回0，因为0不在该题讨论的范围内，之后我们使用一个last记录当前数位之前出现num数字的个数，这里我们以正在填第三位，求1出现的次数为例：
最后还要注意的一点是这个问题是不可以有前导0的存在的，所以在枚举第一位的时候要从1开始，最后将所有位数较低的数字加上就好了。
时间复杂度
这种做法的时间复杂度主要在预处理上，为$O(n * 9^3)$,其中n为数字的位数。
参考文献
算法提高课
java代码
import java.io.*;
import java.util.*;
class Main{
static int N = 15;
static int[][][] f = new int[N][N][N];
static int[][] g = new int[N][N];
static void init(){
for(int i=0; i<=9; i++) {
f[1][i][i] = 1;
g[1][i] = 1;
}
for(int i=2; i<N; i++) {
for(int j=0; j<=9; j++) {
for(int k=0; k<=9; k++) {
g[i][j] += g[i-1][k];
}
}
}
for(int i=2; i<N; i++){
for(int j=0; j<=9; j++){
for(int x=0; x<=9; x++){
if(j == x) {
for(int k=0; k<=9; k++) f[i][j][x] += g[i-1][k];
}
for(int k=0; k<=9; k++){
f[i][j][x] += f[i-1][k][x];
}
}
}
}
}
static long dp(int n, int num){
if(n == 0) return 0;
List<Integer> l = new ArrayList<Integer>();
while(n != 0){
l.add(n % 10);
n /= 10;
}
long res = 0;
int last = 0;
for(int i=l.size()-1; i>=0; i--){
int x = l.get(i);
for(int j=(i==l.size()-1? 1 : 0); j<x; j++){
res += f[i+1][j][num] + (long)last * g[i+1][j];
}
if(x == num) last ++;
if(i == 0) res += last;
}
for(int i=1; i<l.size(); i++){
for(int j=1; j<=9; j++){
res += f[i][j][num];
}
}
return res;
}
public static void main(String[] args) throws IOException{
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
init();
String[] arr = in.readLine().split(" ");
int l = Integer.parseInt(arr[0]);
int r = Integer.parseInt(arr[1]);
while(l != 0 || r != 0){
if(l > r) {
int tmp = l;
l = r;
r = tmp;
}
for(int i=0; i<=9; i++){
System.out.print(dp(r, i) - dp(l-1, i) + " ");
}
System.out.println();
String[] cur = in.readLine().split(" ");
l = Integer.parseInt(cur[0]);
r = Integer.parseInt(cur[1]);
}
}
}
