洛谷P2602 [ZJOI2010]数字计数题解数位DP

题目链接：https://www.luogu.com.cn/problem/P2602

题目大意：

计算区间 \([L,R]\) 范围内 \(0 \sim 9\) 各出现了多少次？

解题思路：

使用 数位DP 进行求解。

定义一个结构体数组 \(f[pos][all0]\) 表示满足如下条件时 \(0 \sim 9\) 出现的次数：

当前所在数位为第 \(pos\) 位；
\(all0\) 为 \(1\) 表示当前状态之前一直都是前置 \(0\) ，为 \(0\) 表示前面的数位上面出现过不为 \(0\) 的数。

然后定义一个返回值为此结构体类型的函数 dfs(int pos, int all0, bool limit) 进行求解，其中：

\(pos\) 和 \(all0\) 的含义同上；
\(limit\) 表示是否处于限制状态。

实现代码如下：

// P2602 [ZJOI2010]数字计数

#include <bits/stdc++.h>

using namespace std;

long long cnt[10], pow10[22], num;

int a[22];

struct Node {

    long long arr[10];

    Node() { memset(arr, 0, sizeof(arr)); }

    void merge(Node v) {

        for (int i = 0; i < 10; i ++)

            arr[i] += v.arr[i];

    }

} f[22][2];

bool vis[22][2];

void init() {

    pow10[0] = 1;

    for (int i = 1; i <= 18; i ++) pow10[i] = pow10[i-1] * 10;

}

Node dfs(int pos, int all0, bool limit) {

    if (pos < 0) return Node();

    if (!limit && vis[pos][all0]) return f[pos][all0];

    int up = limit ? a[pos] : 9;

    Node tmp = Node();

    for (int i = 0; i <= up; i ++) {

        if (i == 0 && all0 && pos>0) ;

        else {

            if (limit && i==up) tmp.arr[i] += num % pow10[pos] + 1;

            else tmp.arr[i] += pow10[pos];

        }

        tmp.merge(dfs(pos-1, all0&&i==0, limit&&i==up));

    }

    if (!limit) {

        vis[pos][all0] = true;

        f[pos][all0] = tmp;

    }

    return tmp;

}

Node get_num(bool minus1) {

    long long x;

    cin >> x;

    if (minus1) x --;

    num = x;

    int pos = 0;

    while (x) {

        a[pos++] = x % 10;

        x /= 10;

    }

    if (num == 0) a[pos++] = 0;

    return dfs(pos-1, true, true);

}

int main() {

    init();

    Node res_l = get_num(true);

    Node res_r = get_num(false);

    for (int i = 0; i < 10; i ++) {

        if (i) putchar(' ');

        cout << res_r.arr[i] - res_l.arr[i];

    }

    cout << endl;

    return 0;

}

巴特西

洛谷P2602 [ZJOI2010]数字计数题解数位DP

最新文章

热门文章

巴特西

洛谷P2602 [ZJOI2010]数字计数 题解 数位DP

最新文章

热门文章

洛谷P2602 [ZJOI2010]数字计数题解数位DP