算法提高课汇总

算法思路

本题思路仍然是数位$DP$套路, 需要注意的是满足性质的$DP$预处理以及题目要求的不含前导0.

$DP$预处理

状态表示 $f(i, j)$

• 集合: $i$位数字且最高位为$j$的Windy数集合.

• 属性: Count

状态计算

第$i$位数字固定为$j$, 考虑第$i - 1$位的$k$, 只要保证$j, k$满足Windy数性质即可,
$f(i, j) = \sum_{k} f(i - 1, k), 0\le k\le 9 \;\&\; |j - k|\ge 2$.

前导$0$

首先考虑为何之前的问题都没有考虑前导0的问题, 原因主要是:

• 有前导0不会影响数字要求的性质, 例如 AcWing 1082. 数字游戏 要求的不降数,
  即使在一个不降数前加若干前导0也不会影响其性质. 而对于Windy数加入前导0
  可能会影响: 例如对于数字135是一个Windy数, 然而0135就不是了.

• 对于之前的问题, 一个数字$X$有前导0表示$X$是一个小于$n$位的数字. 以最高位$a_{n - 1} = 0$为例,
  这表示我们考虑的数字最大是一个$n - 1$位数, 由于我们后续的右子树$a_{n-1}\gt 0$, 所以不会出现
  重复考虑$X$的情况.

其次考虑本题对于前导0的处理:

• 对于左子树Windy数的计算, 我们的状态考虑了前导0的情况, 其原因是为了后续状态的计算. 例如
  状态$f(1, 0)$代表数字0, 如果我们忽略其状态(将其设为0), 则对于状态$f(2, 2)$, 即集合$2x$会
  忽略掉$20$这个数字, 而$20$是一个Windy数. (严格来说0不是前导0, 但相同的思路适用在00等
  情况). 本题的做法是在计算时只计算最高位大于0的状态, 而小于$n$位的数字最后再考虑进去.

  简单来说就是状态计算时考虑前导0, 最终计算时不考虑.

代码实现

#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10;

int f[N + 1][N];

void init()
{
    for ( int j = 0; j <= 9; j ++ )     f[1][j] = 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 )   return 0;

    vector<int> nums;
    while ( n ) nums.push_back(n % 10), n /= 10;

    int res = 0; //综合所有叶节点
    int last = -1; //记录已经确定位(右子树)的信息 本题只需确定上一位即可
    for ( int i = nums.size() - 1; i >= 0; i -- )
    {
        int x = nums[i];
        for ( int j = 0; j < x; j ++ ) //左子树
            if ( abs(j - last) >= 2 )
                res += f[i + 1][j];

        if ( abs(x - last) < 2 )    break; //已经确定的位不是Windy数 可直接退出
        last = x;

        if ( !i )   res ++ ; //n自身也是一个Windy数
    }

    //另外考虑低于n位数不含前导0的数字
    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;
}

不重要问题

正如上面提到的, 在之前的问题中没有另外考虑前导0的情况, 对于存在前导0的情况即代表小于$n$位
的数字, 为何本题要最后再计算小于$n$的数字呢? 这还是由于Windy数的性质(题目已经要求了啊喂).
如果按之前思路, 我们以$dp(10)$为例, 如果最高位(第2位)可以取0, 对应状态$f(2, 0)$, 这是
我们唯一需要考虑的左子树, 返回的结果是8而不是9, 因为有前导0所以此时01不是Windy数.
所以我们需要考虑无前导0的情况$…$