BZOJ 1026 風數：數位 DP 計數相鄰差 ≥ 2 的數

題目大意

定義 windy 數：無前導零，且相鄰兩位數字差的絕對值 ≥ 2 的正整數。給定區間 [A, B] (1 ≤ A ≤ B ≤ 2e9)，求區間內 windy 數個數。

數位 DP 模板

狀態定義

dp[len][last]：長度為 len、最高位 (最左邊) 為 last 的合法數字個數 (允許前導零，但在最終計數時處理)。

預處理 DP 表

void init() {
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i <= 9; ++i) dp[1][i] = 1; // 長度 1，任意數字皆合法
    for (int i = 2; i <= 10; ++i) // 最大長度 10 (2e9 < 10^10)
        for (int j = 0; j < 10; ++j)
            for (int k = 0; k < 10; ++k)
                if (abs(j - k) >= 2)
                    dp[i][j] += dp[i-1][k];
}

計算 [1, x] 內合法數個數

將 x 拆解為數位陣列 digit[1..cnt] (高位到低位)。從高位往低位掃描，累加比當前前綴小的合法數。

long long solve(long long x) {
    if (x <= 0) return 0;
    int digit[12], cnt = 0;
    while (x) { digit[++cnt] = x % 10; x /= 10; }
    // digit[1] 為最低位，digit[cnt] 為最高位

    long long ans = 0;
    // 1. 長度 < cnt 的所有合法數 (最高位不能為 0)
    for (int len = 1; len < cnt; ++len)
        for (int d = 1; d <= 9; ++d)
            ans += dp[len][d];

    // 2. 長度 = cnt，按高位到低位枚舉
    for (int i = cnt; i >= 1; --i) {
        int cur = digit[i];
        // 當前位可選範圍：最高位 1..cur-1，其他位 0..cur-1
        int start = (i == cnt) ? 1 : 0;
        for (int d = start; d < cur; ++d) {
            if (i == cnt || abs(d - digit[i+1]) >= 2) // 檢查與前一位 (更高位) 差值
                ans += dp[i][d];
        }
        // 若當前位與前一位差值 < 2，後續位無法構成合法數，直接跳出
        if (i < cnt && abs(cur - digit[i+1]) < 2) break;
        // 若已處理到最低位 (i==1) 且未 break，說明 x 本身合法，ans++ (但 dp 已包含等長前綴小的，x 本身需額外判斷)
        // 標準寫法：solve(x) 返回 

最終答案
ans = solve(B+1) - solve(A)。因 solve(x) 計算 [1, x-1] 個數。

完整代碼
#include 
#include 
#include 
using namespace std;
#define LL long long
LL dp[12][10];
int digit[12];

void init() {
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i <= 9; ++i) dp[1][i] = 1;
    for (int i = 2; i <= 10; ++i)
        for (int j = 0; j < 10; ++j)
            for (int k = 0; k < 10; ++k)
                if (abs(j - k) >= 2) dp[i][j] += dp[i-1][k];
}

LL solve(LL x) {
    if (x <= 0) return 0;
    int cnt = 0;
    while (x) { digit[++cnt] = x % 10; x /= 10; }
    LL ans = 0;
    for (int len = 1; len < cnt; ++len)
        for (int d = 1; d <= 9; ++d) ans += dp[len][d];
    for (int i = cnt; i >= 1; --i) {
        int start = (i == cnt) ? 1 : 0;
        for (int d = start; d < digit[i]; ++d)
            if (i == cnt || abs(d - digit[i+1]) >= 2) ans += dp[i][d];
        if (i < cnt && abs(digit[i] - digit[i+1]) < 2) break;
    }
    return ans;
}

int main() {
    init();
    LL a, b;
    while (scanf("%lld%lld", &a, &b) == 2)
        printf("%lld\n", solve(b+1) - solve(a));
    return 0;
}


複雜度

預處理：O(10 * 10 * 10) = O(1)
單次查詢：O(位數 * 10) = O(1)
極快，適合多測試案例。