4521: [Cqoi2016]手机号码

时间:2022-10-11 15:05:40

4521: [Cqoi2016]手机号码

Time Limit: 10 Sec Memory Limit: 512 MB

Submit: 1030 Solved: 609

[Submit][Status][Discuss]

Description

人们选择手机号码时都希望号码好记、吉利。比如号码中含有几位相邻的相同数字、不含谐音不

吉利的数字等。手机运营商在发行新号码时也会考虑这些因素,从号段中选取含有某些特征的号

码单独出售。为了便于前期规划,运营商希望开发一个工具来自动统计号段中满足特征的号码数

量。

工具需要检测的号码特征有两个:号码中要出现至少3个相邻的相同数字,号码中不能同

时出现8和4。号码必须同时包含两个特征才满足条件。满足条件的号码例如:13000988721、

23333333333、14444101000。而不满足条件的号码例如:1015400080、10010012022。

手机号码一定是11位数,前不含前导的0。工具接收两个数L和R,自动统计出[L,R]区间

内所有满足条件的号码数量。L和R也是11位的手机号码。

Input

输入文件内容只有一行,为空格分隔的2个正整数L,R。

10^10 < = L < = R < 10^11

Output

输出文件内容只有一行,为1个整数,表示满足条件的手机号数量。

Sample Input

12121284000 12121285550

Sample Output

5

样例解释

满足条件的号码: 12121285000、 12121285111、 12121285222、 12121285333、 12121285550

HINT

Source

数位dp

\(dp[now][n4][n8][l][r][s][t][las]\)分别表示枚举到第i位时,有没有出现过4,有没有出现过8,卡不卡左边界,卡不卡右边界,有没有过连续三个数相同,结尾连续几个数相同,上一位的值


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define max(a,b) ((a)>(b) ? (a): (b))
#define min(a,b) ((a)<(b) ? (a): (b))
#define LL long long
using namespace std; LL i,n,m,j,k,a[13][2][2][2][2][2][5][11],b[12],c[12];
LL ans; int main()
{
for(i=1;i<=11;i++) scanf("%1ld",&b[i]);
for(i=1;i<=11;i++) scanf("%1ld",&c[i]); for(i=b[1];i<=c[1];i++)
{
LL t,g;
if(i==4) t=1; else t=0;
if(i==8) g=1; else g=0;
LL l=(i==b[1])?1:0;
LL r=(i==c[1])?1:0;
a[1][t][g][l][r][0][1][i]=1;
} for(i=2;i<=11;i++)
for(LL b4=0;b4<=1;b4++)
for(LL b8=0;b8<=1;b8++)
for(LL l=0;l<=1;l++)
for(LL r=0;r<=1;r++)
for(LL s=0;s<=1;s++)
for(LL t=0;t<3;t++)
for(LL las=0;las<=9;las++)
{
if(!a[i-1][b4][b8][l][r][s][t][las]) continue;
for(j=0;j<=9;j++)
{ LL n4=0,n8=0,ll=0,rr=0,ss=0,gs=1;
if(b4 && b8) continue;
if(b4 && (j==8)) continue;
if(b8 && (j==4)) continue;
if(l && (j<b[i])) continue;
if(r && (j>c[i])) continue;
if(b4 || (j==4)) n4=1;
if(b8 || (j==8)) n8=1;
if(l && (j==b[i])) ll=1;
if(r && (j==c[i])) rr=1;
if(j==las) gs=t+1;
else gs=1;
if((gs==3) || s) ss=1;
if(gs==3) gs=1;
a[i][n4][n8][ll][rr][ss][gs][j]+=a[i-1][b4][b8][l][r][s][t][las];
if((i==11) && ss) ans+=(LL)a[i-1][b4][b8][l][r][s][t][las];
}
}
printf("%lld",ans);
}

可以说是非常美观的代码了=v=