P2602 [ZJOI2010]数字计数

题解

DFS 恶心的数位DP

对于这道题，我们可以一个数字一个数字的求

也就是分别统计区间 [ L , R ] 内部数字 i 出现的次数（0<=i<=9）

也就是DFS只需要记录：

当前填到第几位 pos

k一共出现多少次 sum

目标数字 k

是否顶上界 limit

是否全是前导零 qdl

dp[pos][sum]：

>不顶上界，没有前导零，

当前填到第pos位，目标数字一共出现sum次的时候（前pos位中一共有sum个目标数字）

对答案产生的贡献

>由于sum最多会取到和pos一样的个数，所以数组大小开的和pos一样就好了

这里 sum 记录的时候分两种情况：

（1）k!=0 直接看看所填数字是否目标数字就好了

（2）k=0 <1> 前面全是前导零，但是所填数字不是0

<2> 填到最后数字是0，也就是0000000，此时0要算出现一次

<3> 其余情况就不记录0出现的次数了

代码

#include<iostream>

#include<cstdio>

#include<string>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<cstdlib>

#include<queue>

using namespace std;

typedef long long ll;

inline ll read()

{

    ll ans=;

    char last=' ',ch=getchar();

    while(ch<''||ch>'') last=ch,ch=getchar();

    while(ch>=''&&ch<='') ans=ans*+ch-'',ch=getchar();

    if(last=='-') ans=-ans;

    return ans;

}

ll a,b;

ll c[],len;

ll dp[][];

ll dfs(ll pos,ll sum,ll k,bool limit,bool qdl)

{

    if(pos<=) return sum;

    if(!limit&&!qdl&&dp[pos][sum]!=-) return dp[pos][sum];

    ll ans=;

    ll up=limit?c[pos]:;

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

        ans+=dfs(pos-,sum+(k==?(!qdl&&i==)||(qdl&&i==&&pos==):(i==k)),k,limit&&(i==up),qdl&&(i==));

    if(!limit&&!qdl) dp[pos][sum]=ans;

    return ans;

}

ll sum(ll x,ll k)

{

    memset(c,,sizeof(c));len=;

    memset(dp,-,sizeof(dp));

    while(x)

    {

        c[++len]=x%;

        x/=;

    }

    return dfs(len,,k,,);

}

int main()

{

    a=read();b=read();

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

      printf("%lld ",sum(b,i)-sum(a-,i));

    return ;

}

双倍经验（比第一个简单）

P1239 计数器

题解

也就是只需要一个 a 就够够的了

代码

#include<iostream>

#include<cstdio>

#include<string>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<cstdlib>

#include<queue>

using namespace std;

typedef long long ll;

inline ll read()

{

    ll ans=;

    char last=' ',ch=getchar();

    while(ch<''||ch>'') last=ch,ch=getchar();

    while(ch>=''&&ch<='') ans=ans*+ch-'',ch=getchar();

    if(last=='-') ans=-ans;

    return ans;

}

const ll mod=1e9+;

ll a,b,T,ans=;

ll c[],len;

ll dp[][];

ll dfs(ll pos,ll sum,ll k,bool limit,bool qdl)

{

    if(pos<=) return sum;

    if(!limit&&!qdl&&dp[pos][sum]!=-) return dp[pos][sum];

    ll ans=;

    ll up=limit?c[pos]:;

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

        ans+=dfs(pos-,sum+(k==?(!qdl&&i==)||(qdl&&i==&&pos==):(i==k)),k,limit&&(i==up),qdl&&(i==));

    if(!limit&&!qdl) dp[pos][sum]=ans;

    return ans;

}

ll sum(ll x,ll k)

{

    memset(c,,sizeof(c));len=;

    memset(dp,-,sizeof(dp));

    while(x)

    {

        c[++len]=x%;

        x/=;

    }

    return dfs(len,,k,,);

}

int main()

{

    a=read();

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

       printf("%lld\n",sum(a,i));

    return ;

}

三倍经验

P4999 烦人的数学作业

题解

拿题一看：我要AC辣！！！

现实是 90pt

为哈！！！！！！

取模的锅，多取几次

P2602 [ZJOI2010]数字计数&P1239 计数器&P4999 烦人的数学作业

我还是太天真

代码

#include<iostream>

#include<cstdio>

#include<string>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<cstdlib>

#include<queue>

using namespace std;

typedef long long ll;

inline ll read()

{

    ll ans=;

    char last=' ',ch=getchar();

    while(ch<''||ch>'') last=ch,ch=getchar();

    while(ch>=''&&ch<='') ans=ans*+ch-'',ch=getchar();

    if(last=='-') ans=-ans;

    return ans;

}

const ll mod=1e9+;

ll a,b,T,ans=;

ll c[],len;

ll dp[][];

ll dfs(ll pos,ll sum,ll k,bool limit,bool qdl)

{

    if(pos<=) return sum;

    if(!limit&&!qdl&&dp[pos][sum]!=-) return dp[pos][sum];

    ll ans=;

    ll up=limit?c[pos]:;

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

        ans+=dfs(pos-,sum+(k==?(!qdl&&i==)||(qdl&&i==&&pos==):(i==k)),k,limit&&(i==up),qdl&&(i==));

    if(!limit&&!qdl) dp[pos][sum]=ans;

    return ans;

}

ll sum(ll x,ll k)

{

    memset(c,,sizeof(c));len=;

    memset(dp,-,sizeof(dp));

    while(x)

    {

        c[++len]=x%;

        x/=;

    }

    return dfs(len,,k,,);

}

int main()

{

    T=read();

    while(T--)

    {

        ans=;

        a=read();b=read();

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

        {

            ll tmp=((sum(b,i)-sum(a-1,i))%mod+mod)%mod; 

            ans=((ans+i*tmp%mod+mod)%mod+mod)%mod;

        }

        printf("%lld\n",ans%mod);

    }

    return ;

}