题解：P2657 [SCOI2009] windy 数

· · 题解

说在前面

update 2025.7.5 发现一处笔误并修改。

注意：本题解不保证存在多项式时间复杂度，如有需要请不要参考此题解。

我也不知道怎么过的……复杂度神奇。

前置芝士：搜索。

题目分析

我们可以想到一个很简单的做法：我们使用 dfs，来搜索可以生成的数。假设现在的最后一位数为 x，那么下一位的数字 k 肯定满足 x + 2 \le k \le 9 或 0 \le k \le x - 2。所以我们直接搜索即可。

这里我们要注意：如果当前是第一位，则不能为 0。所以我们把第一位单独拎出来搜索。

注意事项

  1. 当我们发现这个数 \ge l 且 \le r 时，我们把答案 +1，但是不能退出，因为如果直接退出的话我们能可能会漏掉一些位数更多的情况。例如 l = 1, r = 200，当我们搜索到 20 时，如果直接退出的话，我们就会漏掉例如 135。所以不能退出。

  2. 记得开 long long，如果不开 long long，那么当前的数溢出后会变成负数，越来越小，从而导致 TLE。

完整代码

#include <bits/stdc++.h>

#define int long long

using namespace std;

int l, r, ans;

void dfs(int x) {
    if (x >= l && x <= r) {
        ans++;
    } 
    int lst = x % 10;
    for (int i = 0; i <= lst - 2; i++) {
        if (x * 10 + i > r) break;
        dfs(x * 10 + i);
    } 
    for (int i = lst + 2; i <= 9; i++) {
        if (x * 10 + i > r) break;
        dfs(x * 10 + i); 
    }
}

signed main() {
    cin >> l >> r;
    for (int i = 1; i <= 9; i++) {
        dfs(i);
    }
    cout << ans;
    return 0;
}

说在后面

能过的原因大概是因为合法的数比较少吧……

特别鸣谢：@woshiSB4 提供的思路与代码。

最后，若代码、思路讲解有误，欢迎提出！