自动搬运

查看原文

来自洛谷，原作者为

	Maxmilite **

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

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

以下是正文

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;

视频题解

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