题目描述
给出一段区间a-b,统计这个区间内0-9出现的次数。
比如 10-19,1出现11次(10,11,12,13,14,15,16,17,18,19,其中11包括2个1),其余数字各出现1次。
Input
两个数a,b(1 <= a <= b <= 10^18)
Output
输出共10行,分别是0-9出现的次数
Input示例
10 19
Output示例
1
11
1
1
1
1
1
1
1
1
解题思路
解法一:
从低位向高位对每一个数位的可行值进行考虑,dp[i]代表当前数位为i时可行值的个数.以235678为例,假设当前遍历到了now=5这一数位,此时high=23,after=678,tmp=1000:
1.当 i < now 时,高位的取值范围是[0,23],则dp[i]+=(high+1)*tmp;
2.当 i > now 时,高位的取值范围是[0,22],则dp[i]+=high*tmp;
3.当 i = now 时,对应着高位取值是否等于high两种情况.当高位=high时,则低位取值不能超过after,即有after+1 种情况(加上低位取值为0 这种情况);当高位取值为[0,22]之间时,对应情况有high*tmp.则dp[i]+=high*tmp+after+1.
PS:当i=0时,需要减去高位取值也为0的情况,即dp[0]-=tmp.
解法二:
在递归模式下实现,dp[i]代表当前数位为i时可行值的个数.同样以235678为例,假设当前遍历到了5这一数位,由于在递归过程中,235***这种情况在上一层已经计算过,所以当前层 x=234 ,对应now=4,before=23=t ,tmp=1000.
1. 考虑23 #_ _ _,# 位置处取值范围为[0,x],则dp[0~now]+=tmp;同时对于高位2、3而言,对应出现了(now+1)*tmp次,即dp[2,3]+=(now+1)*tmp;
2. 考虑_ _ i _ _ _(i∈[0,9]),高位对应取值[0,22],则dp[i]+=before*tmp.同样需要减去i=0且高位取值也为0的情况.
代码实现
解法一
#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);\
cin.tie(0);\
cout.tie(0);
typedef long long ll;
ll num[10]= {0};
void solve(ll x,int mark)
{
ll tmp=1,after=0,high,now;
while(x)
{
now=x%10;
high=x/10;
for(int i=0; i<=9; i++)
{
if(now<i)
num[i]=num[i]+mark*high*tmp;
else if(now>i)
num[i]=num[i]+mark*(high+1)*tmp;
else
num[i]=num[i]+mark*(high*tmp+after+1);
}
num[0]=num[0]-mark*tmp;
x/=10;
after+=now*tmp;
tmp*=10;
}
}
int main()
{
IO;
ll a,b;
cin>>a>>b;
solve(b,1);
solve(a-1,-1);
for(int i=0; i<10; i++)
cout<<num[i]<<endl;
return 0;
}
解法二:
#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);\
cin.tie(0);\
cout.tie(0);
typedef long long ll;
ll num[10]= {0};
void solve(ll x,ll tmp,int mark)
{
ll now=x%10,before=x/10,t=before;
for(int i=0;i<=now;i++) num[i]+=mark*tmp;
for(int i=0;i<10;i++) num[i]+=mark*before*tmp;
num[0]-=mark*tmp;
while(t)
{
num[t%10]+=mark*tmp*(now+1);
t/=10;
}
if(before) solve(before-1,tmp*10,mark);
}
int main()
{
IO;
ll a,b;
cin>>a>>b;
solve(b,1,1);
solve(a-1,1,-1);
for(int i=0; i<10; i++)
cout<<num[i]<<endl;
return 0;
}