大家好！我是小码匠。
今天分享的题目继续是数位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复制
代码语言：javascript复制1 99
输出 #1复制
代码语言：javascript复制9 20 20 20 20 20 20 20 20 20
说明/提示
数据规模与约定
- 对于 30% 的数据，保证
；
- 对于 100% 的数据，保证
。
题解
思路
AC代码
代码语言：javascript复制#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;
}
END
