2018年全国多校算法寒假训练营练习比赛（第二场）G

2018年全国多校算法寒假训练营练习比赛（第二场）G

只写了四题，220名开外，，，菜到泣不成声
[题目链接](https://www.nowcoder.com/acm/contest/74/G）

题目描述

    杭州人称傻乎乎的人为62，而嘟嘟家这里没有这样的习俗。相比62，他那里的人更加讨厌数字38，当然啦，还有4这个数字！所以啊，嘟嘟不点都不想见到包含38或者4的数字。每次给出一个区间[n，m],你能找到所有令人讨厌的数字吗？

输入描述:

    多组输入输出；输入的都是整数对n、m（0<n≤m<1000000），如果遇到都是0的整数对，则输入结束。

输出描述:

    对于每次的输入输出全部令人讨厌的数的个数

示例1

    输入
    1 100
    0 0
    输出
    20

解题思路

    数位dp水题，而且数据几乎等于没有限制，随便写[其实是写过一个原题，直接搬的]

AC代码

#include <cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define LL long long
#define bug puts("***********")
#define INF 0x3f3f3f3f

using namespace std;

int bit[100];
LL dp[100][100];
LL DP(int p, int m, int flag)
{
    if (p == 0) return (m != 4);
    if (dp[p][m] != -1 && flag) return dp[p][m];
    int k = flag ? 9 : bit[p];
    LL sum = 0;
    for (int i = 0; i <= k; i++)
    {
        if (i == 4)
            continue;
        if (m == 3 && i != 8)
            sum += DP(p - 1, i, flag || i != k);
        else if (m != 3)
            sum += DP(p - 1, i, flag || i != k);
    }
    if (flag) dp[p][m] = sum;
    return sum;
}
LL solve(LL n)
{
    memset(dp, -1, sizeof(dp));
    int num = 0;
    if (n<0)
        return 0;
    while (n)
    {
        bit[++num] = n % 10;
        n /= 10;
    }
    return DP(num, 0, 0);
}
int main()
{
    int t;
    LL n, m;
    while (~scanf("%lld%lld", &n, &m), n + m)
    {
        printf("%lld\n", m-n+1-solve(m) + solve(n - 1));
    }
    return 0;
}