Skip to content

「SCOI2009」Windy 数

检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

#题面

#题目背景

Windy 定义了一种 Windy 数。

#题目描述

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

#输入格式

输入只有一行两个整数,分别表示 aabb

#输出格式

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

#输入输出样例

样例输入 #1

1 10

样例输出 #1

9

样例输入 #2

25 50

样例输出 #2

20

#数据范围与提示

对于 100%100\% 的测试点,1ab2×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=jk2fi1,kf_{i, j} = \sum_{|j - k| \geq 2} f_{i - 1, k}

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

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

    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 数的数量。

    35
    36
    37
    38
    // 最高位小于原数最高位的 Windy 数的数量
    for (int i = 1; i < *num.rbegin(); i++) {
    res += f[num.size()][i];
    }
  3. 计算 [3000,3578)[3000, 3578) 之间的 Windy 数的数量。

    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;
    }

#代码

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;
}