「CQOI2016」手机号码-数位dp

手机号码是一个有 $11$ 位且不含前导 $0$ 的数。满足条件手机号码的必须同时满足:号码中出现至少 $3$ 个相邻的相同数字;号码中不能同时出现 $8$ 和 $4$ 。

给定两个数 $L$ 和 $R$ ,统计出 $[L,R]$区间内所有满足条件的手机号码的个数。 $L$ 和 $R$ 都是符合定义的手机号码。

链接

Luogu P4124

题解

这个题用数位dp其实也可以递推。

定义一个状态$dp[i][j][num][is8][is4]$,其中$i$代表需要考虑的是后$i$位;$j$表示倒数第$i+1$位是数码$j$;$num$表示目前的连号是几个($num = 1,2$),若这个为$3$则代表已经出现了连着三位相同的数字;最后两维分别表示有没有出现$8$和有没有出现$4$。状态储存的值就是符合条件的数的个数。

边界情况就是在 $i == 0$ 的时候。只有 num == 3is8 && is4 == 0 时,边界才能得 $1$ ;否则就得 $0$ 。

其次转移就好了。枚举下一个数位从 $0$ 到 $9$ ,然后根据新的数位计算出 $num$ , $is8$ , $is4$ 等信息,转移就可以了。这里的 $num$ 如果已经为 $3$ ,就算与上一位相同,我们也不再往上加了;如果不是3的话才往上加。

注意在计算状态的时候,要把所有 is8 && is4 == 1 的情况全都置作$0$。


计算答案的话,就按照普通数位dp的统计方式去统计就可以了:把每一位都拆下来,在每一位都取到所有比这一位小的数,最后再加上最后一个数的情况。

代码

点击切换显示状态
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <cstdio>
using namespace std;
#define ll long long

const int MAXN = 12;

ll x,y;
ll dp[MAXN][MAXN][4][2][2];
//dp[i][j][num][is8][is4];
//后i位,上一个数字是j,连续出现了num个数,有没有出现8,有没有出现4

void init(){
scanf("%lld %lld",&x,&y);
}

void solve(){
for(int i = 0;i<=11;i++)
for(int j = 0;j<=9;j++)
for(int num = 1;num<=3;num++)
for(int is8 = 0;is8<=1;is8++)
for(int is4 = 0;is4<=1;is4++){
ll &t = dp[i][j][num][is8][is4];
if(i == 0)
t = (num==3?1:0);// 边界的判定
else for(int w = 0;w<=9;w++){
t += dp[i-1][w][num==3?3:w==j?num+1:1][is8||(w==8)][is4||(w==4)];
if(is8 && is4)
t = 0;
}
}
}

ll cal(ll x){
if (x < 1e10) return 0;
int d[20],cnt = 0;
while(t) d[++cnt] = x%10,x/=10;
d[cnt+1] = 0;
ll ans = 0;int num = 0,is8 = 0,is4 = 0;
for(int i = cnt;i>=1;--i){
for(int j = 0;j<d[i];j++)
ans += dp[i-1][j][num==3?3:d[i+1]==j?num+1:1][(j==8)||is8][(j==4)||is4];
// 该位小于限定数
num = (num == 3?3:d[i]==d[i+1]?num+1:1);
is8 |= d[i] == 8;
is4 |= d[i] == 4;
}
ans -= dp[10][0][1][0][0];//减去存在前缀0的情况
ans += dp[0][d[1]][num][is8][is4];
return ans;
}

void getans(){
ll ans = cal(y)-cal(x-1);
printf("%lld\n",ans);
}

int main(){
init();
solve();
getans();
return 0;
}