黄月英【题解 义乌中学模拟赛】

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。

丑陋的标程

#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;
}