[BZOJ1833][ZJOI2010]count 数字计数

[BZOJ1833][ZJOI2010]count 数字计数

试题描述

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

输入

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

输出

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

输入示例

输出示例

数据规模及约定

30%的数据中，a<=b<=10^6；
100%的数据中，a<=b<=10^12。

题解

数位 dp，许多恶心的边界条件需要考虑。

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <algorithm>

using namespace std;

#define LL long long

LL read() {

	LL x = 0, f = 1; char c = getchar();

	while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }

	while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }

	return x * f;

}

#define maxn 20

LL f[maxn][maxn][maxn], ans[maxn], ten[maxn];

void sum(LL x, int fl) {

	if(x < 0) return ;

	if(!x) ans[0] += fl;

	LL tot[maxn], tx = x;

	memset(tot, 0, sizeof(tot));

	int num[maxn], cnt = 0;

	while(x) num[++cnt] = x % 10, x /= 10;

	for(int k = 0; k <= 9; k++)

		for(int i = 1; i < cnt; i++)

			for(int j = (i == 1 ? 0 : 1); j <= 9; j++) tot[k] += f[k][i][j];

//	for(int i = 0; i <= 9; i++) printf("%lld%c", tot[i], i < 9 ? ' ' : '\n');

	for(int i = cnt; i; i--) {

		LL sum = 0;

		for(int k = 0; k <= 9; k++)

			for(int j = (i == cnt && i > 1 ? 1 : 0); j < num[i]; j++) tot[k] += f[k][i][j];

		tot[num[i]] += tx % ten[i-1] + 1;

	}

//	for(int i = 0; i <= 9; i++) printf("%lld%c", tot[i], i < 9 ? ' ' : '\n');

	for(int i = 0; i <= 9; i++) ans[i] += tot[i] * fl;

	return ;

}

int main() {

	ten[0] = 1;

	for(int i = 1; i < 13; i++) ten[i] = ten[i-1] * 10;

	for(int k = 0; k <= 9; k++) f[k][1][k] = 1;

	for(int k = 0; k <= 9; k++)

		for(int i = 1; i <= 13; i++)

			for(int j = 0; j <= 9; j++) {

//				if(k == 1) printf("%d %d %d: %lld\n", k, i, j, f[k][i][j]);

				for(int x = 0; x <= 9; x++)

					f[k][i+1][x] += f[k][i][j] + (x == k) * ten[i-1];

			}

	LL a = read(), b = read();

	sum(b, 1); sum(a - 1, -1);

	for(int i = 0; i <= 9; i++) printf("%lld%c", ans[i], i < 9 ? ' ' : '\n');

	return 0;

}

做的时候最好用暴力对拍一下。。。