首页 > 代码库 > BZOJ 1833 ZJOI2010 count 数字计数 数位DP

BZOJ 1833 ZJOI2010 count 数字计数 数位DP

题目大意:求[a,b]间所有的整数中0~9每个数字出现了几次

令f[i]为i位数(算前导零)中每个数出现的次数(一定是相同的,所以只记录一个就行了)

有f[i]=f[i-1]*10+10^(i-1)

然后照例十进制拆分

其中计算[0,999...9]的时候要从1~9枚举最高位,然后其余位调用f[i-1]即可

剩余部分已知位直接乘,未知位调用f[i]

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
ll ans[10],f[20];
inline void Resolve(ll x,ll pos)
{
	while(x)
		ans[x%10]+=pos,x/=10;
}
void Digital_DP(ll x,int flag)
{
	int i,j;
	ll pos,now;
	for(i=1,pos=10;pos<x;++i,pos*=10)
	{
		for(j=0;j<=9;j++)
			ans[j]+=f[i-1]*9*flag;
		for(j=1;j<=9;j++)
			ans[j]+=pos/10*flag;
	}
	now=pos/=10;--i;
	while(now<x)
	{
		while(now+pos<=x)
		{
			ll temp=now/pos;
			Resolve(temp,pos*flag);
			for(j=0;j<=9;j++)
				ans[j]+=f[i]*flag;
			now+=pos;
		}
		pos/=10;--i;
	}
}
int main()
{
	int i;
	ll a,b,pos;
	f[1]=1;
	for(i=2,pos=10;i<=12;i++,pos*=10)
		f[i]=f[i-1]*10+pos;
	cin>>a>>b;
	Digital_DP(b+1,1);
	Digital_DP(a,-1);
	for(i=0;i<=9;i++)
		printf("%lld%c",ans[i],i==9?'\n':' ');
}


BZOJ 1833 ZJOI2010 count 数字计数 数位DP