时间戳

首页 > 技术文章 > zznu 1255 数字统计(数位DP, 数学方法)

zznu 1255 数字统计(数位DP, 数学方法)

chenchengxun 2015-04-25 09:59 原文

最近在学数位DP， 感觉还是满有收获的！ 做了几个题之后想起来自己OJ上曾经做的一道题，以前是用数学方法写的，现在改用数位DP来写了一遍。

题目：

1255: 数字统计

时间限制: 1 Sec  内存限制: 128 MB
提交: 31  解决: 4
[提交][状态]

题目描述

一本书的页码从自然数1 开始顺序编码直到自然数n。书的页码按照通常的习惯编排， 
每个页码都不含多余的前导数字0。例如，第6 页用数字6 表示，而不是06 或006 等。数 
字计数问题要求对给定书的总页码n，计算出书的全部页码中分别用到多少次数字0，1， 
2，…，9。

输入

给出表示书的总页码的整数n（1≤n≤2^31-1）

输出

输出10行，在第k行输出页码中用到数字k-1 的次数，k=1，2，…，10。

样例输入

11

样例输出

1
4
1
1
1
1
1
1
1
1

 

链接：http://acm.zznu.edu.cn/problem.php?id=1255

数学方法：

其实就是假设每一位是0-9然后进行判断， 计算出结果

#include<stdio.h>
int  Slove(int num,int k)
{
    int L, R, M, P = 1, a = num;
    int sum = 0;
    while(a)
    {
        R = num%P;
        M = a%10;
        L = a/10;
        if(k)
        {
            if(k < M)
                sum += (L+1)*P;
            else if(k == M)
                sum += L*P + (R+1);
            else
                sum += L*P;
        }
        else
        {
            if(a<10)
                break;
            if(k == M)
                sum += (L-1)*P + (R+1);
            else
                sum += L*P;
        }
        P *= 10;
        a /= 10;

    }
    return sum;
}

int main()
{
    int  n, ans;
    int i;
    scanf("%d",&n);
    for(i=0; i<=9; i++)
    {
        ans = Slove(n,i);
        printf("%d\n",ans);
    }
    return 0;
}

数位DP;

这个就比较通用了， 就是套模版， 对数据的处理上 稍加注意， 然后把状态确定好。

 

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
LL dp[20][20][11][2];//dp[位数][数字出现的次数][这个数字是多少][首位是否是0]
int bit[20];

LL dfs(int pos,int cou,int num,int flag,bool is0)
{
    if( pos == -1 )
    {
        return  cou;
    }
    
    if(!flag && dp[pos][cou][num][is0] != -1)
        return dp[pos][cou][num][is0];
    
    LL ans = 0;
    int end = flag? bit[pos]: 9;

    for(int i=0; i<=end; i++)
    {
        if(i == num && !(is0 && i == 0) )
            ans += dfs(pos-1, cou+1, num, flag && i == end,  is0 && i == 0 );
        else
            ans += dfs(pos-1, cou, num, flag && i == end, is0 && i == 0 );
    }
    
    if(!flag)
        dp[pos][cou][num][is0] = ans;
    
    return ans;
}


void solve(LL n)
{
    int len = 0, i, m = n;
    LL ans;
    while(n)
    {
        bit[len++] = n%10;
        n /= 10;
    }
    
    for(i=0; i<=9; i++)
    {
        ans = dfs(len-1, 0, i, 1, 1);
        printf("%lld\n", ans);
    }
//    printf("\n\n\n");
}

int main()
{
    LL a;
    memset(dp, -1 ,sizeof(dp));
    
    while(scanf("%lld", &a) != EOF)
    {
        solve(a);
    }
//    printf("\n\n\n");
    return 0;
}

 

推荐阅读