自动搬运

查看原文

来自洛谷，原作者为

	Maxmilite **

搬运于2025-08-24 21:14:25，当前版本为作者最后更新于2022-12-11 21:26:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

B3689 [语言月赛202212] 宇宙密码 题解

Source & Knowledge

2022 年 12 月语言月赛，由洛谷网校入门计划/基础计划提供。

文字题解

题目大意

给定整数 $a$，求 $a$ 的至多 $k$ 位进行「变化」后的所能形成的所有可能数字。

某一位发生「变化」，指这一位的数字 $\pm 1$。其中 $0$ 和 $9$ 需要特殊处理，详细内容可以参照原题面。

解析

提供一种比较简单的做法。

我们注意到数字至多只可能有 $6$ 位。也就是说，最后的答案只可能在 $000000 \sim 999999$ 中取得，至多有 $10 ^ 6$ 个可能的答案。又可以发现，我们直接从 $a$ 推到最后的答案较为困难，可能使用深度优先搜索等超纲算法。然而，我们验证某一个数 $b$ 是否是最后的答案是比较简单的，只需要进行一定的判断即可。

所以，我们可以逐个枚举 $0 \sim 10 ^ n - 1$，并逐个判断及输出即可。

下面介绍一下判断流程。

我们不妨设当前枚举到的整数是 $x$。对于判断，我们可以逐个取 $x$ 的十进制位与原数字 $a$ 的对应位进行比较，并取一个初始化为 $0$ 变量 $c$ 记录「变化」的位的数量。

比较分为以下情况：

• 如果 $x$ 的当前位与 $a$ 的对应位相同，则不做处理。
• 如果 $x$ 的当前位与 $a$ 的对应位的差值的绝对值为 $1$ 或 $9$，则上述的变量 $c$ 增加 $1$。
• 如果 $x$ 的当前位与 $a$ 的对应位的差值绝对值 $\geq 2$ 且 $\neq 9$，则直接判断 $x$ 不符合要求。

如果在上述的枚举过程中没有出现「直接判断为不符合要求」的情况，则将 $c$ 与 $k$ 比较。如果 $c \leq k$，则 $x$ 符合要求，反之不符合要求。

以下是判断流程的代码，使用 check 函数实现：

int check(int x) {
	int cnt = 0, var = a;
	for (int i = 1; i <= n; ++i) {
		if (abs((var % 10) - (x % 10)) == 1 || abs((var % 10) - (x % 10)) == 9) {
			++cnt;
		} else if (abs((var % 10) - (x % 10)) >= 2) {
			return 0;
		}
		var /= 10, x /= 10;
	}
	return cnt <= k;
}

枚举 $0 \sim 10 ^ n - 1$ 的代码如下：

cin >> n >> a >> k;
int limit = pow(10, n);
for (int i = 0; i < limit; ++i) {
	if (check(i)) {
		cout << i << endl;
	}
}
return 0;

由于枚举顺序，自然而然我们保证了从小到大输出。

可以看到，整体的代码量是较小的。

视频题解

完整代码请在视频中查看。