Skip to content

「SCOI2009」Windy 数

题解854 字
# 2009 # 洛谷 # BZOJ # 动态规划 # LibreOJ # SCOI # 数位 DP
检测到 KaTeX 加载失败，可能会导致文中的数学公式无法正常渲染。

#题面

#题目背景

Windy 定义了一种 Windy 数。

#题目描述

不含前导零且相邻两个数字之差至少为 22 的正整数被称为 Windy 数。Windy 想知道，在 aa 和 bb 之间，包括 aa 和 bb ，总共有多少个 Windy 数？

#输入格式

输入只有一行两个整数，分别表示 aa 和 bb。

#输出格式

输出一行一个整数表示答案。

#输入输出样例

样例输入 #1

1 10

样例输出 #1

9

样例输入 #2

25 50

样例输出 #2

20

#数据范围与提示

对于 100%100\% 的测试点，1≤a≤b≤2×1091 \leq a \leq b \leq 2 \times 10^9。

#思路

数位 DP，可以使用前缀和的思想解决。先求出 [0,b+1][0, b + 1] 和 [0,a][0, a] 的答案，再将二者相减即可。

设 fi,jf_{i, j} 表示长度为 ii 的数中最高为数码是 jj 的数的 Windy 的数的个数，有转移方程：

fi,j=∑∣j−k∣≥2fi−1,kf_{i, j} = \sum_{|j - k| \geq 2} f_{i - 1, k}

求取 [0,x][0, x] 之间的 Windy 数数量时需要将大区间分成数段区间来计算，以 35783578 为例：

  1. 计算 [0,1000)[0, 1000) 之间的 Windy 数的数量。

    C++
    28
    29
    30
    31
    32
    33
    // 次高位及以前的 Windy 数的数量
    for (int i = 1; i < num.size(); i++) {
        for (int j = 1; j < 10; j++) {
            res += f[i][j];
        }
    }

  2. 计算 [1000,3000)[1000, 3000) 之间的 Windy 数的数量。

    C++
    35
    36
    37
    38
    // 最高位小于原数最高位的 Windy 数的数量
    for (int i = 1; i < *num.rbegin(); i++) {
        res += f[num.size()][i];
    }

  3. 计算 [3000,3578)[3000, 3578) 之间的 Windy 数的数量。

    C++
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    // 最高位等于原数最高位的 Windy 数
    for (int i = num.size() - 1; i; i--) {
        for (int j = 0; j < num[i - 1]; j++) {
            if (std::abs(j - num[i]) >= 2) {
                res += f[i][j];
            }
        }

        // 如果原数的第 i 位和第 i - 1 位相差小于 2，则后续不会出现 Windy 数
        if (std::abs(num[i] - num[i - 1]) < 2) break;
    }

#代码

C++
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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <iostream>
#include <cmath>
#include <vector>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 15;

int a, b, f[N][N];

std::vector<int> gen(int x) {
    std::vector<int> res;

    while (x) {
        res.push_back(x % 10);
        x /= 10;
    }

    return res;
}

int calc(int x) {
    int res = 0;
    auto num = gen(x);

    // 次高位及以前的 Windy 数的数量
    for (int i = 1; i < num.size(); i++) {
        for (int j = 1; j < 10; j++) {
            res += f[i][j];
        }
    }

    // 最高位小于原数最高位的 Windy 数的数量
    for (int i = 1; i < *num.rbegin(); i++) {
        res += f[num.size()][i];
    }

    // 最高位等于原数最高位的 Windy 数
    for (int i = num.size() - 1; i; i--) {
        for (int j = 0; j < num[i - 1]; j++) {
            if (std::abs(j - num[i]) >= 2) {
                res += f[i][j];
            }
        }

        // 如果原数的第 i 位和第 i - 1 位相差小于 2，则后续不会出现 Windy 数
        if (std::abs(num[i] - num[i - 1]) < 2) break;
    }

    return res;
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> a >> b;

    for (int i = 0; i < 10; i++) {
        f[1][i] = 1;
    }

    for (int i = 2; i <= 10; i++) {
        for (int j = 0; j < 10; j++) {
            for (int k = 0; k < 10; k++) {
                if (std::abs(j - k) >= 2) {
                    f[i][j] += f[i - 1][k];
                }
            }
        }
    }

    cout << calc(b + 1) - calc(a) << endl;

    return 0;
}