P4124 [CQOI2016]手机号码

题解

数位DP   DFS  虽然套路，但还是恶心到找不到锅在哪里

注意这个

然后你就发现其实这样就不用记录前导0了

锅在这个鬼地方QAQ

代码

#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 l,r;

ll c[],len=;

ll dp[][][][][][];

ll dfs(ll pos,ll pre,ll ppre,bool have8,bool have4,bool have,bool limit,bool qdl)

//当前填到了第几位，

  前一位是啥，

  前前位是啥，

  有没有8，

  有没有4，

  有没有连续相等的至少3个数，

  有没有顶上界，

  是不是全都是前导0

{

    if(have8&&have4) return ;

    if(pos<=) return have;

    if(!limit&&!qdl&&dp[pos][pre][ppre][have8][have4][have]!=-)

       return dp[pos][pre][ppre][have8][have4][have];

    ll ans=;

    ll up=limit?c[pos]:;

    for(ll i=(pos==len);i<=up;i++)

    //注意这里，如果是第一位就不能填0，要从1填起

      ans+=dfs(pos-,i,pre,

            have8||(i==),have4||(i==),

            have||((i==pre)&&(i==ppre)),

            limit&&(i==up),qdl&&(i==));

    if(!limit&&!qdl) dp[pos][pre][ppre][have8][have4][have]=ans;

    return ans;

}

ll sum(ll x)

{

    if(x<1e10||x>=1e11) return ;

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

    while(x)

    {

        c[++len]=x%;

        x/=;

    }

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

    return dfs(len,-,-,,,,,);

}

int main()

{

    l=read();r=read();

    if(l>r) { printf("0\n"); return ; }

    printf("%lld\n",sum(r)-sum(l-));

    return ;

}

#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 l,r;

ll c[],len=;

ll dp[][][][][][];

ll dfs(ll pos,ll pre,ll ppre,bool have8,bool have4,bool have,bool limit)

{

    if(have8&&have4) return ;

    if(pos<=) return have;

    if(!limit&&dp[pos][pre][ppre][have8][have4][have]!=-)

       return dp[pos][pre][ppre][have8][have4][have];

    ll ans=;

    ll up=limit?c[pos]:;

    for(ll i=(pos==len);i<=up;i++)

    //注意这里，如果是第一位就不能填0，要从1填起

      ans+=dfs(pos-,i,pre,

            have8||(i==),have4||(i==),

            have||((i==pre)&&(i==ppre)),

            limit&&(i==up));

    if(!limit) dp[pos][pre][ppre][have8][have4][have]=ans;

    return ans;

}

ll sum(ll x)

{

    if(x<1e10||x>=1e11) return ;

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

    while(x)

    {

        c[++len]=x%;

        x/=;

    }

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

    return dfs(len,-,-,,,,);

}

int main()

{

    l=read();r=read();

    if(l>r) { printf("0\n"); return ; }

    printf("%lld\n",sum(r)-sum(l-));

    return ;

}

不计前导0 （其实没有太大改变）