即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

51Nod 数字0到9的数量 (数位DP)

编程语言 Since_natural_ran 16℃ 0评论

跟1009题类似:


http://blog.csdn.net/since_natural_ran/article/details/72668443

但是还是这道题考察能力强。


对于数字的考察有时候要多多注意规律,比如之前求1的数量的时候只是考虑了1,而其它的数字有时候和1有不同的情况,比如0.


按照其它的数字算的话总是0能多算一个dp[len-1]所以要减去。

#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long LL;

LL n,m;
LL dp[20];

void init()
{
    memset(dp,0,sizeof(dp));
    for(int i = 1;i < 20; i++) {
        dp[i] = dp[i-1]*10 + pow(10,i-1);
    }
}

LL solve(LL x,int nu)
{
    LL temp = x;
    LL ans = 0;
    LL tail = 0;
    LL tenn = 1;
    int digit = 0;
    int len = 0;

    while(x) {
        digit = x%10;
        x /= 10;
        len++;
        if(digit > nu) {
            ans += tenn + digit*dp[len-1];
        }
        else if(digit == nu) {
            ans += tail + 1 + digit*dp[len-1];
        }
        else {
            ans += digit*dp[len-1];
        }
        tail = tail + digit*tenn;
        tenn *= 10;
    }
    if(nu == 0) {
        LL t = 1;
        while(temp) {
            ans -= t;
            t *= 10;
            temp /= 10;
        }
    }
    return ans;
}

int main()
{
    //freopen("in.txt","r",stdin);

    init();
    scanf("%I64d%I64d",&n,&m);
    for(int i = 0;i <= 9; i++) {
        printf("%I64d\n",solve(m,i)-solve(n-1,i));
    }
    return 0;
}

转载请注明:CodingBlog » 51Nod 数字0到9的数量 (数位DP)

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情