B3690 [语言月赛202212] 盒武器 题解

· · 题解

B3690 [语言月赛202212] 盒武器 题解

Source & Knowledge

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

文字题解

题目大意

给定两个字符串 s 和 t。重新定义 26 个字母之间的大小关系，使得按照新定义的大小关系，t 的字典序小于 s 的字典序。

解析

提供两种做法。第一种比较容易想到，但是码量较大。第二种码量极短，但是可能有点难想到。

第一种做法如下：

我们注意到 t < s 的两个条件为「t 是 s 的一个前缀」或「存在一个位置 j \leq \min(|s|, |t|)，使得对 1 \leq i < j 都有 s_i = t_i 且 t_j < s_j」。自然而然地，t > s 的两个条件为「s 是 t 的一个前缀」或「存在一个位置 j \leq \min(|s|, |t|)，使得对 1 \leq i < j 都有 s_i = t_i 且 t_j > s_j」。

由于题目保证了 s \neq t，因此 t 与 s 的关系只有以上四种可能。

考虑 t > s 的两个条件。对第一个条件，显然，我们不可能通过调整字母之间的大小关系使得 t < s，且题目保证了数据一定有解，所以这种情况一定不存在。

现在我们需要下手的情况只有一个了，即「存在一个位置 j \leq \min(|s|, |t|)，使得对 1 \leq i < j 都有 s_i = t_i 且 t_j > s_j」。

不难发现，这种情况下，我们只需要修改 t _ j 与 s _ j 的大小关系，使之满足 t _ j < s _ j 即可。因此，我们对这两位单独处理，其余的按照任意顺序输出即可。

以下为此做法的核心代码：

scanf("%s%s", s, t);
lenS = strlen(s);
lenT = strlen(t);
int ptr = 0, minLength = min(lenS, lenT);
while (ptr < minLength) {
    if (s[ptr] != t[ptr])
        break;
    ++ptr;
}
if (ptr == minLength) {
    for (int i = 'a'; i <= 'z'; ++i) {
        printf("%c", i);
    }
} else {
    char a = t[ptr], b = s[ptr];
    printf("%c%c", a, b);
    for (int i = 'a'; i <= 'z'; ++i) {
        if (i != a && i != b)
            printf("%c", i);
    }
}

第二种做法如下：

由第一种做法，我们知道，如果 t > s，我们只需要修改「存在一个位置 j \leq \min(|s|, |t|)，使得对 1 \leq i < j 都有 s_i = t_i 且 t_j > s_j」条件下 s _ j 与 t _ j 的关系即可。

我们考虑，如果我们将整个字母表的大小关系反转，即 \texttt{z} < \texttt{y} < \cdots < \texttt{b} < \texttt{a}，那么无论 s _ j 与 t _ j 是哪个字母，只要原来 s _ j < t _ j，那么在反转后的字母表中，t _ j 一定小于 s _ j。由此，我们即可保证 t < s。

所以这一种做法的代码量少得可怕，核心代码如下：

string s, t;
cin >> s >> t;
if (s > t) cout << "abcdefghijklmnopqrstuvwxyz" << endl;
else cout << "zyxwvutsrqponmlkjihgfedcba" << endl;

视频题解

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