黄月英【题解 义乌中学模拟赛】
LuckyCloud
2018-07-17 19:24:33
### 题目描述
xpp每天研究天文学研究哲学，对于人生又有一些我们完全无法理解的思考。 在某天无聊学术之后，xpp打开了 http://web.sanguosha.com， 准备用他心爱的黄月英虐人。进入了八人身份局，作为一位主公，xpp果断选了黄月英，用黄月英挑7人。
xpp为什么喜欢黄月英这个武将呢？因为集智是个很牛逼的技能。 集智——每当你使用一张非延时类锦囊（在它结算之前）你可以立即摸一张牌。 可见集智这个技能如果用得好那么牌是摸不完的。于是xpp把7个人全部轻松干掉。
虽然xpp的集智永远都能摸锦囊，但是他想到了这样一个问题：由于黄月英是一个富有智慧的人，所以xpp也要想一个富有智慧的问题，具体说来，他对牌上的数字产生了兴趣，于是他想知道，牌上每个数字出现过多少次。 当然，要算牌上的数字太简单了。所以xpp要扩大范围。
xpp正在考虑这样一个问题：从一个数字a到另一个数字b之间，从0到9的每个数字出现过多少次。
xpp智商过于强大，不屑于想此等低端问题，然后你就要把这道题做出来。
### 输入输出格式
#### 输入格式：
共一行，每行两个整数，分别为a，b。
#### 输出格式：
输出共一行，包含10个整数，分别代表从0到9的数字各出现过多少次。
### 输入输出样例
#### 输入样例#1
24 69
#### 输出样例#2
4 4 10 14 15 15 15 5 5 5
### 解题过程
#### 内心OS
本来自信满满准备来一波自认为很熟悉的数位DP，结果发现自己还是有些没理解，以为能秒掉的QAQ，没想到搞了一下午才过，数位DP真是博大精深啊，顺便提一下dp[x]是从最低位到第x位有多少个0,1,2,3,4,5,6,7,8,9。
#### 丑陋的标程
```cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long pos,l,r,num[20],t[13];
struct data
{
long long a[10],sum;
bool f;
data operator -(const data x)
{
data ret;
for (int i=0;i<10;i++)
{
a[i]-=x.a[i];
ret.a[i]=a[i];
}
return ret;
}
data operator +(const data x)
{
data ret;
for (int i=0;i<10;i++)
{
a[i]+=x.a[i];
ret.a[i]=a[i];
}
ret.sum=sum+x.sum;
return ret;
}
}dp[20],ans;
data dfs(int x,int n,bool limit,bool lead)
{
data ret;memset(ret.a,0,sizeof(ret.a));ret.sum=0;
if (x<=0)
{
ret.a[n]=1;
ret.sum=1;
return ret;
}
if (!limit&&dp[x].f&&!lead)
{
ret=dp[x];
ret.a[n]+=t[x+1];
return ret;
}
for (int i=0;i<=num[x]||(limit==false&&i<=9);i++)
ret=ret+dfs(x-1,i,limit&&i==num[x],lead&&i==0);
if (!limit&&!lead)
{
dp[x]=ret;
dp[x].f=true;
}
if (!lead)
{
if (!limit) ret.a[n]+=t[x+1];
else ret.a[n]+=ret.sum;
}
return ret;
}
data solve(long long x)
{
pos=0;
data ret;memset(ret.a,0,sizeof(ret.a));
while (x)
{
num[++pos]=x%10;
x/=10;
}
t[1]=1;
for (int i=2;i<=pos;i++)
t[i]=t[i-1]*10;
for (int i=0;i<=num[pos];i++)
ret=ret+dfs(pos-1,i,i==num[pos],i==0);
return ret;
}
inline long long read()
{
long long cnt=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-')f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){cnt=cnt*10+ch-48;ch=getchar();}
return cnt*f;
}
int main()
{
l=read();r=read();
ans=solve(r)-solve(l-1);
for (int i=0;i<=9;i++)
printf("%lld ",ans.a[i]);
return 0;
}
```