「不要62」問題解析：數位DP入門與暴力枚舉優化

問題描述

統計區間[n, m]中不包含數字4、不包含連續數字62的整數個數。多組測試，以EOF結束。

暴力枚舉法（數據範圍≤10⁶可通過）

bool is_lucky(int x) {
    int prev = -1;
    while (x) {
        int d = x % 10;
        if (d == 4) return false;
        if (prev == 2 && d == 6) return false; // 注意：從低位向高位是 2->6 即 62
        prev = d;
        x /= 10;
    }
    return true;
}

int main() {
    int n, m;
    while (scanf("%d %d", &n, &m) == 2) {
        int cnt = 0;
        for (int i = n; i <= m; ++i)
            if (is_lucky(i)) ++cnt;
        printf("%d\n", cnt);
    }
    return 0;
}

數位DP法（通用解法，支援10¹⁸）

狀態定義

dp[pos][prev_is_6][limit][lead_zero]：

• pos：當前處理位置(從高位到低位)
• prev_is_6：前一位是否為6
• limit：是否受上界限制
• lead_zero：是否仍在前導零階段

遞歸轉移

int dfs(int pos, bool prev6, bool limit, bool lead, const vector& digits) {
    if (pos == -1) return 1; // 合法數字構造完成
    if (!limit && !lead && memo[pos][prev6] != -1) return memo[pos][prev6];

    int up = limit ? digits[pos] : 9;
    int ans = 0;
    for (int d = 0; d <= up; ++d) {
        if (d == 4) continue;                    // 禁用4
        if (prev6 && d == 2) continue;           // 禁用62 (高位6, 低位2)
        ans += dfs(pos-1, d==6, limit && d==up, lead && d==0, digits);
    }
    if (!limit && !lead) memo[pos][prev6] = ans;
    return ans;
}

int count_lucky(int x) {
    if (x < 0) return 0;
    vector digits;
    while (x) { digits.push_back(x%10); x/=10; }
    if (digits.empty()) digits.push_back(0);
    memset(memo, -1, sizeof(memo));
    return dfs(digits.size()-1, false, true, true, digits);
}

區間查詢答案

printf("%d\n", count_lucky(m) - count_lucky(n-1));

複雜度對比

關鍵細節

• 62判斷方向：從低位向高位遍歷時，prev==6 && d==2對應十進制62
• 前導零處理：前導零階段prev6=false，不觸發62檢查
• 0的特殊性：0不含4和62，視為合法，count_lucky(0)=1
• 備忘錄維度：pos[20] × prev6[2]極小，無需limit/lead維度

擴展：統計「包含62」或「包含4」的個數

總數 - 合法數 = 不合法數。或修改DP狀態增加has_4、has_62標誌位統計具體違規類型。