P1239 计数器

题目描述

一本书的页数为N，页码从1开始编起，请你求出全部页码中，用了多少个0，1，2，…，9。其中—个页码不含多余的0，如N＝1234时第5页不是0005，只是5。

输入输出格式

输入格式：

一个正整数N(N≤10^9)，表示总的页码。

输出格式：

共十行：第k行为数字k-1的个数。

输入输出样例

输入样例#1：复制

输出样例#1：复制

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

int n;

int num[];

int main(){

    scanf("%d",&n);

    for(int i=;i<=n;i++){

        int x=i;

        while(x){

            num[x%]++;

            x/=;

        }

    }

    for(int i=;i<=;i++)

        cout<<num[i]<<endl;

}

80分的暴力

正解思路：数位DP

f[i][j][k]表示有i位，最高位为j，数字k出现的次数。

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

int n,tot;

int ans[];

int sum[],num[];

int f[][][];

int main(){

    scanf("%d",&n);

    for(int i=;i<=;i++)    f[][i][i]=;

    sum[]=;

    for(int i=;i<=;i++){

        sum[i]=sum[i-]*;

        f[i][][]=f[i-][][]*+f[i-][][]+sum[i];

        for(int j=;j<=;j++)    f[i][][j]=f[i-][][j]*+f[i-][j][j];

        for(int j=;j<=;j++){

            f[i][j][]=f[i-][][]*+f[i-][][];

            for(int k=;k<=;k++){

                if(j==k)    f[i][j][k]=f[i-][][k]*+f[i-][k][k]+sum[i];

                else f[i][j][k]=f[i-][][k]*+f[i-][k][k];

            }

        }

    }

    int x=n;

    while(x){ num[++tot]=x%;x/=; }

    for(int i=;i<tot;i++)

        for(int j=;j<=;j++)

            for(int k=;k<=;k++)

                ans[k]+=f[i][j][k];

    for(int i=tot;i>=;i--){

        for(int j=;j<num[i];j++){

            if(i==tot&&j==)    continue;

            for(int k=;k<=;k++)    ans[k]+=f[i][j][k];

        }

        ans[num[i]]+=n%sum[i]+;

    }

    for(int i=;i<=;i++)    printf("%d\n",ans[i]);

}

巴特西

洛谷 P1239 计数器

P1239 计数器

题目描述

输入输出格式

输入输出样例

最新文章

热门文章