数位统计DP
给定两个整数 a 和 b，求 a 和 b 之间的所有数字中0 ~ 9的出现次数。
假设n=abcdefg 计算d位上x出现的次数res记录答案
#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; } }
