当前位置：首页 > article >正文

洛谷题目： P2188 小Z的 k 紧凑数（本题较难，省选-难度）题解

article 2025/3/5 0:25:21

题目传送门：

P2188 小Z的 k 紧凑数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

前言：

本题目只有动态Dp的知识点，看似非常简单，（~~我觉得非常的简单，1小时写完了~~），这一期作者将详细讲解，希认真看完！

#题目核心问题：

给定区间 $[l,r]$ 和整数 $k$ , 需要找出该区间内相邻两个数字查的绝对值不超过 $k$ 的整数（即 $k$ 紧凑数）的个数。

##关键思路：

1、状态设计：

1.1、我们首先定义： $dp[p][pe][s][N]$ 来表示一种状态。其中， $p$ 表示当前处理到数字的第几位（从高位到低位，例如对于一个四位数， $p$ 从3开始到0）； $pe$ 表示前一位数字； $s$ 表示当前位是否收到限制（如果前面几位都取到了上界，那么当前位取值就受到了限制）； $N$ 表示前面是否已经有数字了（用于处理前导零的情况）。

1.2、假设，对于数字1234，当处理到百位时， $p=2$ ，如果前面两位都取到了上界（我们假设上界就是1234），那么 $s=1$ ，如果已经确定了千位有数字（不为零），那么 $N=1$

2、边界条件：

1.1、当 $p==-1$ 时，表示数字的所有位数都处理完毕。此时如果 $N$ 为真，则返回1，表示找到了一个符合条件的数；否则返回0。

3、状态转移：

1.1、对于当前位 $p$ ，其取值范围取决于 $s$ 。如果 $s$ 为真，那么当前最大只能娶到给定数字对应位的值。

1.2、对于每一个可能的取值 $i$ ，如果前面已经有数字（ $N$ 为真），则需要判断 $|i-pe|\leq k$ 是否成立。如果成立，递归调用 $dfs$ 函数处理下一位，并将结果累加到 $ans$ 中。乳沟前面还是没有数字（ $N$ 为假），则当 $i>0$ 时，递归调用 $dfs$ 函数处理下一位，并将结果累加到 $ans$ 中。

1.3、举个例子，假设当前处理到一个三位数的十位，前一位（百位）是 3 ， $k=2$ ，如果 $s$ 允许的话，十位可以取1~5（因为 $|1-3|=2,|5-3|=2$ ）），对于每个符合条件的取值，我们将继续递归处理个位。

4、记忆化优化：

1.1、我们在搜索过程当中，如果当前状态（ $p,pe,s,N$ ）已经计算过

即（ $dp[p][pe][s][N]!=-1$ ），并且当前状态将不受上界限制（!s）且前面已经有了数字（N），则直接返回以计算的结果，避免重复的计算。

###实现代码步骤：

1、输入处理：

我们读入区间 $[l,r]$ 和 $k$ 。

2、数位分离：

对于要处理的数字n（在计算小于等于 $n$ 的 $k$ 紧凑数时），我们通过不断驱魔和除法操作，将其每一位分离出来，存储在数组 $num$ 当中。

3、调用记忆化搜索函数：

我们调用 $sovle$ 函数，函数通过调用 $dfs$ 函数来计算小于等于 $n$ 的 $k$ 紧凑数的个数。

4、计算区间结果：

1.1、最终通过 $solve(r,k)-solve(l-1,k)$ 饿到区间 $[l,r]$ 内 $k$ 紧凑书的个数。这是因为 $sovle(n,k)$ 计算的是小于等于 $n$ 的 $k$ 紧凑数个数，相减后就得到了区间 $[l,r]$ 内的个数。

####代码：

#include <bits/stdc++.h>
using namespace std;
long long dp[20][10][2][2];
int num[20];
long long dfs(int p, int pe, int s, int N, int k) {
    if (p == -1) return N;
    if (!s && N && dp[p][pe][s][N]!= -1)
        return dp[p][pe][s][N];
    int u = s? num[p] : 9;
    long long a = 0;
    for (int i = 0; i <= u; ++i) {
        if (N) {
            if (abs(i - pe) <= k) {
                a += dfs(p - 1, i, s && i == u, true, k);
            }
        } else {
            a += dfs(p - 1, i, s && i == u, i > 0, k);
        }
    }
    if (!s && N)
        dp[p][pe][s][N] = a	;
    return a;
}
long long s(long long n, int k) {
    int len = 0;
    while (n) {
        num[len++] = n % 10;
        n /= 10;
    }	
    return dfs(len - 1, 0, true, false, k);
}
int main() {
    long long l, r;
    int k;
    cin >> l >> r >> k;
    memset(dp, -1, sizeof(dp));
    cout << s(r, k) - s(l - 1, k) << endl;
    return 0;
}