[CQOI 2016] 手机号码

题目大意

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

  • 有三个及以上连着的相同数字
  • 4488 不同时存在

1×1010l,  r<1×10111 \times 10^{10} \leqslant l, \; r < 1 \times 10^{11}

题目链接

【CQOI 2016】手机号码

题解

数位 DP。

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

DP 时,记 f(n,limit,last,equal,last,has4,has8)f(n, limit, last, equal, last, has4, has8) 为还剩 nn 位(从高位开始)、当前位最大值为 limitlimit 、上一位为 lastlast 、上一位与再上一位是否相等、是否有 44 、是否有 88 时的答案。转移时,枚举每一位,如果同时有 4488 就跳过,否则去考虑下一位。代码中,limit=10limit = 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;
}