首页 > 代码库 > 不要62

不要62

题目链接

  • 题意:
    求出a到b之间     1)不含有连续的62        2)不含有4
    的数的个数
  • 分析:
    两种状态,记录62。4直接判断即可
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 == 2) || i == 4) continue;
        int nxt = 0;
        if (i == 6) 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);
    LL a, b;
    while (cin >> a >> b && a)
        cout << calc(b) - calc(a - 1) << endl;
    return 0;
}


不要62