P9868 [NOIP2023] 词典

· · 个人记录

Description

给定 n 个两两不同的、长度均为 m 的字符串 w_i。你可以进行如下操作任意次：

你需要求出对于每个 1 \le i \le n，能否通过若干次上述操作，使得 w_i 变为所有字符串中字典序严格最小的。

Solution

若 n = 1，则显然答案为可以。特判输出即可。接下来讨论的都是 n \ne 1 的情况。

首先题目中的操作，可以理解为将某个字符串打乱字符顺序。那么如果想让 w_i 成为所有字符串中字典序严格最小的，那么也就是希望让 w_i 自己变成一种字典序最小的排列，并让字符串 w_j(j \ne i) 变成一种字典序最大的排列。那么很显然我们需要将字符串 w_i 中的字符从小到大排序，将字符串 w_j(j \ne i) 中的字符从大到小排序。

然后我们需要判断处理后的 w_i' 是否比所有的 w_j'(j \ne i) 小。如果这样暴力做时间复杂度会爆炸。考虑优化。

考虑这样一个问题，如果要判断某一个数 x 是否小于若干个数中的每一个，那么只需要找到这若干个数中的最小值，并将这个最小值和 x 比较即可。

同理，在这个题中，判断处理后的 w_i' 是否比所有的 w_j'(j \ne i) 小，只需要找到所有的 w_j'(j \ne i) 中的最小值与 w_i' 进行比较即可。可以发现，每次计算都是与同一个最小值进行比较，所以我们可以提前求出这个 w_x' 来，然后计算时只与这一个字符串比较即可。

这样做还会有一个问题。假如所有 w_i' 的最小值为 w_x'，那么在计算 i = x 的答案时就不能与这个字符串作比较了，因为我们要做的是判断当前字符串是否小于其它字符串。所以我们还需要维护次小值 w_y'，然后在 i \ne x 时将 w_i' 与 w_x' 比较，在 i = x 时将 w_i' 与 w_y' 作比较即可。

Code

赛时我的几个时间优化：

  1. 上面说了，需要将 w_i 按字符从大到小排序得到新字符串 w_i'，但如果实际排序复杂度是 \Theta(m \log m) 的，算了一下可能会超时。因此这里用桶排代替了 std::sort；

  2. 上面有多处用到了字符串的大小比较，这毋庸置疑用 string 更为好写。但为了保险，我还是用的字符数组，以至于手写了四个字符串比较函数；

  3. std::cin 和 scanf 效率较低，我手写的 getchar() 读入字符串。

考场上的代码，差不多一小时做出来的。