[SCOI2009] windy 数

题面

题目描述

不含前导零且相邻两个数字之差至少为 22 的正整数被称为 windy 数。windy 想知道，在 aa 和 bb 之间，包括 aa 和 bb ，总共有多少个 windy 数？

输入格式

输入只有一行两个整数，分别表示 aa 和 bb。

输出格式

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

样例#1        样例#2

输入：1 10         输入: 25 50
输出： 9          输出：20
数据范围：
对于所有的数据，满足 1≤a≤b≤2×1091≤a≤b≤2×109

思路：

首先应该想到的就是数位DP，数位DP就是用来解决形如“在 ll 到 rr 的区间里有多少个数满足题目要求”的问题。

这个题题面的意思大概就是像 183,691183,691 这样的相邻数字之间的差是 22 的数是windy数。

暴力的话显然是不行的，这道题的数据范围很大，从 aa 枚举到 bb 时间复杂度可想而知。

那用数位DP的话怎么做呢？显然这个题有那么点区间DP的意思，但是区间DP并不能解决此题（状态设计出来了没法高效地转移）。

数位DP的状态设计就是 f[i][j]f[i][j] 表示前ii位中最高位为 jj 的windy数的个数。显然 f[i][j]=∑|k−j|≥2f[i−1][k]f[i][j]=∑|k−j|≥2f[i−1][k] （这个是因为此类DP的原理其实就相当于一位一位地往上加数）

状态和转移方法都有了，那该怎么得出题目所要求的东西呢？

我们可以考虑利用前缀和的思想得出该结果。直接求区间显然不怎么现实，那我们就可以分别求出 1−(l−1)1−(l−1) 和 1−r1−r 区间的和，再相减就可以得出结果。

那又怎么求出 1−x1−x 区间的和呢？这里直接求又是不行的。考虑分类讨论。以 x[i]x[i] 表示 xx 这个数的第 ii 位， cntcnt 表示 xx 的位数。

一、求出 cnt−1cnt−1 位的windy数的个数

因为我们要讨论 1−x1−x 这个区间，所以 cnt−1cnt−1 位的windy数是完全被包括在这个范围内的，因此可以直接求解

二、求出有 cntcnt 位且最高位小于 x[0]x[0] 的windy数。

这些windy数显然也是也是在上述范围内的，可以直接累加到答案中。这部分答案即为： ∑1≤x[0]≤9f[cnt][x[0]]∑1≤x[0]≤9f[cnt][x[0]]

三、类比二、中的过程。

依次求出有 cnt−1cnt−1 位、最高位为 x[1]x[1] 的windy数，有 cnt−2cnt−2 位、最高位为 x[2]x[2] 的windy数…………有 11 位、最高位为 x[cnt]x[cnt] 的windy数。每向下推进一位，前面的数字（更高位的数字）就已经固定，即为 xx 这个数的前tt位。
这里需要注意控制一个边界条件。就是当以 x[t]x[t] 为最高位时，若 |x[t]−x[t+1]|<2|x[t]−x[t+1]|<2 ，那么最高位为 x[t]x[t] ，次高位为 x[t+1]x[t+1] 的windy数不存在，直接退出。

Code:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
typedef long long ll;
int a, b;
int f[11][11];
inline int read(void){
    int f = 1, x = 0;char ch;
    do{ch = getchar();if(ch=='-')f = -1;} while (ch < '0' || ch > '9');
    do{ x = x * 10 + ch - '0';ch = getchar();} while (ch >= '0' && ch <= '9');
    return f * x;
}
inline int _abs(int x) { return x <= 0 ? -x : x; }
inline void _init(void){
    for (int i = 0; i <= 9;++i)
        f[1][i] = 1;
    for (int i = 2; i <= 10;++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];//预处理出所有的windy数的个数
        }
    }
    return;
}
inline int calc(int k){
    if(k==0) return 0;
    int res = 0, cnt = 0, num[11] = {0};
    while(k){
        num[++cnt] = k % 10;
        k /= 10;
    }//将读入的数分解
    for (int i = 1; i < cnt;++i){
        for (int j = 1; j <= 9;++j)
            res += f[i][j];//求出cnt-1位的windy数的个数，可以直接累加
    }
    for (int i = 1; i < num[cnt];++i)
        res += f[cnt][i];//处理出所有cnt位、且最高位小于读入数字最高位的windy数的个数
    for (int i = cnt - 1; i >= 1;--i){//最难搞的一块，处理其余的情况
        for (int j = 0; j < num[i];++j)
            if(_abs(j-num[i+1])>=2) res += f[i][j];
        if(_abs(num[i+1]-num[i])<2) break;//不要忘了判断是否合法
    }
    return res;
}
int main(){
    a = read(), b = read();
    _init();
    printf("%d\n", calc(b) - calc(a - 1));//前缀和处理
    // std::cout << '\n' << calc(b) << ' ' << calc(a - 1);
    return 0;
}