数位 DP 是这样一类问题:求某个区间内,满足某种性质的数的个数。

有两个技巧:

  1. 前缀和思想。区间有两个界限,把它转化成一个界限,例如通过 f(N) 表示 0 - N 中满足这种性质的数的个数,求 [X, Y] 时,可用 f(Y) - f(X - 1)。
  2. 从树的角度进行考虑,按位进行分类讨论。

度的数量

度的数量

组合数的计算公式为:Cab=Ca1b+Ca1b1C_a^b = C_{a-1}^b + C_{a-1}^{b-1}

简化题意:给一个区间 [X, Y],问这个区间内有多少个数符合这样的条件:这个数的 B 进制表示中,有 K 位上是 1,其余位都是 0.

思路:

  1. 先将 n 转换成 B 进制数保存起来
  2. n 每一位上的数我们成为限定值,对 n 的每一位进行分类讨论
    1. 可以取限定值
    2. 取 0 ~ 限定值-1 的一个数

对于本题,用不到 2、3、9 这种限定值,本题要求 K 位上全填 1,其余位全填 0,当某位上的限定值 > 1 时,后面的位可以随便填(0 或 1),方案数可以直接算出来,然后 break 掉就可以了。

对 B 进制数从最高位开始遍历,用 last 存储当前位之前取过 1 的位的个数:

  1. 限定值为 0,当前位只能取 0,后面剩余位可以取 k - last 个 1
  2. 限定值为 1,当前位可以取 0 或 1。取 0 时后面剩余位可以取 k - last 个 1;取 1 时后面剩余位可以取 k - last - 1 个 1,因为当前位占用了一个 1,所以要减一
  3. 限定值大于 1,当前位可以取 0 或 1,同 2。
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
#include <iostream>
#include <vector>
using namespace std;

const int N = 35;
int k, b; // k 能用的 1 的个数,b 进制
int c[N][N];

// 预处理求组合数
void init() {
for (int i = 0; i < N; i++) {
for (int j = 0; j <= i; j++) {
if (!j)
c[i][j] = 1;
else
c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
}
}
}

int dp(int n) {
if (!n) return 0;
vector<int> nums;
while (n) nums.push_back(n % b), n /= b; // 将 n 转换成 b 进制
int res = 0;
int last = 0; //当前位之前选了多少1
for (int i = nums.size() - 1; i >= 0; i--) { // 从最高位开始遍历 n
int x = nums[i]; // x 是限定位
if (x) { // 限定位不为 0,左侧分支
res += c[i][k - last]; // 当前位可以取 0,在后面的 i 位中选出剩余个数个 1 的选法为 C(i, k-last)
if (x > 1) { // 限定位大于 1
if (k - last - 1 >= 0) res += c[i][k - last - 1]; // 当前位可以取 1,在后面的 i 位中选出剩余个数个 1 的选法为 C(i, k-last-1),因为当前位已经取 1 了,所以要 -1
break;
} else { // 限定位就是 1,放到下一位来处理,下一位处理的时候可用的 1 的个数会少一个
last++;
if (last > k) break;
}
}
if (!i && last == k) res++;
}
return res;
}

int main() {
init();
int x, y;
cin >> x >> y >> k >> b;
cout << dp(y) - dp(x - 1) << endl;
return 0;
}

数字游戏

1082. 数字游戏

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
#include <iostream>
#include <vector>
using namespace std;

const int N = 15;

int f[N][N];

void init() {
for (int i = 0; i <= 9; i++) f[1][i] = 1;
for (int i = 2; i < N; i++) {
for (int j = 0; j <= 9; j++) {
for (int k = j; k <= 9; k++) {
f[i][j] += f[i - 1][k];
}
}
}
}

int dp(int n) {
if (!n) return 1;
vector<int> nums;
while (n) nums.push_back(n % 10), n /= 10;
int res = 0;
int last = 0; // 记录上一位数是几
for (int i = nums.size() - 1; i >= 0; i--) {
int x = nums[i];
for (int j = last; j < x; j++) {
res += f[i + 1][j];
}
if (x < last) break;
last = x;
if (!i) res++;
}
return res;
}

int main() {
init();
int l, r;
while (cin >> l >> r) {
cout << dp(r) - dp(l - 1) << endl;
}
return 0;
}

Windy 数

Windy 数

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
#include <iostream>
#include <vector>

using namespace std;

const int N = 11;
int f[N][10]; // f[i][j] 表示共 i 位,最高位是 j 的 windy 数的个数

void init() {
for (int i = 0; i <= 9; i++) f[1][i] = 1;
for (int i = 2; i < N; i++) {
for (int j = 0; j <= 9; j++) {
for (int k = 0; k <= 9; k++) {
if (abs(j - k) >= 2) {
f[i][j] += f[i - 1][k];
}
}
}
}
}

int dp(int n) {
if (!n) 0;
vector<int> nums;
while (n) nums.push_back(n % 10), n /= 10;

int res = 0;
int last = -2;
for (int i = nums.size() - 1; i >= 0; i--) {
int x = nums[i];
for (int j = i == nums.size() - 1; j < x; j++) { // 首位不能填0
if (abs(j - last) >= 2) {
res += f[i + 1][j];
}
}
if (abs(x - last) >= 2)
last = x;
else
break;
if (!i) res++;
}
for (int i = 1; i < nums.size(); i++) {
for (int j = 1; j <= 9; j++) {
res += f[i][j];
}
}
return res;
}

int main() {
init();
int l, r;
cin >> l >> r;
cout << dp(r) - dp(l - 1) << endl;
return 0;
}