思路
数位 dp
数位 dp
数位 dp 模版题。
依次考虑每一位，满足题目给出的限制，统计数量，是一些较简单的数位 dp 题目的过程。
数位 dp 运用了差分的思想，即求 \(ans(l - r)\) 的答案用 \(ans(1 - r) - ans(1-(l - 1))\) 来表示.
对于本题，我们需要满足的性质很简单：
- 使数不超过上界，如求 \([5 - 1000]\) 不能使 \(1005\)
- 考虑到某一位时，如果其前一位为 \(6\)，那么则一位不能为 \(2\)，如果这一位填了 \(6\)，下一位不能填 \(2\)。
- 任何一位不能是 \(4\)。
条件 1 是数位 dp 的常规操作，条件 2 和 条件 3 均可以在 dp 过程中通过检查标记来满足。
具体见代码。
代码
点击查看代码
/*
--------------------------------
| code by FRZ_29 |
| code time |
| 2024/08/11 |
| 16:09:04 |
| 星期天 |
--------------------------------
*/
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdio>
#include <ctime>
using namespace std;
void RD() {}
template<typename T, typename... U> void RD(T &x, U&... arg) {
x = 0; int f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
x *= f; RD(arg...);
}
const int N = 1e6 + 5, M = 10;
#define LF(i, __l, __r) for (int i = __l; i <= __r; i++)
#define RF(i, __r, __l) for (int i = __r; i >= __l; i--)
int n, m, num[N];
int f[M][2][2];
int dfs(int u, bool lim, bool lim_6) { // lim 为条件 1 的限制，lim_6 为条件 3 的限制
if (u == 0) return 1;
if (f[u][lim][lim_6] != -1) return f[u][lim][lim_6]; // 记忆化搜索能优化时间复杂度
// printf("u = %d, lim = %d, lim_6 = %d\n", u, lim, lim_6);
int up = (lim ? num[u] : 9);
f[u][lim][lim_6] = 0;
LF(i, 0, up) {
if (i == 4 || (lim_6 && i == 2)) continue;
f[u][lim][lim_6] += dfs(u - 1, lim == true & i == up, i == 6);
}
return f[u][lim][lim_6];
}
int calc(int n) {
if (n < 0) return 0;
int tmp = n;
int cnt = 0;
while (tmp) num[++cnt] = tmp % 10, tmp /= 10;
LF(i, 1, cnt) LF(j, 0, 1) LF(k, 0, 1) f[i][j][k] = -1;
return dfs(cnt, 1, 0);
}
int main() {
// freopen("read.in", "r", stdin);
// freopen("out.out", "w", stdout);
// time_t st = clock();
while (RD(n, m), n, m) printf("%d\n", calc(m) - calc(n - 1));
// printf("\n%dms", clock() - st);
return 0;
}
/* ps:FRZ弱爆了
* 这是 FRZ 第 1 道数位 dp 题
* FRZ做的太少了（悲
* 真是弱爆了
*/
标签：HDU,ch,return,int,题解,62,lim,dp,数位 From： https://www.cnblogs.com/FRZ29/p/18353639在逆风里把握方向，做暴风雨中的海燕，做不改颜色的孤星。