POJ - 2282 The Counting Problem(数位DP 计数问题)-Toy模板网

这篇具有很好参考价值的文章主要介绍了POJ - 2282 The Counting Problem(数位DP 计数问题)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目如下：

Given two integers a and b, we write the numbers between a and b, inclusive, in a list. Your task is to calculate the number of occurrences of each digit. For example, if $a = 1024$ and $b = 1032$ , the list will be
$1024$ $1025$ $1026$ $1027$ $1028$ $1029$ $1030$ $1031$ $1032$

there are ten 0’s in the list, ten 1’s, seven 2’s, three 3’s, and etc.

Input

The input consists of up to $500$ lines. Each line contains two numbers a and b where $0 < a, b < 100000000$ . The input is terminated by a line `0 0’, which is not considered as part of the input.
Output
For each pair of input, output a line containing ten numbers separated by single spaces. The first number is the number of occurrences of the digit $0$ , the second is the number of occurrences of the digit $1$ , etc.

Sample

Input

Output

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

题意简述：

计算 $a$ ~ $b$ , 0 ~ 9 数字的出现次数
注意：输入的时候可以 $a > b$ 计算的时候应使 $\le b$

思路 or 题意：

数位DP – 计数问题文章来源地址https://www.toymoban.com/news/detail-415963.html

AC 代码如下：

/*
Make it simple and keep self stupid
author：Joanh_Lan
*/
#pragma GCC optimize(3)
#pragma GCC optimize("inline") // 如果比赛允许开编译器优化的话，可以默写这两段
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <numeric>
#include <cstring>
#include <cmath>
#include <map>
#include <bitset>
#include <set>
#include <ctime>
#include <queue>
#include <stack>
#include <climits>
#define buff                     \
    ios::sync_with_stdio(false); \
    cin.tie(0);
#define int long long
#define ll long long
#define PII pair<int, int>
#define px first
#define py second
using namespace std;
const int mod = 1e9 + 7;
const int inf = 2147483647;
const int N = 100009;
//int Mod(int a,int mod){return (a%mod+mod)%mod;}
//int lowbit(int x){return x&-x;}//最低位1及其后面的0构成的数值
//int qmi(int a, int k, int p){int res = 1 % p;while (k){if (k & 1) res = Mod(res * a , p);a = Mod(a * a , p);k >>= 1;}return res;}
//int inv(int a,int mod){return qmi(a,mod-2,mod);}
//int lcm(int a,int b){return a*b/__gcd(a,b);}
int a, b, f[30][10][109], ans[10][2], dig[30];
int dfs(int pos, int idx, int cnt, bool lead, bool lim)
{
	if (!pos)	return cnt;
	if (!lim && !lead && f[pos][idx][cnt] != -1)	return f[pos][idx][cnt];


	int ans = 0, t = 0;
	int len = lim ? dig[pos] : 9;
	for (int i = 0; i <= len; i++)
	{
		if (i != idx)
			t = cnt;
		else 
		{
			if (lead && idx == 0)
				t = 0;
			else
				t = cnt + 1;
		}
		ans += dfs(pos - 1, idx, t, lead && i == 0, lim && i == len);
	}

	if (!lim && !lead)
		f[pos][idx][cnt] = ans;
	return ans;
}
void work(int x, int id)
{
	int idx = 0;
	while (x)
		dig[++idx] = x % 10, x /= 10;
	for (int i = 0; i <= 9; i++)
		ans[i][id] = dfs(idx, i, 0, 1, 1);
}
void solve()
{
	if (a > b)
		swap(a, b);
	work(a - 1, 0), work(b, 1);
	for (int i = 0; i <= 9; i++)
		cout << ans[i][1] - ans[i][0] << " \n"[i == 9];
}
signed main()
{
	buff;
	memset(f, -1, sizeof f);
	int _ = 1;
	// cin >> _;
	while (cin >> a >> b, a, b)
		solve();
}