0%

[CQOI2016] 手机号码

题目

题目链接

题目大意:求出 $[l, r]$ 中所有满足数字中出现至少连续 $3$ 个相同的数字,并且不能同时出现 $4$ 和 $8$ 的数的个数。$10^{10} \le l \le r \le 10^{11}$。

思路

还是很模板的数位 DP,就是这个状态实在是太 tm 多了,写的人很烦。

然后就有一个很奇妙的事情,如果 $l = 10^{10}$ 我的程序就会锅。

很显然是求答案的时候出了问题,如果 $l = 10^{10}$,那求答案的时候就会求 $10^{10} - 1$,但是 $[1, 10^{10} - 1]$ 里根据题目是没有一个数是满足条件的。

所以要在开始就判断这个数是不是 $11$ 位数。

但是如果不判断的话,应该也会正常的减掉那些位数不够的数,不知道为什么会锅,而且答案差的还很多。

看了眼题解,全都是先枚举第一位然后再开始搜,这…

最后写了个特判过了,如果搜到第 $3$ 位还有前导零就直接返回 $0$。

懵。

代码

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

template <class T>
inline void read(T &x) {
x = 0;
int f = 0;
char ch = getchar();
while (!isdigit(ch)) { f |= ch == '-'; ch = getchar(); }
while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
x = f ? -x : x;
return ;
}

typedef long long LL;

LL f[20][2][2][2][10][10][2];
LL dig[20];
LL l, r, len;

LL dfs(int dep, bool lim, bool is4, bool is8, bool isc, int l1, int l2, bool zero) {
if (dep == 9 && (!zero)) return 0;
if (!dep) return ((!(is4 && is8)) && isc && zero);
if (!lim && (~f[dep][is4][is8][isc][l1][l2][zero])) return f[dep][is4][is8][isc][l1][l2][zero];
LL up = lim ? dig[dep] : 9, ans = 0;
for (int i = 0; i <= up; ++i) {
ans += dfs(dep - 1, lim && i == up, is4 || (i == 4), is8 || (i == 8), isc || (i == l1 && l1 == l2), i, l1, zero || i);
}
if (!lim) f[dep][is4][is8][isc][l1][l2][zero] = ans;
return ans;
}

LL solve(LL x) {
len = 0;
memset(dig, 0, sizeof(dig));
while (x) dig[++len] = x % 10, x /= 10;
memset(f, -1, sizeof(f));
return dfs(len, true, false, false, false, -1, -1, false);
}

int main() {
read(l), read(r);
printf("%lld\n", solve(r) - solve(l - 1));
return 0;
}