牛客网 Find the AFei Numbers【数位DP】

Dear 丶 2023-08-17 17:36 70阅读 0赞

题目链接：[https://ac.nowcoder.com/acm/contest/338/F][https_ac.nowcoder.com_acm_contest_338_F]

题意：就是让你统计1~n中包含520的数的个数，n<= 1e18

思路：数位DP中比较简单的了，dp\[pos\]\[pre1\]\[pre2\]代表着第pos位，前缀是pre1和pre2的不包含520的个数，最后用总数减去包含520的个数就是答案。

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    #define ls rt << 1
    #define rs rt << 1|1
    #define mid ((l + r) >> 1)
    #define lson l, mid, ls
    #define rson mid + 1, r, rs
    const int maxn = 20;
    const int mod = 1e9 + 7;
    ll dp[maxn][12][12];
    int a[maxn];
    
    ll dfs(int pos, int pre1, int pre2, int lead, int limit)
    {
        if(pos == 0) return 1;
        if(!limit && ! lead && dp[pos][pre1][pre2] != -1)
            return dp[pos][pre1][pre2];
        int up = limit ? a[pos] : 9;
        ll ret = 0;
        for(int i = 0; i <= up; ++i)
        {
            if(pre1 == 5 && pre2 == 2 && i == 0) continue;
            ret += dfs(pos - 1, pre2, i, lead && (i == 0), limit && (i == up));
        }
        if(!limit && !lead)
            dp[pos][pre1][pre2] = ret;
        return ret;
    }
    ll slove(ll x)
    {
        int tot = 0;
        while(x)
        {
            a[++tot] = x % 10;
            x /= 10;
        }
        memset(dp, -1, sizeof(dp));
        return dfs(tot, 0, 0, 1, 1);
    }
    
    int main()
    {
        int t;
        scanf("%d", &t);
        while(t--)
        {
            ll n;
            scanf("%lld", &n);
            ll ans = n - slove(n) + 1;
            printf("%lld\n", ans);
        }
        return 0;
    }

[https_ac.nowcoder.com_acm_contest_338_F]: https://ac.nowcoder.com/acm/contest/338/F