「BZOJ 4521」「CQOI2016」手机号码

Description

现在需要找一些 $11$ 位的手机号码(不含前导零),要出现至少 $3$ 个相邻的相同数字,且不能同时出现 $4$ 和 $8$ 。问区间 $[l,r]\ (10^{10} \leq l \leq r < 10^{11})$ 中有多少符合上述条件的手机号码。

Source

[BZOJ]4521

Solution

考虑用 记忆化搜索 实现 数位DP

用 $f_{pos,pre1,pre2,four,eight,isThree}$ 表示 当前到了第 $12 - pos$ 位,前一位数是 $pre1$,前一位数的前一位数是 $pre2$,是否存在 $4$,是否存在 $8$,是否存在 $3$ 位数连续 的电话号码个数。因为固定 $11$ 位,只需要保证第 $1$ 位非零,所以不需要判断前导零。还有一个细节,当 $l = 10^{10}$ 时,$l - 1$ 会变成 $10$ 位数,显然不符合题意,这时计算就会出错,所以需要特判。具体实现详见代码,时间复杂度为 $O(\lg^3n)$ 。

Code

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <class T>
inline void read(T &x) {
x = 0;
char c = getchar();
bool f = 0;
for (; !isdigit(c); c = getchar()) f ^= c == '-';
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
x = f ? -x : x;
}

template <class T>
inline void write(T x) {
if (x < 0) {
putchar('-');
x = -x;
}
T y = 1;
int len = 1;
for (; y <= x / 10; y *= 10) ++len;
for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

const int MAXN = 11;
LL l, r, f[MAXN + 5][MAXN + 5][MAXN + 5][2][2][2];

inline LL dfs(int *num, int pos, int pre1, int pre2, bool four, bool eight, bool isThree, bool lim) {
//当前到了第 12 - pos 位,前一位数是 pre1,前一位数的前一位数是 pre2,
//four 表示是否出现过 4,eight 表示是否出现过 8,isThree 表示是否有 3 位数连续,lim 表示当前位是否受限制
//固定 11 位,不需要判断前导零,只需要保证开头(第 1 位)不为 0
if (four && eight) return 0;//不能同时有 4 和 8
if (!pos) return isThree;//搜完了,如果有三个以上连续的,返回 1
if (!lim && ~f[pos][pre1][pre2][four][eight][isThree]) return f[pos][pre1][pre2][four][eight][isThree];//返回已记录的值
LL res = 0, maxNum = lim ? num[pos] : 9;//当前位最大值
for (int i = (pos == 11); i <= maxNum; ++i)//第一位不能为 0
res += dfs(num, pos - 1, i, pre1, four || (i == 4), eight || (i == 8), isThree || (pre1 == pre2 && i == pre2), lim && (i == maxNum));
//搜索下一位,判断是否有 4,是否有 8 以及 是否存在 3 个数连续
if (!lim) f[pos][pre1][pre2][four][eight][isThree] = res;//存下当前状态的值
return res;
}

inline LL solve(LL x) {
int len = 0, num[MAXN + 5];
for (; x; x /= 10) num[++len] = x % 10;
memset(f, -1, sizeof (f));//初始化
return len == 11 ? dfs(num, len, 10, 10, 0, 0, 0, 1) : 0;//特判长度是否为 11
//第 1 位受到限制。前 2 位不能为 0 ~ 9,否则会影响检查是否存在 3 位数连续
}

int main() {
read(l), read(r);
write(solve(r) - solve(l - 1));
putchar('\n');
return 0;
}

本文标题:「BZOJ 4521」「CQOI2016」手机号码

文章作者:Heartlessly

发布时间:2019年04月22日 - 18:35:20

最后更新:2019年04月27日 - 15:46:41

原始链接:https://heartlessly.github.io/problems/bzoj-4521/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

0%