首页 > 代码库 > 【bzoj1833】 ZJOI2010—count 数字计数

【bzoj1833】 ZJOI2010—count 数字计数

2024-09-04 02:19:47   219人阅读

http://www.lydsy.com/JudgeOnline/problem.php?id=1833 (题目链接)

题意

　　求在${[a,b]}$范围内整数中，每个数码出现的次数。

Solution

　　数位dp。

　　${t}$数组取到最大数时表示每一位是多少。

　　${f[i][j][k]}$表示第${i}$位，这一位上的数为${j}$，数字${k}$的出现次数。转移：$${f[i][j][k]=\sum_{l=0}^9f[i-1][l][k]+10^(i-1)}$$

　　${g[i][k]}$表示第${i}$位，这一位上的数取到最大时数字${k}$的出现次数。转移：$${g[i][k]=\sum_{j=0}^{t[i-1]-1}f[i-1][j][k]+g[i-1][k]}$$

　　当然，如果${g[i][t[i]]}$还要再加上${t[i]}$对方案的贡献。

细节

　　感觉细节还是蛮多的，还是不够熟练啊

代码

// bzoj1833#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#include<ctime>#define LL long long#define inf (1ll<<30)#define MOD 1000000007#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;LL a[2],t[20],f[20][10][10],g[20][10],ans[10];int n;void solve(int p) {	memset(f,0,sizeof(f));memset(g,0,sizeof(g));	for (n=0;a[p];a[p]/=10) t[++n]=a[p]%10;	for (int i=0;i<10;i++) f[1][i][i]=1;	LL bin=1,bb=0;	g[1][t[1]]=1;	for (int i=2;i<=n;i++) {		bb+=bin*t[i-1],bin*=10;		for (int j=0;j<10;j++) {			for (int k=0;k<10;k++) 				for (int l=0;l<10;l++) f[i][j][k]+=f[i-1][l][k];			f[i][j][j]+=bin;		}		for (int k=0;k<10;k++) {			g[i][k]=g[i-1][k];			for (int j=0;j<t[i-1];j++) g[i][k]+=f[i-1][j][k];		}		g[i][t[i]]+=bb+1;	}	int q=p ? 1 : -1;	for (int i=1;i<n;i++)		for (int j=1;j<10;j++)			for (int k=0;k<10;k++)				ans[k]+=f[i][j][k]*q;	for (int j=1;j<t[n];j++)		for (int k=0;k<10;k++)			ans[k]+=f[n][j][k]*q;	for (int k=0;k<10;k++)		ans[k]+=g[n][k]*q;}int main() {	scanf("%lld%lld",&a[0],&a[1]);a[0]--;	solve(0);solve(1);	for (int i=0;i<10;i++) {		printf("%lld",ans[i]);		if (i<9) printf(" ");	}	return 0;}

　　

【bzoj1833】 ZJOI2010—count 数字计数


联系
我们