手机

东北三宝是指哪三宝（东北三宝是指哪三宝?）

年轻人倡导“数字解毒” 美国功能机、翻盖机又火了

数位dp部分题解

2023-08-28 10:52:38 来源：博客园

前言

最近学了一种新的数位dp的状态表示，打算应用到以前做过的数位dp的题目。如果我们对数$N$进行数位dp，以前的状态定义$f(i,j)$表示所有数位大小为$i$且最高位是数字$j$的数的个数，如果还有其他约束条件那么再补充相应的状态即可。而新的状态定义则是$f(i,1)$和$f(i,0)$，其中$f(i,1)$表示所有数位大小为$i$且值不超过$N \bmod 10^i$的数的数量，相应的$f(i,0)$表示所有数位大小为$i$且值超过$N \bmod 10^i$的数的数量。其中$N \bmod 10^i$表示$N$在十进制下的最低有效$i$位数字构成的值，例如$123456789$的最低有效$6$位数字构成的值就是$456789$。

下面通过几道题目来运用这种新的做法。

数字游戏

科协里最近很流行数字游戏。

(资料图片仅供参考)

某人命名了一种不降数，这种数字必须满足从左到右各位数字呈非下降关系，如 $123$，$446$。

现在大家决定玩一个游戏，指定一个整数闭区间 $[a,b]$，问这个区间内有多少个不降数。

输入格式

输入包含多组测试数据。

每组数据占一行，包含两个整数 $a$ 和 $b$。

输出格式

每行给出一组测试数据的答案，即 $[a,b]$ 之间有多少不降数。

数据范围

$1 \le a \le b \le 2^{31}-1$

输入样例：

1 91 19

输出样例：

解题思路

定义状态$f(i,j,k)$满足以下条件的整数$n$的数量：

$n$的数位大小为$i$，$0 \leq n < 10^i$。
若$n \leq N \bmod 10^i$，则$j=1$；否则$j=0$。
$n$的最高位是数字$k$。
$n$从左到右各位数字呈非递降。

对于确定的状态$f(i,j,k)$，我们可以枚举数位是$i+1$的数的最高位是哪个数字（记作$u$）来转移到数位大小是$i+1$的状态，状态转移方程就是$$f(i,j,k) \longrightarrow f(i+1,\ u < p_i \ \operatorname{or} \ u = p_i \ \operatorname{and} \ j, \ u) \quad (u \leq k)$$

其中$p_i$表示的是$N$在十进制下从低位（第$0$位）开始的第$i$位上的数字。然后再考虑一下是否需要处理前导$0$的情况，可以发现包含前导$0$并不会影响答案，因为包含前导$0$的数仍然满足从左到右各位数字呈非下降关系。因此最终答案就是$\sum\limits_{i=0}^{9}{f(sz,1,i)}$，其中$sz$是$N$在十进制下的数位个数。

AC代码如下，时间复杂度为$O(10^2 \cdot \log{N})$：

1 #include  2 using namespace std; 3  4 const int N = 12; 5  6 int f[N][2][10]; 7 int p[N], sz; 8  9 int get(int x) {10     if (!x) return 1;11     sz = 0;12     while (x) {13         p[sz++] = x % 10;14         x /= 10;15     }16     memset(f, 0, sizeof(f));17     for (int i = 0; i <= 9; i++) {18         f[1][i <= p[0]][i]++;19     }20     for (int i = 1; i < sz; i++) {21         for (int j = 0; j <= 1; j++) {22             for (int k = 0; k <= 9; k++) {23                 for (int u = 0; u <= k; u++) {24                     f[i + 1][u < p[i] || u == p[i] && j][u] += f[i][j][k];25                 }26             }27         }28     }29     int ret = 0;30     for (int i = 0; i <= 9; i++) {31         ret += f[sz][1][i];32     }33     return ret;34 }35 36 int main() {37     int a, b;38     while (~scanf("%d %d", &a, &b)) {39         printf("%d\n", get(b) - get(a - 1));40     }41     42     return 0;43 }

Windy数

Windy 定义了一种 Windy 数：不含前导零且相邻两个数字之差至少为 $2$ 的正整数被称为 Windy 数。

Windy 想知道，在 $A$ 和 $B$ 之间，包括 $A$ 和 $B$，总共有多少个 Windy 数？

输入格式

共一行，包含两个整数 $A$ 和 $B$。

输出格式

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

数据范围

$1 \le A \le B \le 2 \times 10^9$

输入样例1：

1 10

输出样例1：

输入样例2：

25 50

输出样例2：

解题思路

定义状态$f(i,j,k)$满足以下条件的整数$n$的数量：

$n$的数位大小为$i$，$0 \leq n < 10^i$。
若$n \leq N \bmod 10^i$，则$j=1$；否则$j=0$。
$n$的最高位是数字$k$。
$n$的所有相邻数位上的数相差至少为$2$。

状态转移方程为$$f(i,j,k) \longrightarrow f(i+1,\ u < p_i \ \operatorname{or} \ u = p_i \ \operatorname{and} \ j, \ u) \quad (|u - k| \geq 2)$$

这里就需要处理前导$0$的情况，这是因为前导$0$可能会使得数不满足相邻两个数字之差至少为$2$这个条件，比如$15$是满足条件的，而$015$就不满足条件了。为了避免前导$0$的情况，这时我们只需分别考虑$1 \sim sz$每一个数位大小，统计最高位的数字不是$0$的情况即可，有$\sum\limits_{i=1}^{sz}{\sum\limits_{j=1}^{9}{f(i,1,j)}}$。除此之外，当数位大小不足$sz$，即$i < sz$时，我们默认往高位补$0$（并非添加前导$0$），这时不管最低$i$位怎么填数字，整个数都不会超过$N$，因此还需要加上$\sum\limits_{i=1}^{sz-1}{\sum\limits_{j=1}^{9}{f(i,0,j)}}$。因此最终答案就是$$\sum\limits_{i=1}^{sz}{\sum\limits_{j=1}^{9}{f(i,1,j)}} + \sum\limits_{i=1}^{sz-1}{\sum\limits_{j=1}^{9}{f(i,0,j)}}$$

AC代码如下，时间复杂度为$O(10^2 \cdot \log{N})$：

1 #include  2 using namespace std; 3  4 const int N = 15; 5  6 int f[N][2][10]; 7 int p[N], sz; 8  9 int get(int x) {10     if (!x) return 0;11     sz = 0;12     while (x) {13         p[sz++] = x % 10;14         x /= 10;15     }16     memset(f, 0, sizeof(f));17     for (int i = 0; i <= 9; i++) {18         f[1][i <= p[0]][i]++;19     }20     for (int i = 1; i < sz; i++) {21         for (int j = 0; j <= 1; j++) {22             for (int k = 0; k <= 9; k++) {23                 for (int u = 0; u <= 9; u++) {24                     if (abs(k - u) >= 2) f[i + 1][u < p[i] || u == p[i] && j][u] += f[i][j][k];25                 }26             }27         }28     }29     int ret = 0;30     for (int i = 1; i <= sz; i++) {31         for (int j = 1; j <= 9; j++) {32             ret += f[i][1][j];33             if (i < sz) ret += f[i][0][j];34         }35     }36     return ret;37 }38 39 int main() {40     int a, b;41     scanf("%d %d", &a, &b);42     printf("%d", get(b) - get(a - 1));43     44     return 0;45 }

数字游戏 II

由于科协里最近真的很流行数字游戏。

某人又命名了一种取模数，这种数字必须满足各位数字之和 $mod\ N$ 为 $0$。

现在大家又要玩游戏了，指定一个整数闭区间 $[a.b]$，问这个区间内有多少个取模数。

输入格式

输入包含多组测试数据，每组数据占一行。

每组数据包含三个整数 $a,b,N$。

输出格式

对于每个测试数据输出一行结果，表示区间内各位数字和 $mod\ N$ 为 $0$ 的数的个数。

数据范围

$1 \le a,b \le 2^{31}-1$,$1 \le N < 100$

输入样例：

1 19 9

输出样例：

解题思路

定义状态$f(i,j,k)$满足以下条件的整数$n$的数量：

$n$的数位大小为$i$，$0 \leq n < 10^i$。
若$n \leq N \bmod 10^i$，则$j=1$；否则$j=0$。
$n$的各位数字之和模$m$为$k$。

状态转移方程为$$f(i,j,k) \longrightarrow f\left(i+1,\ u < p_i \ \operatorname{or} \ u = p_i \ \operatorname{and} \ j, \ (u+k) \bmod m\right)$$

可以发现不需要处理前导$0$的情况，因为对$0$求和后并不会影响模$m$的结果。因此最终答案就是$f(sz, 1, 0)$。

AC代码如下，时间复杂度为$O(10 \cdot m \cdot \log{N})$：

1 #include  2 using namespace std; 3  4 const int N = 15, M = 110; 5  6 int a, b, m; 7 int f[N][2][M]; 8 int p[N], sz; 9 10 int get(int x) {11     if (!x) return 1;12     sz = 0;13     while (x) {14         p[sz++] = x % 10;15         x /= 10;16     }17     memset(f, 0, sizeof(f));18     for (int i = 0; i <= 9; i++) {19         f[1][i <= p[0]][i % m]++;20     }21     for (int i = 1; i < sz; i++) {22         for (int j = 0; j <= 1; j++) {23             for (int k = 0; k < m; k++) {24                 for (int u = 0; u <= 9; u++) {25                     f[i + 1][u < p[i] || u == p[i] && j][(u + k) % m] += f[i][j][k];26                 }27             }28         }29     }30     return f[sz][1][0];31 }32 33 int main() {34     while (~scanf("%d %d %d", &a, &b, &m)) {35         printf("%d\n", get(b) - get(a - 1));36     }37     38     return 0;39 }

不要62

杭州人称那些傻乎乎粘嗒嗒的人为 $62$（音：laoer）。

杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别的士司机和乘客的心理障碍，更安全地服务大众。

不吉利的数字为所有含有 $4$ 或 $62$ 的号码。例如：$62315,73418,88914$ 都属于不吉利号码。但是，$61152$ 虽然含有 $6$ 和 $2$，但不是连号，所以不属于不吉利数字之列。

你的任务是，对于每次给出的一个牌照号区间 $[n,m]$，推断出交管局今后又要实际上给多少辆新的士车上牌照了。

输入格式

输入包含多组测试数据，每组数据占一行。

每组数据包含一个整数对 $n$ 和 $m$。

当输入一行为“0 0”时，表示输入结束。

输出格式

对于每个整数对，输出一个不含有不吉利数字的统计个数，该数值占一行位置。

数据范围

$1 \le n \le m \le 10^9$

输入样例：

1 1000 0

输出样例：

解题思路

定义状态$f(i,j,k)$满足以下条件的整数$n$的数量：

$n$的数位大小为$i$，$0 \leq n < 10^i$。
若$n \leq N \bmod 10^i$，则$j=1$；否则$j=0$。
$n$的最高位是数字$k$。
$n$中不含有数字$4$以及相邻的$62$。

状态转移方程为$$f(i,j,k) \longrightarrow f(i+1,\ u < p_i \ \operatorname{or} \ u = p_i \ \operatorname{and} \ j, \ u) \quad (u \ne 4 \ \operatorname{and} \ \neg (u=6 \ \operatorname{and} \ k=2 ))$$

可以发现不需要处理前导$0$的情况，因此最终答案就是$\sum\limits_{i=0}^{9}{f(sz,1,i)}$。

AC代码如下，时间复杂度为$O(10^2 \cdot \log{N})$：

1 #include  2 using namespace std; 3  4 const int N = 15; 5  6 int f[N][2][N]; 7 int p[N], sz; 8  9 int get(int x) {10     if (!x) return 1;11     sz = 0;12     while (x) {13         p[sz++] = x % 10;14         x /= 10;15     }16     memset(f, 0, sizeof(f));17     for (int i = 0; i <= 9; i++) {18         if (i != 4) f[1][i <= p[0]][i]++;19     }20     for (int i = 1; i < sz; i++) {21         for (int j = 0; j <= 1; j++) {22             for (int k = 0; k <= 9; k++) {23                 for (int u = 0; u <= 9; u++) {24                     if (u == 6 && k == 2 || u == 4) continue;25                     f[i + 1][u < p[i] || u == p[i] && j][u] += f[i][j][k];26                 }27             }28         }29     }30     int ret = 0;31     for (int i = 0; i <= 9; i++) {32         ret += f[sz][1][i];33     }34     return ret;35 }36 37 int main() {38     int a, b;39     while (scanf("%d %d", &a, &b), a) {40         printf("%d\n", get(b) - get(a - 1));41     }42     43     return 0;44 }

参考资料

F - Nim Editorial：https://atcoder.jp/contests/abc317/editorial/7047

关键词：