首页 > 代码库 > BZOJ 1833 数字计数（统计[a,b]每个数字出现次数）

BZOJ 1833 数字计数（统计[a,b]每个数字出现次数）

2024-07-08 23:45:39   223人阅读

题目链接：http://61.187.179.132/JudgeOnline/problem.php?id=1833

题意：给定区间[a,b]。求区间内0到9每个数字出现的次数。

思路：f[i][j]表示到后i位是否全 0（j=1表示i位之前全0）这个状态某个数字出现的次数，p[i][j]表示这个状态后面有多少个数字。那么当前枚举到的数字为要统计的数字时，答案加 上后面还有多少种数字，即下一个状态的p值。那么我们枚举要统计的数字依次统计即可。

 

i64 f[20][2],p[20][2];i64 n,m;int a[20],aNum;int cur;pair<i64,i64> DFS(int dep,int flag,int allZero){    if(dep==-1)  return MP(0,1);    if(!flag&&f[dep][allZero]!=-1) return MP(f[dep][allZero],p[dep][allZero]);    i64 x=0,y=0;    int L=flag?a[dep]:9;    int i;    for(i=0;i<=L;i++)    {        pair<i64,i64> q=DFS(dep-1,flag&&(i==L),allZero&&(i==0));        x+=q.first;        y+=q.second;        if(i==cur)        {            if(i==0&&!allZero||i!=0) x+=q.second;        }    }    if(!flag)    {        f[dep][allZero]=x;        p[dep][allZero]=y;    }    return MP(x,y);}i64 cal(i64 n,int x){    if(n==0) return 0;    cur=x; aNum=0;    while(n)    {        a[aNum++]=n%10;        n/=10;    }    pair<i64,i64> p=DFS(aNum-1,1,1);    return p.first;}int main(){    RD(n); RD(m);    i64 a[20]={0};    int i;    FOR0(i,10)    {        clr(f,-1);        a[i]=cal(m,i)-cal(n-1,i);    }    printf("%lld",a[0]);    FOR1(i,9) printf(" %lld",a[i]);    puts("");}

 

 

 


联系
我们