[CQOI 2016] 手机号码

发表于2017-05-05更新于2020-08-06

题目大意

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

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

1×1010⩽l,  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 时的答案。转移时，枚举每一位，如果同时有 44 和 88 就跳过，否则去考虑下一位。代码中，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;
}