题目描述：
给你正整数 low ，high 和 k 。
如果一个数满足以下两个条件，那么它是 美丽的 ：
- 偶数数位的数目与奇数数位的数目相同。
- 这个整数可以被
k 整除。
请你返回范围 [low, high] 中美丽整数的数目。
数据范围：
$0 \lt low \le high \le 10^9; 0\lt k \le 20$
题解：
数位 DP：用来解决一类特定问题，这种问题比较好辨认，一般具有这几个特征：
- 要求统计满足一定条件的数的数量（即，最终目的为计数）；
- 这些条件经过转化后可以使用「数位」的思想去理解和判断；
- 输入会提供一个数字区间（有时也只提供上界）来作为统计的限制；
- 上界很大（比如 $10^{18}$ )，暴力枚举验证会超时。
数位 DP 的基本原理：
考虑人类计数的方式，最朴素的计数就是从小到大开始依次加一。但我们发现对于位数比较多的数，这样的过程中有许多重复的部分。例如，从 $7000 $ 数到 $7999$ 、从 $8000$ 数到 $8999$ 、和从 $9000$ 数到 $9999$ 的过程非常相似，它们都是后三位从 $000$ 变到 $999$ ，不一样的地方只有千位这一位，所以我们可以把这些过程归并起来，将这些过程中产生的计数答案也都存在一个通用的数组里。此数组根据题目具体要求设置状态，用递推或 DP 的方式进行状态转移。
基础状态，枚举到了第几位 $step$ 。针对不同的问题需要记录不同的状态。
而且也需要注意，只有当前位不受到上界限制才能记录。只有当前位不受到限制时，后面的位才能从 $0000$ 到 $9999$ 。
而且数位dp经常会用到计数技巧，比如把一个区间内的答案拆成两部分相减， $ans[l,r] = ans[0,r] - ans[0,l - 1]$ 。
使用记忆化搜索实现比较简单。模板为
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
|
int dfs(int step, int state, bool is_limit, bool is_lead)
{
if (step == n)
return !is_lead;
if (!is_limit && !is_lead && dp[step][val][diff] != -1)
return dp[step][val][diff];
int ans = 0;
if (is_lead)
ans = dfs(step + 1, state, false, true);
int up = is_limit ? s[step] - '0' : 9;
for (int i = is_lead; i <= up; ++i)
{
ans += dfs(step + 1, state, is_limit && i == up, false);
}
if (!is_limit && !is_lead)
dp[step][state][diff] = ans;
return ans;
}
dfs(0, 0, true, true);
|
注意需要搞两遍，其实可以再搞一个函数嵌套一下。
而且，使用奇偶位数个数差， $diff$ 。并且 diff = diff + (i % 2) * 2 - 1，刚好满足了 $i$ 为奇数时，加 $1$ ， $i$ 为偶数时，减 $1$ 。
代码：
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
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int n, k;
int dp[10][21][10 * 2 + 1];
string s;
int dfs(int step, int val, int diff, bool is_limit, bool is_lead)
{
if (step == n)
return !is_lead && val == 0 && diff == n;
if (!is_limit && !is_lead && dp[step][val][diff] != -1)
return dp[step][val][diff];
int ans = 0;
if (is_lead)
ans = dfs(step + 1, val, diff, false, true);
int up = is_limit ? s[step] - '0' : 9;
for (int i = is_lead; i <= up; ++i)
{
ans += dfs(step + 1, (val * 10 + i) % k, diff + (i % 2) * 2 - 1, is_limit && i == up, false);
}
if (!is_limit && !is_lead)
dp[step][val][diff] = ans;
return ans;
}
int numberOfBeautifulIntegers(int low, int high, int _k)
{
s = to_string(high);
n = s.length();
k = _k;
memset(dp, -1, sizeof(dp));
int ans1 = dfs(0, 0, n, true, true);
s = to_string(low - 1);
n = s.length();
memset(dp, -1, sizeof(dp));
int ans2 = dfs(0, 0, n, true, true);
return ans1 - ans2;
}
};
|