A85104.不要62
2026-03-14 19:33:23
发布于：四川
4阅读
0回复
0点赞
小引
起因是bro在做“就要62”这道入门题，发现了它的好bro“不要62”，如你所见它没有几个人过并且还是一道“提高+/省选-”的题，so,我打算发一个题解
问题分析
这道题要求统计区间 [n, m] 内不包含数字 4 且不包含连续数字 62 的数的个数。直接暴力枚举每个数并检查会超时（因为 m 可以接近 10^7），所以需要用数位动态规划（数位 DP） 来高效解决。
数位 DP 的核心思想是：将数字按位分解，通过状态记录关键信息（如前一位是否是 6），递归 / 记忆化搜索所有合法的数字组合，避免重复计算。
完整代码
有注释版
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm> // 新增：包含reverse函数所需的头文件
using namespace std;
// dp[pos][pre][limit]：
// pos：当前处理到第几位（从高位到低位）
// pre：前一位的数字（记录是否是6，用于判断62）
// limit：当前位是否受原数字的限制
int dp[8][10][2]; // 数字最多7位，pre范围0-9，limit是0/1
vector<int> digits; // 存储数字的每一位
// 记忆化搜索
int dfs(int pos, int pre, bool limit) {
// 递归终止：所有位处理完，找到一个合法数
if (pos == digits.size()) return 1;
// 记忆化：如果当前状态已经计算过，直接返回
if (!limit && dp[pos][pre][limit] != -1) {
return dp[pos][pre][limit];
}
// 当前位的上界：有limit则为digits[pos]，否则为9
int up = limit ? digits[pos] : 9;
int res = 0; // 统计合法数的个数
// 枚举当前位可能的数字
for (int i = 0; i <= up; i++) {
// 跳过不吉利的数字：包含4 或 前一位是6且当前位是2
if (i == 4 || (pre == 6 && i == 2)) {
continue;
}
// 递归处理下一位
res += dfs(pos + 1, i, limit && (i == up));
}
// 记忆化存储：仅存储无限制的状态
if (!limit) {
dp[pos][pre][limit] = res;
}
return res;
}
// 计算0~x中合法的数字个数
int calc(int x) {
digits.clear();
// 将x分解为各位数字（高位到低位）
if (x == 0) {
digits.push_back(0);
} else {
while (x) {
digits.push_back(x % 10);
x /= 10;
}
reverse(digits.begin(), digits.end()); // 现在可以正常使用reverse
}
// 初始化dp数组为-1（表示未计算）
memset(dp, -1, sizeof(dp));
// 从第0位开始搜索，前一位初始为0，有上界限制
return dfs(0, 0, true);
}
int main() {
int n, m;
// 循环输入，直到0 0结束
while (cin >> n >> m && (n || m)) {
// 区间[n, m]的合法数 = 0~m的合法数 - 0~(n-1)的合法数
cout << calc(m) - calc(n - 1) << endl;
}
return 0;
}
无注释版
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
int dp[8][10][2];
vector<int> digits;
int dfs(int pos, int pre, bool limit) {
if (pos == digits.size()) return 1;
if (!limit && dp[pos][pre][limit] != -1) {
return dp[pos][pre][limit];
}
int up = limit ? digits[pos] : 9;
int res = 0;
for (int i = 0; i <= up; i++) {
if (i == 4 || (pre == 6 && i == 2)) {
continue;
}
res += dfs(pos + 1, i, limit && (i == up));
}
if (!limit) {
dp[pos][pre][limit] = res;
}
return res;
}
int calc(int x) {
digits.clear();
if (x == 0) {
digits.push_back(0);
} else {
while (x) {
digits.push_back(x % 10);
x /= 10;
}
reverse(digits.begin(), digits.end());
}
memset(dp, -1, sizeof(dp));
return dfs(0, 0, true);
}
int main() {
int n, m;
while (cin >> n >> m && (n || m)) {
cout << calc(m) - calc(n - 1) << endl;
}
return 0;
}
代码解释
1.核心函数 calc(x)：计算 0~x 中合法的数字个数，是数位 DP 的入口：
- 将数字 x 分解为各位（如 123 分解为 [1,2,3]），存储到 digits 数组。
- 初始化 DP 数组，调用 dfs 进行记忆化搜索。
2.记忆化搜索 dfs(pos, pre, limit)：
- 终止条件：pos == digits.size()，表示所有位处理完，返回 1（找到一个合法数）。
- 记忆化优化：如果当前状态（无限制）已计算过，直接返回结果，避免重复递归。
- 枚举当前位：遍历 0~up（up 是当前位的上界），跳过含 4 或 62 的情况。
- 递归下一位：传递新的状态（下一位、当前位数字、新的限制），累加合法数个数。
3.主函数：
- 输入 n, m，直到 0 0 结束。
- 区间 [n, m] 的合法数 = calc(m) - calc(n-1)（容斥原理）。
测试用例验证
输入：1 100
- calc(100)：0~100 中合法数的个数是 81（包含 0）。
- calc(0)：0 是合法数，返回 1。
- 结果：81 - 1 = 80，与样例输出一致。
总结
1.核心思路：用数位 DP 避免暴力枚举，通过记忆化搜索统计合法数字个数，时间复杂度为 O (位数 × 10 × 2)，效率极高。
2.关键状态：记录当前处理的位数、前一位数字、是否有上界限制，确保不重复计算且不遗漏合法数字。
3.容斥原理：区间 [n, m] 的结果 = calc(m) - calc(n-1)，需注意边界（如 n=1 时，n-1=0）。
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
你以为这就完了吗？
别忘了为什么我要说这个题没几个人做过，因为我想拿那三颗宝石
要想拿到宝石，就必须控制内存和时间
极致优化版
带注释
#include <cstdio>
using namespace std;
// 全局变量说明：
// num[c]：存储10的c次方，用于快速提取数字的第c位（如num[1]=10，num[2]=100）
// dp[c][0]：预处理的c位数中，最高位是6的合法数个数（合法：不含4、不含连续62）
// dp[c][1]：预处理的c位数中，最高位不是6的合法数个数
long long num[10], dp[10][2];
int main() {
// ====================== 预处理阶段：初始化边界值 ======================
// dp[0][0]：0位数（空数）的状态，最高位是6的合法数为0（无意义，仅作为递推边界）
// dp[0][1]：0位数的状态，最高位不是6的合法数为1（空数视为1个合法状态）
dp[0][0] = 1, dp[0][1] = 0;
// num[0]=1=10^0，num[1]=10=10^1（1位数的位权）
// dp[1][0]=8：1位数（0-9）中，排除4后剩余9个数，最高位是6的合法数为1，此处为递推兼容值
// dp[1][1]=1：1位数中，最高位不是6的合法数个数（1-3,5,7-9共7个，此处为递推兼容值）
num[0] = 1, num[1] = 10, dp[1][0] = 8, dp[1][1] = 1;
// ====================== 预处理阶段：递推计算各长度的合法数 ======================
// c表示当前处理的位数（2~7位，适配题目10^7以内的数）
for (int c = 2; c <= 7; c++) {
num[c] = num[c - 1] * 10; // 计算10^c，如c=2时num[2]=100
// 状态转移核心逻辑：
// dp[c][0]（当前位是6）：
// - 前一位是6（dp[c-1][0]）：后c-1位不能是4/2（避免62），共8种选择
// - 前一位非6（dp[c-1][1]）：后c-1位不能是4，共7种选择
dp[c][0] = dp[c - 1][0] * 8 + dp[c - 1][1] * 7;
// dp[c][1]（当前位非6）：
// - 无论前一位是否是6，当前位非6且非4，后c-1位合法数总和为dp[c-1][0]+dp[c-1][1]
dp[c][1] = dp[c - 1][0] + dp[c - 1][1];
}
// ====================== 主逻辑：处理输入并计算区间合法数 ======================
int l, r; // 输入的区间[l, r]
long long ans; // 最终答案：[l, r]内的合法数个数
while (1) {
scanf("%d%d", &l, &r); // 读取输入的区间
if (l == 0 && r == 0) // 输入0 0时终止程序
return 0;
ans = 0; // 初始化答案，先计算0~r的合法数个数
// ---------------------- 计算0~r的合法数个数 ----------------------
// c从最高位（7位）到最低位（1位）逐位处理
for (int c = 7; c > 0; c--) {
// 提取当前位的数字：r / num[c-1] % 10（如c=7时，提取千万位）
// 枚举当前位从0到“当前位数字-1”的所有可能值，统计合法数
for (int i = r / num[c - 1] % 10 - 1; i >= 0; i--) {
if (i == 6) {
// 当前位是6，累加“最高位是6”的合法数个数
ans += dp[c - 1][0];
} else if (i == 2 && r / num[c] % 10 == 6) {
// 当前位是2且前一位是6（构成62），不吉利，跳过
continue;
} else if (i == 4) {
// 当前位是4，不吉利，跳过
continue;
} else {
// 其他合法数字，累加所有合法数个数
ans += dp[c - 1][0] + dp[c - 1][1];
}
}
// 检查当前位是否触发不吉利条件，触发则终止后续位的统计
// 条件1：当前位是2且前一位是6（构成62），需修正计数并终止
if (r / num[c - 1] % 10 == 2 && r / num[c] % 10 == 6) {
ans--;
break;
}
// 条件2：当前位是4，不吉利，需修正计数并终止
if (r / num[c - 1] % 10 == 4) {
ans--;
break;
}
}
ans++; // 补全边界：包含r本身的合法数（若r合法）
// ---------------------- 减去0~l-1的合法数个数 ----------------------
l--; // 计算0~l-1的合法数，等价于原区间[l, r] = 0~r - 0~(l-1)
for (int c = 7; c > 0; c--) {
// 逻辑与计算0~r完全对称，只是累加改为累减
for (int i = l / num[c - 1] % 10 - 1; i >= 0; i--) {
if (i == 6) {
ans -= dp[c - 1][0];
} else if (i == 2 && l / num[c] % 10 == 6) {
continue;
} else if (i == 4) {
continue;
} else {
ans -= dp[c - 1][0] + dp[c - 1][1];
}
}
// 检查不吉利条件，修正计数
if (l / num[c - 1] % 10 == 2 && l / num[c] % 10 == 6) {
ans++;
break;
}
if (l / num[c - 1] % 10 == 4) {
ans++;
break;
}
}
ans--; // 补全边界：减去l-1本身的合法数（若l-1合法）
// 输出最终答案：[原l, r]内的合法数个数
printf("%lld\n", ans);
}
}
不带注释
#include <cstdio>
using namespace std;
long long num[10], dp[10][2];
int main() {
dp[0][0] = 1, dp[0][1] = 0;
num[0] = 1, num[1] = 10, dp[1][0] = 8, dp[1][1] = 1;
for (int c = 2; c <= 7; c++)
num[c] = num[c - 1] * 10, dp[c][0] = dp[c - 1][0] * 8 + dp[c - 1][1] * 7,
dp[c][1] = dp[c - 1][0] + dp[c - 1][1];
int l, r;
long long ans;
while (1) {
scanf("%d%d", &l, &r);
if (l == 0 && r == 0)
return 0;
ans = 0;
for (int c = 7; c > 0; c--) {
for (int i = r / num[c - 1] % 10 - 1; i >= 0; i--) {
if (i == 6)
ans += dp[c - 1][0];
else if (i == 2 && r / num[c] % 10 == 6)
continue;
else if (i == 4)
continue;
else
ans += dp[c - 1][1] + dp[c - 1][0];
}
if (r / num[c - 1] % 10 == 2 && r / num[c] % 10 == 6) {
ans--;
break;
}
if (r / num[c - 1] % 10 == 4) {
ans--;
break;
}
}
ans++;
l--;
for (int c = 7; c > 0; c--) {
for (int i = l / num[c - 1] % 10 - 1; i >= 0; i--) {
if (i == 6)
ans -= dp[c - 1][0];
else if (i == 2 && l / num[c] % 10 == 6)
continue;
else if (i == 4)
continue;
else
ans -= dp[c - 1][0] + dp[c - 1][1];
}
if (l / num[c - 1] % 10 == 2 && l / num[c] % 10 == 6) {
ans++;
break;
}
if (l / num[c - 1] % 10 == 4) {
ans++;
break;
}
}
ans--;
printf("%lld\n", ans);
}
}
注释核心说明
1.分段注释：将代码分为「预处理初始化」「预处理递推」「主逻辑计算」三大块，逻辑边界清晰；
2.变量注释：每个全局 / 局部变量都标注用途，尤其是dp数组的状态定义（新手最难理解的部分）；
3.状态转移注释：详细解释dp[c][0]和dp[c][1]的递推逻辑，包括每一步的选择数来源；
4.边界处理注释：对ans++/ans--、break等关键边界修正逻辑标注原因；
5.逐位统计注释：解释 “枚举当前位 0~ 当前值 - 1” 的核心思想，以及不吉利数字的过滤逻辑。
这里空空如也
有帮助，赞一个