手机号码

本文主要是介绍手机号码，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

手机号码

题解

一道典型的数位dp，我们只需要将它的编号，是上一位，上两位，是否有三个连续，是否有4，是否有8，加入dp。我们可以用dfs,来更新数位dp。注意在dfs中加入是否达到当前最大值，来枚举当前数字。

源码

#include<cstdio>
#include<cstring>
#include<iostream> 
#include<algorithm>
#include<stack>
#include<vector>
#include<queue>
using namespace std;
typedef long long LL;
#define gc() getchar()
LL l,r,pow_10[20];
LL dp[15][15][15][5][5][5]; 
template<typename _T>
inline void read(_T &x)
{_T f=1;x=0;char s=gc();while(s>'9'||s<'0'){if(s=='-')f=-1;s=gc();}while(s>='0'&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=gc();}x*=f;
}
LL dfs(LL x,LL id,LL im,LL in,bool s1,bool s2,bool s3,bool s4)
{if(s2&&s3) return 0;//是否同时出现4与8if(!id) return s1;//是否枚举到第11位if(!s4&&dp[id][im][in][s1][s2][s3]!=-1)return dp[id][im][in][s1][s2][s3];//是否更新过LL res=0,maxx=s4?x/pow_10[id-1]%10:9;for(int i=0;i<=maxx;i++)res+=dfs(x,id-1,i,im,s1||(i==in&&i==im),s2||i==8,s3||i==4,s4&&i==maxx);//更新当前值if(!s4) dp[id][im][in][s1][s2][s3]=res;//记忆化return res;
}
LL solve(LL x)
{if(x<pow_10[10]) return 0;memset(dp,-1,sizeof(dp));LL ans=0;for(int i=1;i<=x/pow_10[10];i++)ans+=dfs(x,10,i,0,0,i==8,i==4,i==x/pow_10[10]);//第一位不能为0，必须枚举第一位。return ans;
}
int main()
{pow_10[0]=1;for(int i=1;i<=11;i++)pow_10[i]=pow_10[i-1]*10;//预处理10的次方read(l);read(r);printf("%lld\n",solve(r)-solve(l-1));return 0;
}

谢谢！！！

这篇关于手机号码的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---