[BZOJ 4521][CQOI 2016] 手机号码

题目大意

\([l, \; r]\) 内满足以下条件的数的个数:

  • 有三个及以上连着的相同数字
  • \(4\)\(8\) 不同时存在

\(1 \times 10^{10} \leqslant l, \; r < 1 \times 10^{11}\)

题目链接

BZOJ 4521

题解

数位 DP。

计算小于等于一个数的答案,最终答案相减。

DP 时,记 \(f(n, limit, last, equal, last, has4, has8)\) 为还剩 \(n\) 位(从高位开始)、当前位最大值为 \(limit\) 、上一位为 \(last\) 、上一位与再上一位是否相等、是否有 \(4\) 、是否有 \(8\) 时的答案。转移时,枚举每一位,如果同时有 \(4\)\(8\) 就跳过,否则去考虑下一位。代码中,\(limit = 10\) 表示这一位与接下来的位都没有限制。

代码

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
#include <cstdio>
#include <cstring>
#include <algorithm>
const int LEN = 11;
const long long MIN = 1e10;
int a[LEN];
long long f[LEN][11][10][2][2][2][2];
bool calced[LEN][11][10][2][2][2][2];
long long dp(int n, int limit, int last, bool equal, bool flag, bool has4, bool has8) {
long long &curr = f[n][limit][last][equal][flag][has4][has8];
if (calced[n][limit][last][equal][flag][has4][has8]) return curr;
calced[n][limit][last][equal][flag][has4][has8] = true;
curr = 0;
if (n == 1) {
for (int i = 0; i <= std::min(limit, 9); i++) {
if ((has4 && has8) || (i == 4 && has8) || (i == 8 && has4)) continue;
if (flag || (equal && i == last)) curr++;
}
} else {
int next = a[LEN - n + 1];
for (int i = 0; i <= std::min(limit, 9); i++) {
if ((has4 && has8) || (i == 4 && has8) || (i == 8 && has4)) continue;
int temp = i < limit || limit == 10 ? 10 : next;
curr += dp(n - 1, temp, i, i == last, flag || (equal && i == last),
has4 || (i == 4), has8 || (i == 8));
}
}
return curr;
}
long long calc(long long x) {
if (x < MIN) return 0;
for (int i = LEN - 1; ~i; i--) a[i] = x % 10, x /= 10;
memset(calced, false, sizeof (calced));
long long res = 0;
for (int i = 1; i <= a[0]; i++) {
int limit = i == a[0] ? a[1] : 10;
res += dp(LEN - 1, limit, i, false, false, i == 4, i == 8);
}
return res;
}
int main() {
long long l, r;
scanf("%lld %lld", &l, &r);
printf("%lld\n", calc(r) - calc(l - 1));
return 0;
}