形式化题目

给定两个正整数 $A, B$（$1 \le A \le B \le 2 \times 10^9$），统计闭区间 $[A, B]$ 内有多少个正整数 $x$，其十进制表示 $x = \overline{d_k d_{k-1} \dots d_1}$ 满足：

1. 无前导零，即最高位 $d_k \ne 0$；
2. 任意相邻两个数位的绝对差至少为 $2$，即对所有 $1 \le i < k$，均有 $|d_{i+1} - d_i| \ge 2$。

数位 DP 解法

思路

根据区间计数的可减性，闭区间 $[A, B]$ 内的答案可以转化为前缀计数的差值：

1. 朴素枚举的瓶颈

若暴力枚举区间内的每一个整数并拆位验证，总次数可达 $O((B - A + 1) \log_{10} B)$。当 $B \approx 2 \times 10^9$ 时，运算量达到 $10^{10}$ 级别，远超 1 秒的时限。

2. 数位 DP 建模

一个数字是否为 Windy 数，只由其从高位到低位的连续数字决定，且仅依赖相邻上一位所填的数字。这具有极强的无后效性与重复子结构特征。

我们采用记忆化搜索从高位到低位依次确定数位，设计状态函数：

• $\text{pos}$：当前正考虑填第 $\text{pos}$ 位（从左到右，从最高位 $0$ 到最低位 $L-1$）；
• $\text{prev}$：前一位所填的具体数字（若尚未开始填入有效最高位，则设为 $\text{None}$）；
• $\text{is\_limit}$：布尔值，表示前面已填的数位是否都紧贴上限 $n$。若为真，则当前位至多只能填到 $n$ 的当前位数值；若为假，则可自由填 $0 \sim 9$；
• $\text{is\_num}$：布尔值，表示前面是否已经填入过非零数字（即是否已经跳过了前导零阶段）。

3. 状态转移与决策

根据是否已经进入有效数字阶段分两种情况转移：

1. 尚未填入有效数字（$\text{is\_num} = \text{False}$）：
   • 可以继续跳过当前位，保持前导零：递归至 $\text{dfs}(\text{pos} + 1, \text{None}, \text{False}, \text{False})$；
   • 可以在当前位填入首个非零数字 $d \in [1, \text{up}]$，作为数字的最高位：递归至 $\text{dfs}(\text{pos} + 1, d, \text{is\_limit} \land (d = \text{up}), \text{True})$。
2. 已经填入有效数字（$\text{is\_num} = \text{True}$）：
   • 枚举当前位数字 $d \in [0, \text{up}]$；
   • 检查相邻约束：仅当 $|d - \text{prev}| \ge 2$ 时才为合法转移，递归至 $\text{dfs}(\text{pos} + 1, d, \text{is\_limit} \land (d = \text{up}), \text{True})$。

4. 转移过程可视化

以下展示在填数字时，前导零状态与有效数字状态之间的流转逻辑：

graph TD
    Start["开始 (pos=0, prev=None, is_num=False)"]
    Skip["跳过当前位 (仍为前导零, is_num=False)"]
    StartNum["填入最高位 d ∈ [1, up] (is_num=True)"]
    NextDigit["填入下一位 d ∈ [0, up] 且 |d - prev| >= 2"]
    ValidEnd["到达末尾: 计入合法方案 (+1)"]

    Start -->|"继续不填"| Skip
    Start -->|"选填 1..up"| StartNum
    Skip -->|"继续不填"| Skip
    Skip -->|"选填 1..up"| StartNum
    StartNum -->|"枚举下一位"| NextDigit
    NextDigit -->|"枚举下一位"| NextDigit
    NextDigit -->|"pos == L"| ValidEnd
    StartNum -->|"pos == L (一位数)"| ValidEnd

代码

Python 版：

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 20:26
# update_at: 2026-10-04 13:25

from functools import cache
import sys


def count_windy(n: int) -> int:
    """统计 [1, n] 内相邻数位差绝对值 >= 2 的正整数个数。"""
    if n <= 0:
        return 0
    digits = [int(c) for c in str(n)]

    @cache
    def dfs(pos: int, prev: int | None, is_limit: bool, is_num: bool) -> int:
        if pos == len(digits):
            return int(is_num)

        up = digits[pos] if is_limit else 9
        ans = 0
        if not is_num:
            # 这一位不选数字，继续跳过前导零
            ans += dfs(pos + 1, None, False, False)
            # 这一位选择作为最高位（不能填 0）
            for d in range(1, up + 1):
                ans += dfs(pos + 1, d, is_limit and d == up, True)
        else:
            # 已经有前缀数字，下一位必须与 prev 差绝对值 >= 2
            for d in range(up + 1):
                if abs(d - prev) >= 2:
                    ans += dfs(pos + 1, d, is_limit and d == up, True)
        return ans

    return dfs(0, None, True, False)


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    a, b = next(data), next(data)
    print(count_windy(b) - count_windy(a - 1))


if __name__ == "__main__":
    solve()

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 10:46
 * update_at: 2026-10-05 10:46
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXLEN = 12;

// memo[pos][last + 1]：从第 pos 位起在不受上限约束时能填出的方案数，
// 第二维用 last + 1 把小标，使 last = -1（还处于前导零阶段）正好落在下标 0；-1 表示未计算。
ll memo[MAXLEN][11];
int digit[MAXLEN]; // digit[i] 表示上限 n 从高到低第 i 位的数字
int len;           // 上限 n 的十进制位数

// 数位 DP（记忆化搜索）：从高位往低位逐位填数。
// pos：当前要填的位下标；last：上一位填的数字，-1 表示还没填过有效数字（仍在前导零阶段）；
// is_limit：前面已填的位是否都紧贴上限；is_num：是否已经填过有效数字。
// 返回从 pos 位起能得到的合法方案数，pos == len 时只有 is_num 为真才算一个正整数。
ll dfs(int pos, int last, bool is_limit, bool is_num) {
    if (pos == len) {
        return is_num ? 1 : 0;
    }

    // 只有不受上限约束的状态能复用；此时 last 与 is_num 的取值一一对应。
    if (!is_limit && memo[pos][last + 1] != -1) {
        return memo[pos][last + 1];
    }

    int up = is_limit ? digit[pos] : 9;
    ll res = 0;
    if (!is_num) {
        // 还处于前导零阶段：这一位可以继续空着，仍是前导零。
        res += dfs(pos + 1, -1, false, false);
        // 也可以在这一位填首个非零数字，作为这个数的最高位。
        for (int d = 1; d <= up; d++) {
            res += dfs(pos + 1, d, is_limit && d == up, true);
        }
    } else {
        // 已经有前缀数字：当前位必须与上一位相差至少 2。
        for (int d = 0; d <= up; d++) {
            if (abs(d - last) >= 2) {
                res += dfs(pos + 1, d, is_limit && d == up, true);
            }
        }
    }

    if (!is_limit) {
        memo[pos][last + 1] = res;
    }
    return res;
}

// 统计 [1, n] 内 Windy 数的个数。
ll count_windy(ll n) {
    if (n <= 0) {
        return 0;
    }

    ll tmp[MAXLEN]; // 先按低位到高位拆位，再翻转成高位到低位
    int l = 0;
    while (n > 0) {
        tmp[l] = n % 10;
        n /= 10;
        l++;
    }
    len = l;
    for (int i = 0; i < len; i++) {
        digit[i] = tmp[len - 1 - i];
    }

    // 只清理本次实际会用到的位置，last + 1 的取值范围是 0..10。
    for (int i = 0; i < len; i++) {
        for (int j = 0; j <= 10; j++) {
            memo[i][j] = -1;
        }
    }

    return dfs(0, -1, true, false);
}

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

    ll A, B;
    cin >> A >> B;

    // 区间计数可减：ans(A, B) = count(B) - count(A - 1)。
    cout << count_windy(B) - count_windy(A - 1) << endl;

    return 0;
}

复杂度

• 时间复杂度：数字长度 $L = \lfloor \log_{10} B \rfloor + 1 \le 10$。状态四元组 $(\text{pos}, \text{prev}, \text{is\_limit}, \text{is\_num})$ 的不同组合数不超过 $10 \times 11 \times 2 \times 2 = 440$ 个，每次转移仅需枚举 $0 \sim 9$ 共 10 个数字。总操作次数在 $10^3 \sim 10^4$ 级别，运行时间 $< 20\text{ ms}$，远低于 $1000\text{ ms}$。
• 空间复杂度：递归深度至多为 $L \le 10$，记忆化哈希缓存最多容纳数百个键值对，额外空间开销 $< 1\text{ MB}$，远低于 $128\text{ MB}$。

总结

Windy 数是数位 DP 的经典问题。解决此类问题的关键结构是：

1. 用前缀差分 $[A, B] \to [1, B] - [1, A - 1]$ 消除双侧边界约束；
2. 采用记忆化搜索（DFS）自顶向下逐位确定数位，借助 is_limit 控制上界，借助 is_num 精确处理前导零与数字长度变化；
3. 将上一位的数字作为 prev 传入状态，完美刻画相邻位差值不小于 2 的局部合法性。