数位统计DP

给定两个整数 a 和 b，求 a 和 b 之间的所有数字中0 ~ 9的出现次数。

假设 n = a b c d e f g n = abcdefg n=abcdefg 计算 d d d位上 x x x出现的次数 r e s res res记录答案

1、 ( 001 — — a b c − 1 ) (001——abc-1) (001——abc−1) x x x ( 000 — — 999 ) (000——999) (000——999) r e s + = a b c ∗ 1000 res += abc * 1000 res+=abc∗1000

2、 a b c abc abc x x x

​ 2.1、 d < x d < x d<x r e s + = 0 res += 0 res+=0

​ 2.2、 d = x d = x d=x 000 — — e f g 000——efg 000——efg r e s + = e f g + 1 res += efg + 1 res+=efg+1

​ 2.3、 d > x d > x d>x 000 — — 999 000——999 000——999 r e s + = 1000 res += 1000 res+=1000

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define mod 1000000007
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl '\n'
#define eps 1e-6
inline int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a; }
inline int lowbit(int x) {
    return x & -x; }


using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
int get(vector<int>num,int l,int r) {
   //计算num中第l到第r位的数
	int res = 0;
	for (int i = l;i >= r;--i) {
   
		res = res * 10 + num[i];
	}
	return res;
}
int power10(int x) {
   //10的x次方
	int res = 1;
	while (x--)res *= 10;
	return res;
}
int count(int n, int x) {
   //统计1到n中x出现的次数
	if (!n)return 0;

	vector<int>num;
	while (n) {
    //n的得到每一位
		num.push_back(n % 10);
		n /= 10;
	}
	n = num.size();
	int res = 0;

	for (int i = n - 1 - !x; i >= 0;--i) {
   
		if (i < n - 1) {
    //当i为第一位时 第一种情况不存在 
			res += get(num, n - 1, i + 1) * power10(i);
			if (!x)res -= power10(i); //如果x为0的话 x之前的数都不能为0
		}

		if (num[i] == x)res += get(num, i - 1, 0) + 1;
		else if (num[i] > x)res += power10(i);
	}
	return res;

}
int main() {
   
	int a, b;
	while (cin >> a >> b, a || b) {
   
		if (a > b)swap(a, b);

		for (int i = 0;i < 10;++i) {
   
			cout << count(b, i) - count(a - 1, i) << " ";// 前缀和的思想
		}
		cout << endl;
	}
}