BZOJ4521: [Cqoi2016]手机号码

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

丝帛数位DP，大意是设一个好大的状态如：f[i][cur][j][is8][is4][isok][=/<]

#include<cstdio>

#include<cctype>

#include<queue>

#include<cstring>

#include<algorithm>

#define rep(i,s,t) for(int i=s;i<=t;i++)

#define dwn(i,s,t) for(int i=s;i>=t;i--)

#define ren for(int i=first[x];i;i=next[i])

using namespace std;

typedef long long ll;

ll f[15][3][10][2][2][2][2];

//f[i][cur][j][is8][is4][isok][=/<]

int bit[15],len;

ll solve(ll n) {

	ll ans=0;

	if(n==99999999999ll+1) ans++,n--;

	memset(f,0,sizeof(f));len=0;

	while(n) bit[++len]=n%10,n/=10;

	rep(i,1,bit[len]) f[len][1][i][i==8][i==4][0][i<bit[len]]=1;

	dwn(i,len-1,1) rep(cur,1,2) rep(j,0,9) rep(is8,0,1) rep(is4,0,1) rep(isok,0,1) rep(c,0,1) {

		ll& ans=f[i+1][cur][j][is8][is4][isok][c];

		if(ans) {

			rep(k,0,(c?9:bit[i])) {

				if(k==j&&cur==2&&!isok) f[i][1][k][is8|(k==8)][is4|(k==4)][1][c|(k<bit[i])]+=ans;

				else if(k==j&&!isok) f[i][cur+1][k][is8|(k==8)][is4|(k==4)][isok][c|(k<bit[i])]+=ans;

				else f[i][1][k][is8|(k==8)][is4|(k==4)][isok][c|(k<bit[i])]+=ans;

			}

		}

	}

	rep(j,0,9) rep(is8,0,1) rep(is4,0,1) if(is8+is4<=1) ans+=f[1][1][j][is8][is4][1][1];

	return ans;

}

int main() {

	ll l,r;scanf("%lld%lld",&l,&r);

	printf("%lld\n",solve(r+1)-solve(l));

	return 0;

}

秒客网