windy数

Posted on Edited on In

题目大意：求一段区间内不含前导零且相邻两个数字之差至少为2的正整数的个数

PS：很久以前写了一篇题解，现在无论是从码风还是代码实现上来看，都感觉那时候是个傻逼

时隔很久，终于有时间来重新整理一下思路，修改一下码风。

对于这道题目，我们直接在一段前后没有区间里搞的话，貌似不好求，于是运用一下在区间问题里面经典的前缀和思想——

对于\([1,r]\)求得一个\(res_1\)，在\([1,l-1]\)求得一个\(res_2\)，两者做差即是\([l,r]\)内的\(res\)

接下来讨论如何求出\([1,一个端点]\)的答案，

我们设\(f[i][j]\)表示当前这一位是\(i\)，上一位是\(j\)的方案数目

然后考虑转移：我们枚举每一位的\(0\)~\(9\)，特别的，如果发现上一位是有限制的，那么这一位的上限便不再是9，只能是原数中的那个数字

举个例子：

假如原数为\(123456\)

我们可以从\(122...\)转移到\(1229..\)，但是我们显然不能从\(123...\)转移到\(1239..\)，只能转移到\(1234..\)这一位上限显然只能是4

然后就可以大力讨论转移了。

代码如下：

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
57
58
59
60
61
62
#include <bits/stdc++.h>
using namespace std;

const int N = 666;

inline int read()
{
    int s(0), w(1);
    char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') w = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
    return s * w;
}

inline void put(int x)
{
    if (! x) putchar('0');
    if (x < 0) putchar('-'), x = -x;
    int num(0); char c[66];
    while (x) c[++ num] = x % 10 + 48, x /= 10;
    while (num) putchar(c[num --]);
    return (void)(putchar('\n'));
}

int n, m, cnt;
int num[N], f[N][N];
/*
pos 当前枚举的哪一位
pre 上一位是谁
flag 上一位是否达到了限制，换言之，前边搜到的数字，是否和原数字匹配了
lim 是否有前导零
*/
inline int dfs(int pos, int pre, int flag, int lim)
{
    if (! pos) return 1;
    if (! flag && f[pos][pre] != -1 && !lim) return f[pos][pre];
    int i, nex, res(0);
    nex = flag ? num[pos] : 9;
    for (i = 0; i <= nex; ++ i)
    {
        int delta = abs(pre - i);
        if (delta < 2 && ! lim) continue;
        if (i == nex && flag) res += dfs(pos - 1, i, 1, 0);
        else res += (i || ! lim) ? dfs(pos - 1, i, 0, 0) : dfs(pos - 1, i, 0, 1);
    }
    if (! flag && ! lim) f[pos][pre] = res;
    return res;
}

inline int calc(int x)
{
    memset (f, -1, sizeof f), cnt = 0;
    while (x) num[++ cnt] = x % 10, x /= 10;
    return dfs(cnt, 0, 1, 1);
}

signed main ()
{
    n = read(), m = read();
    put(calc(m) - calc(n - 1));
    return 0;
}