博客

给出一段区间a-b，统计这个区间内0-9出现的次数。

比如 10-19，1出现11次（10,11,12,13,14,15,16,17,18,19,其中11包括2个1)，其余数字各出现1次。

输入

两个数a,b（1 <= a <= b <= 10^18)

输出

输出共10行，分别是0-9出现的次数

输入样例

10 19

输出样例

1

11

1

1

1

1

1

1

1

1


满足区间减法，于是我们只需要分别计算 [0,a−1]以及 [0,b]的结果，相减既是答案。我们考虑从一个数 x的低位往高位开始枚举，对于第 k位我们分情况进行讨论。

假设 x=12345，k指向数字 3的位置，则此时pre=12,after=45,tmp=100

我们枚举 i从 0−9：

当前数字小于 i，即 i∈[4,9]，此时高位的变化范围可以是 [0,11]，共 pre×tmp种方案

当前数字大于 i，即 i∈[0,2]，此时高位的变化范围可以是 [0,12]，共 (pre+1)×tmp种方案

当前数字等于 i，即 i=3，此时高位的变化范围可以是 [0,12]，当且仅当高位等于 12时低位最多取到45，因此共有 pre×tmp+after+1种方案

特殊的当 i=0时且高位为 0时，显然这种情况是不允许的，因此我们需要减去一个 tmp 。


ps:


数位dp的做法

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll ans[10];
void solve(ll n,int sign)
{
 ll cur,pre,after,tmp=1,tn=n;
 while(n)
 {
 	cur=n%10;
 	pre=n/10;
 	after=tn-n*tmp;
 	for(int i=0;i<=9;i++)
 	{
 	 if(cur>i)
	  ans[i]+=(pre+1)*tmp*sign;
	 else if(cur<i)
	  ans[i]+=pre*tmp*sign;
	 else
	  ans[i]+=(pre*tmp+after+1)*sign;	
	}
	ans[0]-=tmp*sign;
	tmp*=10;n/=10;
 }
}
int main()
{
  ios::sync_with_stdio(false);
  ll r,l;
  cin>>l>>r;
  solve(l-1,-1);
  solve(r,1);
  for(int i=0;i<=9;i++)
   cout<<ans[i]<<endl;
  return 0;
}