0%

[SCOI2009] windy 数

题目

题目链接

题目大意:求出 $a$ 和 $b$ 之间有多少个数满足不含前导零且相邻两个数字之差至少为 $2$。$1 \le a \le b \le 2 \times 10^9$。

思路

(感觉防止自己陷入抑郁情绪的一种方法就是让自己忙起来…)

数位 DP 的裸题,设 $f(i, j, k)$ 表示第 $i$ 位,上一位数字为 $j$,$k$ 表示下一位是否有上限。一般来说数位 DP 用记忆化搜索会好写些。

然后就是很套路的搜。

代码

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

template <class T>
inline void read(T &x) {
x = 0;
int f = 0;
char ch = getchar();
while (!isdigit(ch)) { f |= ch == '-'; ch = getchar(); }
while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
x = f ? -x : x;
return ;
}

typedef long long LL;

int f[15][15];
int dig[15];
int len, a, b;

int dfs(int dep, int lst, bool lim) {
if (!dep) return 1;
if ((!lim) && (~f[dep][lst])) return f[dep][lst];
int up = lim ? dig[dep] : 9, ans = 0;
for (int i = 0; i <= up; ++i) {
if (abs(i - lst) < 2) continue;
ans += dfs(dep - 1, lst == 11 && i == 0 ? 11 : i, lim && i == up);
}
if (!lim) f[dep][lst] = ans;
return ans;
}

int solve(int x) {
len = 0;
memset(dig, 0, sizeof(dig));
while (x) dig[++len] = x % 10, x /= 10;
memset(f, -1, sizeof(f));
return dfs(len, 11, true);
}

int main() {
read(a), read(b);
printf("%d\n", solve(b) - solve(a - 1));
return 0;
}