【第008题】题解及代码分享：记忆化搜索挂了，数位DP[ZJOI2010] 数字计数

小码匠

发布于 2023-11-14 19:39:26

33600

代码可运行

文章被收录于专栏：小码匠和老码农小码匠和老码农

运行总次数：0

代码可运行

大家好！我是小码匠。

今天分享的题目继续是数位DP，可惜我的记忆化搜索写挂了。

emo。。。

路漫漫其修远兮，吾将上下而求索

离自己的既定目标：

目标：300道
已完成：8道
待完成：292道

已完成目标：

分类	算法	题目
算法基础	前缀和	【第001题】题解分享：湖南省选->激光炸弹
算法基础	差分	【第002题】题解分享：P4552 [Poetize6] IncDec Sequence
算法基础	高维前缀和	【第003题】题解及代码分享：CodeForces 165E Compatible Numbers
算法基础	尺取	【第004题】题解及代码分享：AtCoder ABC326-C
动态规划	动态规划	【第005题】题解及代码分享：AtCoder ABC326-D
算法基础	高维前缀和	【第006题】题解及代码分享：高位前缀和之AtCoder ARC100 - E Or Plus Max
动态规划	数位DP	【第007题】题解及代码分享：数位DP经典模版题 [SCOI2009] windy 数
动态规划	数位DP	【第008题】题解及代码分享：数位DP[ZJOI2010] 数字计数

前置知识

数位DP
- https://oi-wiki.org/dp/number/

题目描述

给定两个正整数 a 和 b，求在 [a,b] 中的所有整数中，每个数码(digit)各出现了多少次。

输入格式

仅包含一行两个整数 a,b，含义如上所述。

输出格式

包含一行十个整数，分别表示 0∼9 在 [a,b] 中出现了多少次。

输入输出样例

输入 #1复制

1 99

输出 #1复制

9 20 20 20 20 20 20 20 20 20

说明/提示

数据规模与约定

对于 30% 的数据，保证

a≤b≤10^6

；

对于 100% 的数据，保证

1≤a≤b≤10^{12}

。

题解

思路

AC代码

#include <bits/stdc++.h>

using namespace std;

long long l, r, dp[20], digit[20], a[20];

void calc(long long n, vector<long long> &ans) {
    long long cnt = n;
    int len = 0;
    while (n > 0) {
        a[++len] = n % 10;
        n /= 10;
    }
    for (int i = len; i > 0; --i) {

        for (int j = 0; j < 10; ++j) {
            ans[j] += dp[i - 1] * a[i];

        }
        for (int j = 0; j < a[i]; ++j){
            ans[j] += digit[i - 1];

        }
        cnt -= digit[i - 1] * a[i];
        ans[a[i]] += cnt + 1;
        ans[0] -= digit[i - 1];
    }
}


void coder() {
    cin >> l >> r;
    digit[0] = 1;
    vector<long long> ans_1(20);
    vector<long long> ans_2(20);
    for (int i = 1; i <= 13; ++i) {
        dp[i] = dp[i - 1] * 10 + digit[i - 1];
        digit[i] = 10 * digit[i - 1];
    }
    calc(r, ans_1);
    calc(l - 1, ans_2);
    for (int i = 0; i < 10; ++i) {
        cout << ans_1[i] - ans_2[i] << " ";
    }
}

int main() {
    coder();
    return 0;
}

DFS(记忆化搜索)：挂了

下面代码只有30分，挂了，尚未找到哪错了。

#include <bits/stdc++.h>

using namespace std;

long long l, r, dp[20], digit[20], a[20];

void solve(long long n, vector<long long> &ans) {
    long long cnt = n;
    int len = 0;
    while (n > 0) {
        a[++len] = n % 10;
        n /= 10;
    }
    for (int i = len; i > 0; --i) {

        for (int j = 0; j < 10; ++j) {
            ans[j] += dp[i - 1] * a[i];

        }
        for (int j = 0; j < a[i]; ++j) {
            ans[j] += digit[i - 1];

        }
        cnt -= digit[i - 1] * a[i];
        ans[a[i]] += cnt + 1;
        ans[0] -= digit[i - 1];
    }
}


void best_coder() {
    cin >> l >> r;
    digit[0] = 1;
    vector<long long> ans_1(20);
    vector<long long> ans_2(20);
    for (int i = 1; i <= 13; ++i) {
        dp[i] = dp[i - 1] * 10 + digit[i - 1];
        digit[i] = 10 * digit[i - 1];
    }
    solve(r, ans_1);
    solve(l - 1, ans_2);
    for (int i = 0; i < 10; ++i) {
        cout << ans_1[i] - ans_2[i] << " ";
    }
}

long long dp_dfs[20][20], num[20];

long long dfs(int len, bool same, int cnt, bool zero, int x) {
    long long sum = 0;
    if (len == 0) {
        return cnt;
    }

    if (dp_dfs[len][cnt] != -1 && zero && same) {
        return dp_dfs[len][cnt];
    }

    for (int i = 0; i < 10; ++i) {
        if (!same && i > num[len]) {
            break;
        }
        sum += dfs(len - 1, same || (i < num[len]), cnt + ((!zero || i > 0) && (i == x)), zero && (i == 0), x);

    }
    if (!zero && same) {
        dp_dfs[len][cnt] = sum;
    }

    return sum;
}

int answer(long long n,  int x) {
    memset(dp_dfs, -1, sizeof(dp_dfs));
    int len = 0;
    while (n > 0) {
        num[++len] = n % 10;
        n /= 10;
    }
    return dfs(len, false, 0, true, x);
}

void happy_coder() {
    cin >> l >> r;
    for (int i = 0; i < 10; ++i) {
        cout << answer(r, i) - answer(l - 1, i) << " ";
    }
}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    //best_coder();

    // 最优解
    happy_coder();

    return 0;
}