当前位置:首页 > 枚举 > 正文
洛谷P9868词典(NOIP2023)
224+

题目大意:n个单词,可以调整每个单词的字母顺序问每个单词,是否有可能成为字典序最小的单词?

题目描述

小 S 的词典里有 $n$ 个两两不同的、长度均为 $m$ 的单词 $w_1,w_2,\cdots,w_n$。每个单词都是一个小写字母构成的字符串。

小 S 可以做以下操作任意多次(可以不做):选择词典中的任意一个单词,交换其中任意两个字符。

对于每个 $1 \le i \le n$,小 S 想知道,是否可以通过以上操作得到新的 $n$ 个单词 $w’_1,w’_2,\cdots , w’_n$,使得对于每个 $j \neq i$,$w’_i$ 的字典序比 $w’_j$ 都要小。**对于 $n=1$ 的情况,我们约定:上述性质是自然成立的。**

对于两个同样长度的字符串 $s = s_1s_2\cdots s_L$ 和 $t = t_1t_2 \cdots t_L$,称字符串 $s$ 字典序小于字符串 $t$,当且仅当以下条件成立:存在位置 $i$,在第 $i$ 个字符之前 $s$ 和 $t$ 都相同,而且 $s_i < t_i$,即小写字母 $s_i$ 在英文字母顺序中先于 $t_i$。

输入输出格式

输入格式

输入的第一行包含两个正整数 $n$ 和 $m$,分别表示单词个数和单词长度。

接下来 $n$ 行,每行包含一个长度为 $m$ 的小写字母字符串 $w_i$, 表示一个单词。

输出格式

输出一行,其中包含一个长度为 $n$ 的 `01` 字符串 $a$;对于 $1 \le i \le n$,如果题目描述中的性质成立,则 $a_i =$ `1`,否则 $a_i =$ `0`。

输入输出样例

输入样例 #1

4 7
abandon
bananaa
baannaa
notnotn

输出样例 #1

1110

说明

**【样例解释 #1】**

– 不做任何操作,第一个单词字典序最小,因此输出第一个字符为 `1`;
– 交换 `bananaa` 的前两个字符以及 `abandon` 的第三个和第六个字符,得到 `abondan`, `abnanaa`, `baannaa`, `notnotn`,此时第二个单词字典序最小,因此输出第二个字符为 `1`;
– 交换 `baannaa` 的第一个和最后一个字符得到 `aaannab`,其余字符串不变,此时第三个单词字典序最小,因此输出第三个字符为 `1`;
– 无论如何操作,第四个单词不会小于第二个单词,因此输出第四个字符为 `0`。

**【样例解释 #2】**

该组样例满足测试点 $4$ 的限制。

**【样例解释 #3】**

该组样例满足测试点 $7$ 的限制。

**【样例解释 #4】**

该组样例满足测试点 $10$ 的限制。

**【数据范围】**

对于所有测试数据,保证:$1 \le n \le 3000$,$1 \le m \le 3000$,$w_i$ 为长度为 $m$ 的小写字母字符串且两两不同。

| 测试点编号 | $n\leq$ | $m\leq$ |
| :———-: | :———-: | :———-: |
| $1$ | $1$ | $1$ |
| $2\sim 4$ | $26$ | $1$ |
| $5\sim 7$ | $15$ | $2$ |
| $8$ | $300$ | $300$ |
| $9$ | $10^3$ | $10^3$ |
| $10$ | $3000$ | $3000$ |

解题思路

可以对每个单词进行桶排序,对于自己是否可能成为最小,只需要从a~z遍历,其他单词从z~a遍历,时间复杂度$O(n^2logn)$。

不拿发现,只有发现一个位置小即可,只需要最小的字母比其他单词最大的字母小就行,如果条件不成立,后面比下去也没有意义——不可能出现比我小的字母,因为我自己递增,其他单词递减。

结论:最小字母小于其他单词最大字母才可能是字典序最小的单词,只需要预处理每个单词最小最大字母,枚举验证即可,时间复杂度$O(n^2)$。

程序实现

报歉!评论已关闭.