[ZJOI2010]count 数字计数

[ZJOI2010]count 数字计数

Time Limit:3000MS  Memory Limit:65536K
Total Submit:128 Accepted:63
Case Time Limit:1000MS

Description

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

Input

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

Output

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

Sample Input

1 99

Sample Output

9 20 20 20 20 20 20 20 20 20

Hint

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

Source

Day1
我的娘啊,这题搞死我了。。
数位统计真是恶心囧。。。
算法差不多吧,就是一位位统计过去,最关键的一点是处理好第一位为0的情况。。我的办法是首先看成0000-9999之类的,然后减掉多余的0囧。。

#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
const int inf=~0U>>1,maxn=10,maxd=15;
using namespace std;
typedef long long ll;
ll A[maxn],C[maxn],Pow[maxd],Pre[maxn];
int N[maxd],n;
void Dfs(int p)
{
int t=N[p];
if(p<0)
{
rep(j,10)C[j]+=Pre[j];
return;
}
rep(i,t)
{
ll num=Pow[p];
if(p==n-1&&i==0)
{
rep(j,10)C[j]+=num/10*p;
rep(j,p+1)
{
C[0]-=(Pow[p-j]-Pow[p-j]/10)*j;
}
}
else
{
Pre[i]++;
rep(j,10)C[j]+=Pre[j]*num;
Pre[i]–;num/=10;
rep(j,10)C[j]+=p*num;
}
}
Pre[t]++;Dfs(p-1);
}
void Cal(ll x)
{
for(n=0;x;x/=10,n++)N[n]=x%10;
memset(C,0,sizeof(C));
memset(Pre,0,sizeof(Pre));
Dfs(n-1);
}
int main()
{
//freopen("in","r",stdin);
//freopen("out","w",stdout);
ll a,b;cin>>a>>b;Pow[0]=1;rep(i,maxd-1)Pow[i+1]=Pow[i]*10;
Cal(b);rep(i,10)A[i]=C[i];
Cal(a-1);rep(i,10)A[i]-=C[i];
rep(i,10)cout<<A[i]<<" ";
}

6 thoughts on “[ZJOI2010]count 数字计数

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>