[ZJOI2010]数字计数题解

题面

这道题是一道数位DP的模板题；

因为窝太蒟蒻了，所以不会递推，只会记忆化搜索；

首先，咋暴力咋来；

将一个数分解成一个数组，这样以后方便调用；

数位DP的技巧：(用1~b的答案)-(1~a的答案)就是(a~b的答案)；

那么对于每个数码i，我们做两次dfs(分别以a为上界和以b为上界)；

设正在搜索的数码是digit：

枚举每一位，当这位==digit时，便将答案+1，并记忆化；

然后就没了;

可是这样做忽略了两个重要的事情：

1.可能存在前导零；

2.目前搜到的数比目标值要大；

对于这两件事，在dfs中记录limit=1表示改为的上界就是目标的这一位的上界，否则对这一位不作要求；

head=1表示目前搜到的数不存在前导零；

很显然的：(伪代码)

long long dfs(int pos,int limit,int lead,int digit,long long sum)

register int up=; //up表示这一位的上界

if(limit) up=num[pos];

inc(j,,up) ans+=dfs(pos-,(j==up)&&limit,lead||j,digit,sum+((j||lead)&&(j==digit)));

利用好位运算，然后注意要记忆化，然后就可以AC了；

#include <bits/stdc++.h>

#define inc(i,a,b) for(register int i=a;i<=b;i++)

using namespace std;

long long a,b,f[34][3400],num[34];

long long  dfs(int pos,int limit,int lead,int digit,long long sum)

{

    long long ans=0;

    if(pos<=0) return sum;

    if(!limit&&lead&&f[pos][sum]!=-1) return f[pos][sum];

    register int up=9; if(limit) up=num[pos];

    inc(j,0,up) ans+=dfs(pos-1,(j==up)&&limit,lead||j,digit,sum+((j||lead)&&(j==digit)));

    if(!limit&&lead) f[pos][sum]=ans;

    return ans;

}

long long work(long long x,register int type)

{

    memset(f,-1,sizeof(f));

    register int len=0;

    while(x){

        num[++len]=x%10;

        x/=10;

    }

    return dfs(len,1,0,type,0);

}

int main()

{

    cin>>a>>b;

    for(register int i=0;i<=9;i++){

        cout<<work(b,i)-work(a-1,i);

        if(i!=9) cout<<" ";

    }

}

/*

1 99

*/

巴特西

[ZJOI2010]数字计数题解

最新文章

热门文章

巴特西

[ZJOI2010]数字计数 题解

最新文章

热门文章

[ZJOI2010]数字计数题解