veteran233QAQ的博客
0%

HDU 2089 - 不要62

发表于 更新于

题目

http://acm.hdu.edu.cn/showproblem.php?pid=2089

思路

数位dp经典模板题，建议学习

AC代码

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
#include <bits/stdc++.h>
#define endl '\n'
#define lson(x) (x<<1)
#define rson(x) (x<<1|1)
#define lowbit(x) (x&-x)
using namespace std;
struct _IO { _IO() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); } }_io;
typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair<ll, ll> pll;

ll dp[20][2], a[20];
ll dfs(ll pos, ll sta, bool limit)
{
    if (!pos) return 1;
    if (!limit && dp[pos][sta] != -1) return dp[pos][sta];
    ll up = limit ? a[pos] : 9, ans = 0;
    for (ll i = 0; i <= up; ++i)
    {
        if (sta && i == 2) continue;//上一位是6，当前位是2
        if (i == 4) continue;//当前位是4
        ans += dfs(pos - 1, i == 6, limit && i == a[pos]);
    }
    if (!limit) dp[pos][sta] = ans;
    return ans;
}
ll solve(ll x)
{
    ll pos = 0;
    while (x)
    {
        a[++pos] = x % 10;
        x /= 10;
    }
    return dfs(pos, 0, 1);
}

int main()
{
    ll n, m;
    memset(dp, -1, sizeof(dp));
    while (cin >> n >> m)
    {
        if (n == m && m == 0) break;
        cout << solve(m) - solve(n - 1) << endl;
    }
    return 0;
}