不要 62

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1171 字

求[n,m]中不含数字4且不含连续子串"62

一本通
练习

正文

/*
原题：不要 62（一本通 5.3 练习 2，HDU 2089）
题意：求 [n,m] 中不含数字 4 且不含连续子串 "62" 的整数个数，遇到 0 0 结束。
思路：数位 DP，state=(pos,last6,tight)，last6 标记上一位是否为 6。
     转移时跳过 d==4，以及 last6 且 d==2 的情况（即 "62"）。
     答案 = f(m) - f(n-1)。
复杂度：时间 O(log10 m * 2)，空间 O(log10 m * 2)
易错点：前导零不会引入 4 或 62，无需单独处理；遇到 0 0 结束输入。
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int dig[12];
ll memo[12][2][2];
int len;
ll dfs(int pos, bool last6, bool tight){
    if(pos == len){
        return 1;
    }
    if(memo[pos][last6][tight] != -1) return memo[pos][last6][tight];
    ll ans = 0;
    int up = tight ? dig[pos] : 9;
    for(int d = 0; d <= up; d++){
        if(d == 4) continue;
        if(last6 && d == 2) continue;
        ans += dfs(pos + 1, d == 6, tight && d == up);
    }
    return memo[pos][last6][tight] = ans;
}
ll f(ll n){
    len = 0;
    ll t = n;
    while(t){
        dig[len++] = t % 10;
        t /= 10;
    }
    if(len == 0) dig[len++] = 0;
    reverse(dig, dig + len);
    memset(memo, -1, sizeof(memo));
    return dfs(0, false, true);
}
int main(){
    ll n, m;
    while(cin >> n >> m && (n || m)){
        cout << f(m) - f(n - 1) << "\n";
    }
    return 0;
}

不要 62

正文

一本通·提高篇的其它内容