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=