`算法题解` `AcWing` 1085. 不要62

题目链接

相同的题目

题解

含有4 或 连续的62, 是非法的数;
… 一般我们的数位DP, 要么是计算(非法数)的个数, 要么是计算(合法数)的个数;
… 至于要选择哪个, 要具体问题具体分析, 总之看哪种选择 DP是能处理的.

数位DP的核心是: Aligned( pre, k)函数, 即对于[a b c] [000 -- 999]这个集合里的数, 如何求解呢?
… 由于(非法数), 相邻数位有明显的限制约定, 符号DP的递推, 故: 选择计算 (非法数)
IF( 假如abc中 有4 或 连续的62): 则: 整个集合 都是非法的, ans += 10^3
ELSE IF( c != 6): 此时, 非法数, 它的4 或 62, 一定不会涉及到 abc数位, 则: ans += DP[ 3]
… Dp[ x]表示: 在[x个0 -- x个9]的(字符串数)集合里, 非法数的个数
ELSE: 此时, c == 6, 非法数 可能涉及c, 也可能不涉及, 需要继续划分; 令数为: [a b c] [hh . .], 进行FOR( hh, 0, 9, 1)遍历
… IF( hh == 2 || h == 4){ ans += 10^2;}
… ELSE{ ans += DP[ 2];}

乍一看, 这个Aligned定义是没问题的, 可是, …, 其实是问题的;
问题出在: c == 6, 且hh == 6时;
假如是: c == 6 && hh == 7, 此时, 非法数, 确实不会涉及a b c hh, 答案是DP[ 2]
但是, 当hh == 6时, 你将它归结为DP[ 2], 即说明: [a b c] [hh . .] 不会涉及到a b c hh
而这是错的, 比如: [ 1 2 3] [6 2 1], 此时, 你的DP[ 2]里, 肯定不会有2 1这个值 (因为它是合法的)

故, 对于hh == 6的情况, 还得 继续划分hhh; 对于hhh = 6时, 还得继续划分hhhh…
时间就变成了10^n…

当然这个思路是正确的, 对于h开头为6的情况, 就是得 不断的划分; 没有办法直接的递推

因此, 处理方法是: 将hh = 6的情况, 通过记忆化存储下来,
即当c == 6 && hh == 6时: ans += DP_2[ 2], 其中DP_2[ a]表示: [6,a个0 -- 6,a个9]之间的非法数个数

弄两个DP, DP_2 有些重复, 而且麻烦; 直接定义: DP[ h][ k]为: [h,k个0 -- h,k个9]之间的非法数个数

此时, 原来的Dp[ a] 就等于 现在的Dp[0,1,2...,9][ a - 1], 因此, 以上的那个Aligned定义, 也可以用新的Dp[h][k]来实现

代码

//{ objects and structs
LITERAL_ int D1_ = 9, D2_ = 8;
Ll_ Dp[ D1_ + 1][ D2_ + 1];
//} objects and structs
//{ functions
Ll_ Power_10( PAR_( int, _k)){
    if( _k < 0){ return 0;}
    Ll_ ans = 1;
    FOR_( i, 1, _k, 1){
        ans *= 10;
    }
    return ans;
}
void Build_dp(){
    //< Dp[ a][ b]:  在[a,b个0, a,b个9]这些`字符串数`中, 非法数的个数 (即含有4 或 含有`连续的62`);
    //< `b`也就是: 自由数位 的个数
    //> Dp[][ 0]
    FOR_( h, 0, 9, 1){
        Dp[ h][ 0] = ( h == 4 ? 1 : 0);
    }
    //> Dp[ ][ >0]
    FOR_( i, 1, D2_, 1){
        FOR_( h, 0, 9, 1){
            auto & cur_dp = Dp[ h][ i];
            cur_dp = 0;
            if( h == 4){ cur_dp = Power_10( i);}
            else if( h == 6){
                FOR_( hh, 0, 9, 1){
                    if( hh == 2){ cur_dp += Power_10( i - 1);}
                    else{
                        cur_dp += Dp[ hh][ i - 1];
                    }
                }
            }
            else{
                FOR_( hh, 0, 9, 1){
                    cur_dp += Dp[ hh][ i - 1];
                }
            }
        }
    }
}
int Single_number( PAR_( int, _a)){
    //--
    vector< int> bits;
    for( auto i = _a; i > 0; i /= 10){
        bits.push_back( i % 10);
    }
    reverse( bits.begin(), bits.end());
    if( bits.empty()){ bits.push_back( 0);}
    //--
    int n = bits.size();
    FOR_( i, 0, n - 1, 1){
        if( bits[ i] == 4){ return 1;}
        if( i > 0){
            if( ( bits[ i] == 2) && ( bits[ i - 1] == 6)){
                return 1;
            }
        }
    }
    return 0;
}
Ll_ Aligned( PAR_( vector< int>, _pre), PAR_( int, _k)){
    //< [pre,k个0 -- pre,k个9], 且该数 `> 0`, `不含前导零`, `位数相同`
    //< 他的答案: 可以将这`10^k`个数的(前缀和后缀) 分开, 即得到: `10^k`个相同前缀, 得到`10^k`个后缀`[k个0 -- k个9]`(字符串数, 不是数字)
    //< (即, 数字 与 字符串数, 相同!!!)
    int n = _pre.size();
    //{ contain `4` or `62` in `pre`
    FOR_( i, 0, n - 1, 1){
        if( _pre[ i] == 4){
            return Power_10( _k);
        }
        if( i > 0){
            if( ( _pre[ i] == 2) && ( _pre[ i - 1] == 6)){
                return Power_10( _k);
            }
        }
    }
    //}
    return Dp[ *_pre.rbegin()][ _k];
}
Ll_ Prefix( PAR_( int, _r)){
    if( _r < 0){ return 0;}
    //--
    vector< int> bits;
    for( auto i = _r; i > 0; i /= 10){
        bits.push_back( i % 10);
    }
    reverse( bits.begin(), bits.end());
    if( bits.empty()){ bits.push_back( 0);}
    //--
    Ll_ ans = 0;
    int n = bits.size();
    FOR_( i, 0, n - 1, 1){
        int k = n - 1 - i;
        FOR_( h, 0, bits[ i] - 1, 1){
            if( (h == 0) && (i == 0)){  //< 是`i`, 不是`k`;   代表`[0,k个0--0,k个9]`, 不是代表`[0--0]`
                //< [0000, 0999], 分为: [0--0], [1--9], [10--99], [100-999] 共(k+1)类
                FOR_( b, -1, k - 1, 1){
                    if( b == -1){ //< [0--0]
                        ans += Single_number( 0);
                    }
                    else{ //< [1,b个0--9,b个9]
                        FOR_( hh, 1, 9, 1){
                            ans += Aligned( {hh}, b);
                        }
                    }
                }
                continue;
            }
            vector< int> pre( bits.begin(), bits.begin() + i);
            pre.push_back( h);
            //* 此时, 该类所对应的所有数 一定形如: [pre,h,0...0 -- pre,h,9...9] 共n位
            //* 说白了:  这些数, `> 0`, `不含前导零`, `位数相同`;  (即, 数字 与 字符串数, 相同!!!)
            ans += Aligned( pre, k);
        }
    }
    ans += Single_number( _r);
    //--
    return ans;
}
//} functions
//--
void __Solve( const int _test_id){
    ( void)_test_id;
    //----
    int l, r;
    while( true){
        scanf("%d%d", &l, &r);
        if( (l == 0) && (r == 0)){
            break;
        }
        l > r ? swap( l, r) : (void)0;
        printf("%lld", (r - l + 1) - ( Prefix( r) - Prefix( l - 1))); //< 后面要`带括号`!
        printf("\n");
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137