数位dp从会打模板到不会打模板

打了几个数位$dp$，发现自己除了会打模板之外没有任何长进，遇到非模板题依然什么都不会

那么接下来这篇文章将介绍如何打模板（滑稽）

假设我们要处理$l----r$

采用记忆化搜索的方式，枚举$<=r$每一种情况，枚举每一位，然后再枚举$<=l-1$每一种情况，然后两个值相减即可

我们可以比较轻松打出一个模板

ll dfs(ll x,ll pre,ll lead,ll limit){

    if(x>pos) return 1;

    if(!limit&&f[x][pre]) return f[x][pre];

    ll ans=0;

    ll mx=limit?maxn[pos-x+1]:9;

    for(ll i=0;i<=mx;i++){

        if(????????) continue;

        if(lead&&i==0) ans+=dfs(x+1,-2,1,limit&&(i==mx));

        else ans+=dfs(x+1,i,0,limit&&(i==mx));

    }

    if(!limit&&!lead) f[x][pre]=ans;

    return ans;

}

解释一下$limit$是什么

假设有一个数

$1\ 2\ 3\ 4\ 5\ 6$

$1\ 2\ 3\ ?\ ?\ ?$

我们枚举到第四位时最多枚举到$4$，

$1\ 2\ 3\ 4\ 5\ 6$

$1\ 2\ 2\ ?\ ?\ ?$

这时我们枚举到第四位最多枚举到$9$

$limit$就是判断这个的

那么为什么要在$！limit$下才记忆化呢？

如果在所有情况下我们都记录f，那么假如之前枚举到$9$时你记录了一个答案，然后当前位有$limit$限制根本枚举不到$9$，你仍然用了这个f会出现错误

当然你这样记忆化也可以这样避免冲突

ll dfs(ll x,ll limit,ll tmp,ll d){

    if(f[x][limit][tmp][d])

         return f[x][limit][tmp][d];

       ………………

    f[x][limit][tmp][d]=ans;

    return ans;

}

解释一下$lead$

处理前导0用的，

有的时候

$0\ 0\ 0\ 4\ 5\ 6$

也被认为是合法的，这时处理可能会出现问题，$lead$特判特殊处理

那么我们看几道模板题

例题

windy数

Windy 定义了一种 Windy 数：不含前导零且相邻两个数字之差至少为2的正整数被称为 Windy 数。

Windy 想知道，在l和r 之间，包括l 和 r ，总共有多少个 Windy 数？

非常简单对不对

套模板

代码：

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define A 50

ll f[A][A],maxn[A];

ll pos=0,a,b;

ll dfs(ll x,ll pre,ll lead,ll limit){

    if(x>pos) return 1;

    if(!limit&&f[x][pre]) return f[x][pre];

    ll ans=0;

    ll mx=limit?maxn[pos-x+1]:9;

//    printf("mx=%lld\n",mx);

    for(ll i=0;i<=mx;i++){

        if(abs(pre-i)<2) continue;

        if(lead&&i==0) ans+=dfs(x+1,-2,1,limit&&(i==mx));

        else ans+=dfs(x+1,i,0,limit&&(i==mx));

//        printf("ans=%lld\n",ans);

    }

    if(!limit&&!lead) f[x][pre]=ans;

    return ans;

}

ll solve(ll x){

    pos=0;

    memset(f,0,sizeof(f));

    while(x){

        maxn[++pos]=x%10;

        x/=10;

    }

    ll ans=dfs(1,-2,1,1);

    return ans;

}

int main(){

    scanf("%lld%lld",&a,&b);

    swap(a,b);

    printf("%lld\n",solve(a)-solve(b-1));

}

不要62

$l---r$间数位上不含$4$且没有$62$相连的数个数

套模板

代码

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define A 50

ll f[A][A],maxn[A];

ll pos=0,a,b;

ll dfs(ll x,ll pre,ll limit){

    if(!x) return 1;

    if(!limit&&f[x][pre]) return f[x][pre];

//    printf("x=%lld pre=%lld  limit=%lld\n",x,pre,limit);

    ll ans=0;

    ll mx=limit?maxn[x]:9;

    for(ll i=0;i<=mx;i++){

        if(pre==6&&i==2) continue;

        if(i==4) continue;

        ans+=dfs(x-1,i,limit&&(i==mx));

    }

//    printf("ans=%lld\n",ans);

    if(!limit) f[x][pre]=ans;

    return ans;

}

ll solve(ll x){

    pos=0;

    memset(f,0,sizeof(f));

    while(x){

        maxn[++pos]=x%10;

        x/=10;

    }

    ll ans=dfs(pos,0,1);

    return ans;

}

int main(){

    a=233,b=233;

    while(a!=0&&b!=0){

        scanf("%lld%lld",&a,&b);

        if(a<b)swap(a,b);

        if(a==0||b==0){

            return 0;

        }

        printf("%lld\n",solve(a)-solve(b-1));

    }

}

手机号码

至少$3$个相邻的相同的数，$8$ $4$不能同时出现

套模板，注意下特判，不然会70到自闭

代码

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define A 30

ll f[A][A][A][2][2][2],pos[A];

ll tot=0,a,b;

ll dfs(ll x,ll prer,ll pre,ll limit,ll _4,ll _8,ll ok){

    if(_4&&_8) return 0;

    if(x>tot&&!ok) return 0;

    if(x>tot&&ok) return 1;

    if(!limit&&f[x][prer][pre][_4][_8][ok]) return f[x][prer][pre][_4][_8][ok];

    ll maxn=limit?pos[tot-x+1]:9;

    ll ans=0;

    for(ll i=0;i<=maxn;i++){

        if(x==1&&i==0) continue;

        if(_4&&i==8) continue;

        if(_8&&i==4) continue;

        if(pre==prer&&i==pre&&i==prer)

            ans+=dfs(x+1,pre,i,(limit&&i==maxn),(_4||i==4),(_8||i==8),1);

        else

            ans+=dfs(x+1,pre,i,limit&&(i==maxn),(_4||i==4),(_8||i==8),ok);

//        printf("ans=%lld i=%lld maxn=%lld\n",ans,i,maxn);

    }

    if(!limit)

        f[x][prer][pre][_4][_8][ok]=ans;

    return ans;

}

ll solve(ll x){

    tot=0;

    if(x<1e10) return 0;

    memset(f,0,sizeof(f));

    while(x){

        pos[++tot]=x%10;

        x/=10;

    }

    ll ans=dfs(1,0,0,1,0,0,0);

    return ans;

}

int main(){

    scanf("%lld%lld",&a,&b);

    if(a<b) swap(a,b);

    printf("%lld\n",solve(a)-solve(b-1));

}

花神的数论题

设 sum(i) 表示 i 的二进制表示中 1 的个数。给出一个正整数 N ，花神要问你派(Sum(i)),也就是 sum(1)—sum(N) 的乘积。

套模板，等等，我要套什么，

这个题不算很板，值得思考思考。

数位dp计算出所有二进制下sum个数，然后快速幂处理一下，

代码

#include<bits/stdc++.h>

using namespace std;

#define A 53

#define mod 10000007

#define ll long long

ll n,tot=0,sum=0;

ll f[A][2][A][A],ans[A],pos[A];

ll dfs(ll cur,ll up,ll tmp,ll d){

    if(!cur)

        return tmp==d;

    if(~f[cur][up][tmp][d])

        return f[cur][up][tmp][d];

    ll lim=up?pos[cur]:1;

    ll ret=0;

    for(ll i=0;i<=lim;i++)

        ret+=dfs(cur-1,up&&i==lim,tmp+(i==1),d);

    return f[cur][up][tmp][d]=ret;

}

ll meng(ll a,ll b){

    ll ret=1;

    while(b)

        ret=ret*(b&1?a:1)%mod,a=a*a%mod,b>>=1;

    return ret;

}

ll solve(ll x){

    sum=1;

    while(x){

        pos[++tot]=x&1;

        x>>=1;

    }

    for(ll i=1;i<=tot;i++){

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

        ans[i]=dfs(tot,1,0,i);

    }

    for(ll i=1;i<=tot;i++){

        sum=(sum*max(meng(i,ans[i]),1ll))%mod;

    }

    return sum;

}

int main(){

    scanf("%lld",&n);

    printf("%lld\n",solve(n));

}

剩下一些题都不算很板

数数

淘金

方伯伯商场之旅

题解慢慢补充八

那么你现在会模板了吗？

巴特西

数位dp从会打模板到不会打模板

例题

windy数

代码：

不要62

代码

手机号码

代码

花神的数论题

代码

最新文章

热门文章