首页 > 代码库 > Bomb

Bomb

题目链接

  • 题意:
    求1-x中出现连续的49的数有多少个(注意要用long long)
  • 分析:
    计算不包括连续的49或者计算包括连续的49。两种方法都差不多,简单的数位DP
LL f[100][2], bits[100];

LL dfs(int pos, int s, bool lmt)
{
    if (pos == -1) return 1;
    if (!lmt && ~f[pos][s]) return f[pos][s];
    int u = lmt ? bits[pos] : 9;
    LL ret = 0;
    for (int i = 0; i <= u; i++)
    {
        if (s == 1 && i == 9) continue;
        int nxt = 0;
        if (i == 4) nxt = 1;
        ret += dfs(pos - 1, nxt, lmt && i == u);
    }
    return lmt ? ret : f[pos][s] = ret;
}

LL calc(LL n)
{
    CLR(f, -1);
    LL len = 0;
    while (n)
    {
        bits[len++] = n % 10;
        n /= 10;
    }
    return dfs(len - 1, 0, true);
}

int main()
{
    //freopen("0.txt", "r", stdin);
    int T;
    RI(T);
    FE(kase, 1, T)
    {
        LL n;
        cin >> n;
        cout << 1 + n - calc(n) << endl;
    }
    return 0;
}


Bomb