题目
谁是帕鲁
题目分析
我们需要求区间 [L, R] 中有多少个数，其数字里包含的“圈圈”总数恰好为 K。
比如数字 8 有 2 个圈，6 有 1 个圈，1 有 0 个圈。
数字范围高达 10^{12}，暴力遍历肯定会超时。这种“统计区间内满足某种性质的数”的题目，是典型的数位 DP（Digit DP）应用场景。
解题思路（数位DP）
1. 核心思想：转“枚举”为“填空”
不要把数字看成一个整体，而是把它看成几个等待填空的格子。
比如求 0 \sim 536 之间的数，其实就是准备了 3 个格子（百位、十位、个位），我们要一位一位地往里填数字。
2. 差分转化
求 [L, R] 的数量，通常转化为：
这样我们只需要编写一个函数 solve(N)，算出 0 \sim N 之间有多少个符合条件的数即可。
3. “机器人走迷宫” (DFS 设计)
我们设计一个递归函数 dfs，想象成一个机器人从最高位开始，一位一位地做决策。机器人需要记住四个关键信息（也就是 DFS 的四个参数）：
-
pos (我现在在哪？)：
表示当前正在填哪一位。比如 pos=2 代表在填百位，pos=0 代表在填个位。
-
cnt (我背包里有几个圈？)：
表示从最高位填到现在，已经累计了多少个圈圈。
- 如果最后
cnt恰好等于 K，说明找到了一个解。 - 如果中途
cnt已经超过 K，那后面不用填了，直接剪枝。
- 如果最后
-
limit (我有天花板限制吗？)：
这是数位 DP 的精髓。以 N=536 为例：
- 受限状态 (
true)：如果你在百位填了5（贴着上界填），那么十位最大只能填3。 - 自由状态 (
false)：如果你在百位填了2（比 5 小），那十位想填9都可以。 - 传递规则：只有当前位“受限”且填了最大值时，下一位才继续“受限”。
- 受限状态 (
-
lead (我是不是还在填前导零？)：
用来区分数字 0 和占位用的 0。
- 比如我们要凑三位数，数字
5实际上是005。 - 前面的两个
0是前导零，它们不应该产生圈圈。 - 中间的
0（如101）或者末尾的0是有效数字，要算 1 个圈。 - 判断规则：如果当前是前导零状态，且填了
0，则下一位继续是前导零；否则状态结束。
- 比如我们要凑三位数，数字
4. 记忆化（核心：为什么会产生大量重复？）
一句话原理： “以前算过的局面，如果条件完全一样，就不要再算一遍，直接看答案。”
(1) 哪里重复了？
想象我们要计算 [0, 9999] 里有多少个满足条件的数。
DFS 是从高位往低位填。请看下面两个不同的分支：
- 分支 A：千位填了
1（1 是 0 个圈）。- 当前状态：剩下 3 位没填，背包里有 0 个圈。
- 任务：计算后面
___(百、十、个位) 怎么填能凑够 K 个圈。
- 分支 B：千位填了
2（2 也是 0 个圈）。- 当前状态：剩下 3 位没填，背包里还是 0 个圈。
- 任务：计算后面
___(百、十、个位) 怎么填能凑够 K 个圈。
- 分支 C：千位填了
3（3 也是 0 个圈）。- 当前状态：同上...
发现了吗？
不管千位是 1、2、3 还是 5、7，只要它没带来圈圈，且没有“贴着上界”的限制（limit=false），剩下的任务是完全一模一样的！
如果没有记忆化，计算机就会把“三位数填空凑 K 个圈”这个子任务重复算很多遍。
有了 dp[pos][cnt]，算完分支 A 后，我们就把结果存在 dp[3][0] 里。等走到分支 B、C 时，发现 dp[3][0] 已经有值了，直接拿来用，瞬间结束。
(2) 什么时候才能记？
只有当 !limit && !lead 时才能记录状态。
-
为什么 limit 必须为 false？
如果 limit=true，说明你现在的填法受限于原数字（比如最高位只能填到 5），这是一种特例，不能作为通用经验传给别人。
-
为什么 lead 必须为 false？
前导零状态下，填 0 是不占位数也不加圈的，这也是特例，不能和正常的填数混淆。
(3) 时间复杂度分析
数位 DP 的效率非常恐怖，它把指数级的搜索降维成了多项式级。
-
状态总数：pos \times cnt
- pos（位数）：10^{12} 大约是 12 位，即使是
Long.MAX_VALUE也就 19 位。我们按 20 算。 - cnt（圈数）：最坏情况全是 8，19 位全是 8 也就 19 \times 2 = 38 个圈。我们按 40 算。
- 状态总数只有 20 \times 40 = 800 个左右。
- pos（位数）：10^{12} 大约是 12 位，即使是
-
单次转移成本：
- 每个状态内部我们只做一个 0 \sim 9 的循环，计算量是常数 10。
-
总复杂度：
O(\text{位数} \times \text{最大圈数} \times 10)对于本题，大约是 20 \times 40 \times 10 \approx 8000 次运算。
-
结论：
相比于暴力枚举 10^{12} 个数，数位 DP 的计算量几乎可以忽略不计，这也是为什么它能秒杀大数区间统计题。
5. 易错点：数字 0 的处理
DFS 的前导零逻辑通常会把数字 0 视为“空串”（全都是前导零，最后没填任何有效数字）。
所以 DFS 算出来的是 1 \sim N 的结果。
补救措施：在主函数里单独判断一下：数字 0 本身有 1 个圈。如果题目要求的 K=1，我们手动把答案加 1。
参考代码
import java.util.Scanner;
import java.util.Arrays;
public class Main {
// 0-9 每个数字对应的封闭图形数量
static int[] circleCost = {1, 0, 0, 0, 1, 0, 1, 0, 2, 1};
// dp数组：记忆化搜索的核心
// dp[pos][cnt] 表示：
// 剩下 pos 位没填，当前已经累计了 cnt 个圈圈，
// 在【没有限制 (limit=false)】且【没有前导零 (lead=false)】的情况下，
// 后面能凑出多少个满足最终目标 K 的数。
static long[][] dp;
// 存储把数字拆解后的每一位
static int[] digits = new int[20];
static int K; // 目标圈圈数
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long L = sc.nextLong();
long R = sc.nextLong();
K = sc.nextInt();
// 答案 = [0, R] 的数量 - [0, L-1] 的数量
System.out.println(solve(R) - solve(L - 1));
}
/**
* solve 函数：计算区间 [0, num] 中有多少个数满足条件
* 逻辑：
* 1. 它是 DFS 的启动器，负责把数字拆包。
* 2. 它负责处理 "0" 这个特殊数字（因为 DFS 里的前导零逻辑通常会忽略 0）。
*/
static long solve(long num) {
if (num < 0) return 0;
if (num == 0) return K == 1 ? 1 : 0; // 特判0
// 1. 将数字拆解到数组中 (倒序存储，比如 536 -> [6, 3, 5])
int len = 0;
long temp = num;
while (temp > 0) {
digits[len++] = (int) (temp % 10);
temp /= 10;
}
// 2. 初始化 DP 数组 (每次 solve 都需要清空，因为 K 可能会变，或者复用时清理脏数据)
// len 最大 19 (Long.MAX_VALUE)，state 最大约 19*2=38
dp = new long[len + 1][200];
for (long[] row : dp) {
// -1 表示没算过
Arrays.fill(row, -1);
}
// 3. 运行 DFS 计算 (0, num] 范围内的解
// 从最高位开始搜
// pos = len - 1 (最高位)
// currentCnt = 0 (目前 0 个圈)
// limit = true (刚开始肯定受限，因为最高位不能超过 num 的最高位)
// lead = true (刚开始肯定是前导零状态)
long ans = dfs(len - 1, 0, true, true);
// 4. DFS 算的是 [1, n] 里的满足解 (因为前导零逻辑把 00...0 过滤掉了)
// 所以我们要手动检查 0 这个数字是否满足条件 (0有1个圈)。
// 如果 0 的圈圈数 (1) 等于 K，那么 0 也是一个解，需要补上。
if (1 == K) {
ans++;
}
return ans;
}
/**
* DFS 函数含义：
* 从第 pos 位开始填空，在当前已积累 cnt 个圈、是否受限于最大值 limit、是否处于前导零 lead 的状态下，
* 【能构造出多少个符合目标 K 的后续数字后缀】。
*
* @param pos 当前处理第几位 (从高 len-1 到低 0)
* @param cnt 当前已经累计了多少个圈
* @param limit 是否受到上界限制 (true: 只能填 0~a[pos], false: 0~9 随便填)
* @param lead 是否处于前导零状态 (true: 前面全是 0)
*/
static long dfs(int pos, int cnt, boolean limit, boolean lead) {
// [剪枝]：如果当前累计圈数已经超过 K，后面怎么填都不可能等于 K 了，直接回退
if (cnt > K) return 0;
// [递归边界]：pos < 0 说明每一位都填完了
if (pos < 0) {
// 如果 lead=true，说明每一位都是 0，构成了“空串”，这在 DFS 里不应该算作一个有效数字。
// (数字 0 的逻辑我们已经在 solve 里单独处理了)
// 只有当 不是前导零 且 圈数==K 时，才返回 1
return (!lead && cnt == K) ? 1 : 0;
}
// 记忆化：只有 "无限制" 且 "非前导零" 的状态是通用的，可以查表
if (!limit && !lead && dp[pos][cnt] != -1) {
return dp[pos][cnt];
}
long res = 0;
// 确定当前位能填的上限：受限取原位，不受限取 9
int up = limit ? digits[pos] : 9;
for (int i = 0; i <= up; i++) {
// 下一位是否还是前导零：
// 必须当前是前导零，且当前位填了 0，下一位才继续是前导零
boolean nextLead = lead && (i == 0);
// 计算新的圈数：
// 如果是前导零里的 0 (比如 005 里的 0)，不产生圈数
// 否则，加上当前数字对应的圈数
int nextCnt = nextLead ? cnt : (cnt + circleCost[i]);
// 递归下一层
// limit 传递逻辑：当前 limit 为真 且 当前位选了最大值 up，下一位才受限
// lead 传递逻辑：当前 lead 为真 且 当前位选了 0，下一位才继续是前导零
res += dfs(pos - 1, nextCnt, limit && (i == up), lead && (i == 0));
}
// 记录状态
if (!limit && !lead) {
dp[pos][cnt] = res;
}
return res;
}
}
幸运年
这道题非常经典，属于数位 DP 中的 “模式匹配” 类型。
上一题我们是“数圈圈”（累加属性），这一题我们需要“找 substring”（状态跳转）。
解题思路
这道题要求统计区间 [l, r] 内包含子串 "14" 或者 "2023" 的数字个数。由于数据范围高达 10^{12}，暴力枚举不可行，我们需要使用 数位 DP。
与常见的累加数位和不同，这道题的核心难点在于：如何在填数字的过程中，判断当前是否已经凑出了目标子串？
我们可以将问题拆解为两个部分：
1. 定义状态（状态机思想）
我们需要一个变量 state 来记录“当前数字的后缀匹配到了目标字符串的哪一步”。
我们可以把匹配进度划分为 6 个状态（0 ~ 5）：
- 状态 0: 初始状态，未匹配任何有效前缀。
- 状态 1: 匹配了 "1"（可能是 "14" 的开头）。
- 状态 2: 匹配了 "2"（可能是 "2023" 的开头）。
- 状态 3: 匹配了 "20"。
- 状态 4: 匹配了 "202"。
- 状态 5 (终态): 成功！ 当前数字已经包含了 "14" 或 "2023"。一旦进入此状态，无论后面填什么，这个数都是幸运数。
2. 状态转移（预处理跳转表）
在 DFS 过程中，如果当前状态是 4（即后缀是 "202"），下一位填了 1，状态应该变成多少？
此时数字后缀变成了 "2021"，它破坏了 "2023" 的进程，但它以 "1" 结尾，所以应该跳回 状态 1。
如果你填了个 0，变成 "2020"，状态该变去哪？ 显然，"2020" 的后缀是 "20"，所以应该回到 状态 3。
为了避免在 DFS 里写复杂的 if-else 判断，我们可以预处理一个跳转表 trans[state][digit]。
- 枚举当前所有状态（
0~5）和下一位可能填的所有数字（0~9）。 - 利用字符串模拟拼接，计算新字符串的最长有效后缀对应哪个状态。
- DFS 时直接查表即可，代码会极其清爽。
3. 数位 DP 模板
套用通用的数位 DP 记忆化搜索模板：
pos: 当前处理的数位。state: 当前的匹配状态。limit: 最高位限制。lead: 前导零标记（注意：前导零状态下填 0，状态应保持为 0，不应进入匹配逻辑）。
参考代码
import java.util.*;
public class Main {
// 状态定义：
// 0: 无匹配
// 1: "1"
// 2: "2"
// 3: "20"
// 4: "202"
// 5: 已包含 "14" 或 "2023" (成功状态)
// 预处理跳转表：trans[当前状态][新填入的数字] = 下一个状态
static int[][] trans = new int[6][10];
// dp[pos][state]：记忆化数组
// pos: 剩余位数 (最大约19位)
// state: 当前匹配状态 (0~5)
static long[][] dp = new long[20][6];
// 存储拆解后的数字每一位
static int[] nums = new int[20];
// --- 静态代码块：程序启动时先计算好跳转表 ---
static {
// 定义每个状态代表的字符串含义
// 0:空, 1:"1", 2:"2", 3:"20", 4:"202", 5:成功
String[] patterns = {"", "1", "2", "20", "202", "SUCCESS"};
for (int s = 0; s < 5; s++) { // 遍历未成功的状态 0~4
for (int d = 0; d <= 9; d++) {
// 模拟：旧状态字符串 + 新数字
String currentStr = patterns[s] + d;
// 1. 判断是否达成目标 (包含 14 或 2023)
if (currentStr.contains("14") || currentStr.contains("2023")) {
trans[s][d] = 5; // 跳转到成功状态
continue;
}
// 2. 如果没成功，寻找最长匹配后缀，决定回退到哪个状态
// 检查顺序必须从长到短 (202 -> 20 -> 2 -> 1 -> 0)
if (currentStr.endsWith("202")) trans[s][d] = 4;
else if (currentStr.endsWith("20")) trans[s][d] = 3;
else if (currentStr.endsWith("2")) trans[s][d] = 2;
else if (currentStr.endsWith("1")) trans[s][d] = 1;
else trans[s][d] = 0; // 没匹配到任何前缀，回到起点
}
}
// 状态 5 是“黑洞状态”：一旦成功，后面填什么依然是成功
for (int d = 0; d <= 9; d++) trans[5][d] = 5;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long l = sc.nextLong();
long r = sc.nextLong();
// 差分思想：[l, r] 的答案 = [0, r] - [0, l-1]
System.out.println(solve(r) - solve(l - 1));
}
/**
* 计算区间 [0, n] 内有多少个幸运数字
*/
static long solve(long n) {
if (n <= 0) return 0;
// 1. 拆位 (倒序存储，nums[0]是最低位)
String s = String.valueOf(n);
int len = s.length();
for (int i = 0; i < len; i++) {
nums[len - 1 - i] = s.charAt(i) - '0';
}
// 2. 初始化 DP
for (int i = 0; i < len; i++) Arrays.fill(dp[i], -1);
// 3. 启动 DFS
// 从最高位(len-1)开始，初始状态为0，受限，有前导零
return dfs(len - 1, 0, true, true);
}
/**
* DFS 核心函数
*
* @param pos 当前处理第几位 (从高向低)
* @param state 当前匹配到了哪个阶段 (0~5)
* @param limit 是否受到上界限制
* @param lead 是否处于前导零状态
* @return 满足条件的后缀数量
*/
static long dfs(int pos, int state, boolean limit, boolean lead) {
// 递归终点：填完所有位
if (pos < 0) {
// 如果最终状态是 5，说明找到了幸运数，返回 1，否则 0
return state == 5 ? 1 : 0;
}
// 记忆化：只有通用状态 (无限制且无前导零) 才能查表
if (!limit && !lead && dp[pos][state] != -1) return dp[pos][state];
long res = 0;
int up = limit ? nums[pos] : 9; // 确定枚举上界
for (int i = 0; i <= up; i++) {
int nextState;
// 处理状态转移
if (lead) {
// 如果是前导零状态
if (i == 0) {
nextState = 0; // 填 0 依然是前导零，状态不变
} else {
// 刚结束前导零，相当于从状态 0 开始填入数字 i
nextState = trans[0][i];
}
} else {
// 正常状态转移，查表
nextState = trans[state][i];
}
// 递归下一层
// nextLead: 当前是前导零 且 当前填了 0，下一位才继续是前导零
boolean nextLead = lead && (i == 0);
res += dfs(pos - 1, nextState, limit && (i == up), nextLead);
}
// 记录通用状态
if (!limit && !lead) dp[pos][state] = res;
return res;
}
}
windy数
这道题是数位 DP 中处理 “相邻数位约束” 的最经典例题。
上一题《幸运年》是看 “一串数”（子串匹配），这道题是看 “两个数”（相邻绝对值差）。
解题思路
这道题要求统计区间 [a, b] 内满足特定性质（相邻位差 \ge 2）的数字个数。由于数据范围达到 2 \times 10^9，直接遍历每个数字判断会超时。这类“统计区间内满足位约束的数”的问题，是 数位 DP 的标准应用场景。
1. 核心思想：按位填空
我们可以把问题转化为：假设有 N 个空的格子（代表数字的每一位），我们从高位到低位，一位一位地尝试填入数字 0 \sim 9。在填写的过程中，我们需要遵循题目给出的约束。
题目定义 Windy 数有两个条件：
- 无前导零（数位 DP 天然处理这一点）。
- 相邻位差值 \ge 2：即 |A_i - A_{i+1}| \ge 2。
这意味着，当我们站在当前位 pos 准备填数字时，我们必须知道前一位填了什么。
比如：如果前一位填了 5，那当前位只能填 0, 1, 2, 3 （|x-5| \ge 2 \to x \le 3） 或者 7, 8, 9 （|x-5| \ge 2 \to x \ge 7）。4, 5, 6 都不能填。
2. 差分转化
求区间 [a, b] 的数量，通常转化为求前缀和：
其中 solve(n) 计算的是 [1, n] 范围内有多少个 Windy 数。
3. 状态设计 (DFS 参数)
为了保证填进去的数字符合要求，我们在搜索（DFS）时需要维护以下关键信息：
pos(当前位置)：当前正在填第几位（从高位往低位填）。pre(上一位数字)：上一位填的数字是多少（0-9），这是本题的关键。因为能不能填某个数，取决于它和 上一位 数字的差值是否 \ge 2。limit(上界限制)：数位 DP 的通用参数。- 如果上一位是贴着上界填的（比如 N=536，百位填了 5），那么当前位只能填 0 \sim 3。
- 如果上一位没贴上界（比如百位填了 4），当前位可以随便填 0 \sim 9。
lead(前导零标记)：用于处理前导零。- 题目要求不含前导零，且前导零不参与“相邻差”的计算。
- 例如数字
9，在计算机看来可能是009。前两个0是前导零，它们与后面的9不需要满足 |0-9| \ge 2。只有从第一个非 0 数字开始，才需要遵守相邻位约束。
4. 状态转移
- 当前处于前导零阶段 (
lead = true)：- 如果填
0：这一位还是前导零，下一位继续lead=true。此时“上一位数字”依然不存在（我们用 -2 表示）。 - 如果填
1~9：前导零结束，下一位lead=false。这一位数字将作为下一位的pre。
- 如果填
- 当前处于正常填数阶段 (
lead = false)：- 枚举所有数字 d，只有当 |d - pre| \ge 2 时才能填。
5. 记忆化
我们用 dp[pos][pre] 记录状态：“剩下 pos 位，上一位是 pre 时，有多少种填法”。
- 注意：只有在 无限制 (
!limit) 且 非前导零 (!lead) 的情况下，状态才是通用的，可以记录下来供后续复用。
参考代码
import java.util.*;
public class Main {
// dp[pos][pre]
// pos: 剩余位数 (最大 10 位，开 12 足够)
// pre: 上一位填的数字 (0-9)
static long[][] dp = new long[12][10];
// 存储拆解后的数字
static int[] nums = new int[12];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long a = sc.nextLong();
long b = sc.nextLong();
// 利用前缀和思想：[a, b] 的数量 = [1, b] 的数量 - [1, a-1] 的数量
System.out.println(solve(b) - solve(a - 1));
}
/**
* 计算 [1, n] 范围内 Windy 数的个数
*/
static long solve(long n) {
if (n == 0) return 0;
// 1. 拆位 (倒序存储)
int len = 0;
long temp = n;
while (temp > 0) {
nums[len++] = (int) (temp % 10);
temp /= 10;
}
// 2. 初始化 DP (每次都要清空，因为 pre 的依赖关系在不同题目中不同)
for (long[] row : dp) Arrays.fill(row, -1);
// 3. 启动 DFS
// 从最高位 (len-1) 开始填
// pre 初始为 -2，表示前面还没有填过任何有效数字
return dfs(len - 1, -2, true, true);
}
/**
* DFS 数位搜索核心函数
*
* @param pos 当前处理第几位 (从高 len-1 到低 0)
* @param pre 前一位填的数字 (如果还在前导零阶段，用 -2 标记)
* @param limit 是否受到上界限制 (true: 只能填 0~nums[pos])
* @param lead 是否处于前导零状态 (true: 还没填过非 0 数字)
* @return 当前状态下能凑出的 Windy 数个数
*/
static long dfs(int pos, int pre, boolean limit, boolean lead) {
// [递归终点] 填完所有位
if (pos < 0) {
// 如果 lead=true，说明整个数是 0，不符合题目 [1, R] 的范围要求，返回 0
// 否则返回 1 (找到一个有效 Windy 数)
return lead ? 0 : 1;
}
// [记忆化] 只有通用状态 (!limit && !lead) 才能复用
// pre >= 0 保证了不是前导零阶段 (前导零时 pre=-2)
if (!limit && !lead && pre >= 0 && dp[pos][pre] != -1) {
return dp[pos][pre];
}
long res = 0;
int up = limit ? nums[pos] : 9;
for (int i = 0; i <= up; i++) {
// --- 分情况讨论 ---
if (lead) {
// 情况 A: 还在前导零阶段
if (i == 0) {
// 当前位填 0 -> 继续保持前导零，pre 依然是 -2
res += dfs(pos - 1, -2, limit && (i == up), true);
} else {
// 当前位填 1-9 -> 前导零结束，pre 变成当前数字 i
// 注意：这是第一位有效数字，不需要和前面比较差值
res += dfs(pos - 1, i, limit && (i == up), false);
}
} else {
// 情况 B: 正常填数阶段
// 必须满足 Windy 数定义：相邻差 >= 2
if (Math.abs(i - pre) >= 2) {
res += dfs(pos - 1, i, limit && (i == up), false);
}
}
}
// [记录状态]
if (!limit && !lead && pre >= 0) {
dp[pos][pre] = res;
}
return res;
}
}
