题解：P13085 [SCOI2009] windy 数（加强版）

lcfollower · 2025-07-05 09:41:14 · 题解

好不容易蹭到一个题解。

前情回顾还有这个，于是就有了这题。

某个帖子已经提示我们了，要写数位 dp。

数位 dp 的思想是 dp 与前缀和，我们记 windy_i 为 [1,i] 之间的 Windy 数，则 windy_{[l ,r]} = windy_r - windy_{l - 1}。

然后我们进行 dp，来设 f_{pos ,lst} 表示到了第 pos 位，前一位值是 lst 的 Windy 数个数。我们从高位向低位 dp，这样方便我们后续做某些事情，下文展开。那么转移方程为 f_{pos ,lst} = \sum\limits_{i = 0}^9 [i - lst \ge 2]\times f_{pos + 1 ,i} ，i 表示枚举当前位数。

等一下，是不是有什么没有考虑？

是的，我们逐一攻破。

• 这一位数的可能范围一定是 [0,9] 之间的整数。

  • 错误。假设正在求 windy_x，位数为 cnt，如果你是贴着边界的，也就是说第 cnt\sim pos+1 位与 x 的 cnt\sim pos + 1 位是一样的，这样这一位的范围只能为 [0,a_{pos}]，其中 a_{pos} 表示 x 的第 pos 位的值，因为 dp 要保证答案在 x 及以内。

  • 反之，这一位可以随便选，范围为 [0,9] 间的整数。

• 如果我们选了多个 0，该怎么办？

  • 这就表示可能有前导零的存在，但是多个 0 分情况，并非一定是前导零。

  • 当这多个零前面已经有至少一个非零位的时候，无影响，这不是前导零。

  • 否则没有，这就是前导零，而理论上这个数不合法，但是这样我们考虑到了非 cnt 位数的情况，这样我们把这一前导零视作没有就可以了，但是需要用变量记录一下。

• 所以好复杂，用啥实现啊。

  • dfs 即可，它更简单。如果你硬要不写 dfs 我也没办法。

• 我们的状态过多了，dfs 会超时。

  • 记忆化呗。

• 我们定的状态在贴着边界的时候不适用。

  • 因为当高位不贴边界时，低位可以自由选择，此时；若仍贴着上界，则需继续判断后续位是否越界‌，不可返回。

  • 同理在贴着边界的时候我们不应赋值 f 数组。

• 好像在有前导零的时候也不适用。

  • 是的。前面有好多前导零，后面随便选，而这个状态默认前面没有前导零，是正常 0，选的范围也不同，比如 [2,9]。我们状态默认没有前导零，前面的就不能返回了。

  • 同理在有前导零的时候我们不应赋值 f 数组。

# include <bits/stdc++.h>

# define int long long
# define up(i ,x ,y) for (int i = x ; i <= y ; i ++)
# define dn(i ,x ,y) for (int i = x ; i >= y ; i --)
# define inf 1e14

using namespace std;

inline int read (){int s = 0 ; bool w = 0 ; char c = getchar () ; while (!isdigit (c)) {w |= (c == '-') ,c = getchar () ;} while (isdigit (c)){s = (s << 1) + (s << 3) + (c ^ 48) ; c = getchar ();}return w ? -s : s;}
inline void write (int x){if (x < 0) putchar ('-') ,x = -x; if (x > 9) write (x / 10) ; putchar (x % 10 | 48);}
inline void writesp (int x){write (x) ,putchar (' ');}
inline void writeln (int x){write (x) ,putchar ('\n');}

const int N = 25 ,mod = 1e9 + 7;
int f[25][10] ,a[25];
inline int dfs (int pos ,int lst ,bool leading ,bool limit){
//leading = 0 : 前导 0. 反之。
  if (!pos) return 1;
  if (leading && !limit && f[pos][lst] != -1) return f[pos][lst];//无前导零 + 不贴边界 + 记忆化.
  int lim = limit ? a[pos] : 9 ,res = 0;//lim 为选择边界。
  up (i ,0 ,lim)
    if (abs (i - lst) >= 2) res += dfs (pos - 1 ,
    (!leading && !i) ? -2 : i /*如果还能保持前导零那么 lst 为 -2，这样后面随便填，因为 0~9 - (-2) 都大于等于 2.*/,
    leading || i ,/*1.已经没有前导零了，2.这一位不为 0.*/
    limit && (i == lim));//是否贴着边界.
  if (!limit && leading) f[pos][lst] = res;//记忆化.
  return res;
} inline int solve (int x){
  int cnt = 0 ;
  memset (f ,-1 ,sizeof f);
  while (x) {
    a[++ cnt] = x % 10;
    x /= 10;
  } return dfs (cnt ,-2 ,0 ,1);
} signed main (){
  int l = read () ,r = read ();//writeln (solve (r));
  writeln (solve (r) - solve (l - 1));
  return 0 ;
}