「BZOJ 1026」「SCOI2009」windy数

Description

给定 $l$ 和 $r\ \left( 1 \leq l \leq r \leq 2 \times 10^9 \right)$，求区间 $[l,r]$ 有多少个 不含前导零且相邻两个数字之差至少为 $2$ 的正整数（即 $\rm{windy}$ 数）。

Source

[BZOJ]1026

Solution

数位DP 入门题。

用 $f_{pos,pre}$ 表示当前到了第 $len - pos + 1$ 位，上一位是 $pre$ 的 $\rm{windy}$ 数个数。

考虑用 记忆化搜索 实现 数位DP 。枚举每一位，保证当前位与上一位的差大于等于 $2$ 。注意判断是否有前导零，如果有或者刚开始搜，就把上一位设为 $11$（因为 $0 \sim 9$ 与 $11$ 的差都大于等于 $2$，保证下一位没有限制），具体实现详见代码。时间复杂度为 $O(\lg^2 n)$ 。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
	int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

const int MAXN = 10;
int l, r, f[MAXN + 5][MAXN + 5];

int dfs(int *num, int pos, int pre, bool lead, bool lim) {
    //pos 表示当前是第 len - pos + 1 位，pre 表示上一个数，lead 表示是否有前导零，lim 表示当前数位是否受到限制 
    if (!pos) return 1;//搜完了 
    if (!lim && !lead && ~f[pos][pre]) return f[pos][pre];//返回该状态已记录的值 
    int res = 0, maxNum = lim ? num[pos] : 9;//如果有限制，当前位则为 0 ~ 当前位的值，否则为 0 ~ 9 
    for (int i = 0; i <= maxNum; ++i) {
        if (abs(i - pre) < 2) continue;//相邻数位之差不能小于 2（题目要求） 
        if (lead && !i) res += dfs(num, pos - 1, 11, 1, lim && i == maxNum);//如果前面全是前导零，第一位仍设为 11 
        else res += dfs(num, pos - 1, i, 0, lim && i == maxNum);//否则设当前位为 i，枚举下一位 
    }
    if (!lim && !lead) f[pos][pre] = res;//如果没有前导 0 且 最高位无限制，则存下这个状态的值 
    return res;
}//记忆化搜索 实现 数位DP 

inline int solve(int x) {
    int len = 0, num[MAXN + 5];
    for (; x; x /= 10) num[++len] = x % 10;
    memset(f, -1, sizeof (f));//初始化为 -1
    return dfs(num, len, 11, 1, 1);//从 11 开始可以保证数字第一位没有限制 
}

int main() {
    read(l), read(r);
    write(solve(r) - solve(l - 1));
    putchar('\n');
    return 0;
}