用途

统计 $\text{[l,r]}$ 内符合要求的数字，一般是数位上带有xx的数字。

思路

（一般性的思路）设 $dp[i][j]$ 为不超过 i 位的数字数位上含有数字 j 的个数 $(0\le j\le 9)$ ，则 $dp[i][j]=10\times dp[i-1][j]+10^{i-1}$ ：首先在第 i 位加上前导的数字 $0\to9$ ，即乘十，暂不考虑前导数字中对 j 的统计；而前导数字为 j 的情况下，不考虑前 i-1 位数字中对 j 的统计（上一步已经统计过），则是前 i-1 位数字数目。

一般的题目中仍需要更多动态规划的构思。

例题

懒惰

洛谷 p2602 数字计数

给定两个正整数'a'和'b'，求在 $[a,b]$ 中的所有整数中，每个数码(digit)各出现了多少次。对于一个数 x ，计算 $[0,x]$ 中每个数码出现的次数：对于最高位 i ，首先每个数码都出现了 $i\times dp[i-1]$ 次，其次从0到 i-1 的每个数码都出现了 $10^{i-1}$ 次；
对于第 i 位，i 这个数码出现了去掉这一位之后余下的数字加一的次数；而去掉这一位之后余下的数字中的数码各自出现的次数需要$\times$1，即按照这种方法计算下一位。

code

#include<cstdio>
using namespace std;
long long a,b,dp[20],po[20]={1},all_=0,cnt[20];
void count(long long x,int m)
{
    if(!x) cnt[0]+=m;
    long long num=0;
    for(int i=0,op=x%10;x;num+=op*po[i++],x/=10,op=x%10)
    {
        for(int j=0;j<op;j++)
            cnt[j]+=po[i]*m;
        all_+=op*dp[i]*m;
        cnt[op]+=(num+1)*m;
        if(i) cnt[0]-=po[i]*m;
    }
}
int main()
{
    scanf("%lld%lld",&a,&b);
    for(int i=1;i<=15;i++)
    {
        po[i]=po[i-1]*10;
        dp[i]=dp[i-1]*10+po[i-1];
    }
    count(b,1);
    count(a-1,-1);
    for(int i=0;i<=9;i++)
        printf("%lld ",all_+cnt[i]);
    return 0;
}

CVBB ACM Team

目录

用途

思路

例题

洛谷 p2602 数字计数

CVBB ACM Team

用户工具

站点工具

目录

用途

思路

例题

洛谷 p2602 数字计数

页面工具