51nod 1042 数字0-9的数量(数位dp)

时间:2022-12-15 23:10:49

题目描述

给出一段区间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;
}