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

· · 题解

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 记录「变化」的位的数量。

比较分为以下情况：

如果在上述的枚举过程中没有出现「直接判断为不符合要求」的情况，则将 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;

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

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

视频题解

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