手机号码
题意
\(11\) 位手机号，求 \([L,R]\) 之间所有满足以下条件的号码个数：
-
\(4\) 和 \(8\) 不同时出现。
-
存在三个连续的数。
解析
拿来当数位 DP 板子（记搜版），记搜好用。
求 \([L,R]\) 的个数，我们用前缀和，求出 \([1,R]\) 和 \([1,L-1]\) 的个数，把限制条件变成一个。
dp 数组多开几维，把能记的状态都记上，转移按位枚举 \([0,9]\)，并且注意限制条件。
数位 DP 有一个很常见的限制条件是某一位是否达到最大数，如果达到了，那后面的数不能无限制的填，否则 \([0,9]\) 都可以。
然后你会发现所有数位 DP好像长得差不多。
#include<cstdio>
#include<cstring>
#define LL long long
LL l,r,f[11][11][11][2][2][2][2];
int n[12];
inline LL dfs(int p,int a,int b,bool c,bool t,bool _4,bool _8)
{
// p:now
// a:p+1
// b:p+2
// c:whether reach the limit?
// t:is there "three"
if(_4&&_8) return 0;//this is top priority
if(p<=0) return t;//pay attention the order
if(f[p][a][b][c][t][_4][_8]!=-1) return f[p][a][b][c][t][_4][_8];
LL res=0;int top=(c?n[p]:9);
for(int i=0;i<=top;i++)
res+=dfs(p-1,i,a,(c&&i==top),t||(i==a&&i==b),_4||i==4,_8||i==8);
return f[p][a][b][c][t][_4][_8]=res;
}
LL work(LL x)
{
if(x<1e10) return 0;//if smaller than 1e10,none.
int len=0;
while(x) n[++len]=x%10,x/=10;
LL res=0;
memset(f,-1,sizeof(f));
for(int i=1;i<=n[len];i++)
res+=dfs(10,i,0,i==n[len],0,i==4,i==8);
return res;
}
int main()
{
scanf("%lld%lld",&l,&r);
printf("%lld\n",work(r)-work(l-1));
return 0;
}