【NOIP2023】词典 - 题目 - Universal Online Judge

小 S 的词典里有 $n$ 个两两不同的、长度均为 $m$ 的单词 $w_{1}, w_{2}, \dots, w_{n}$ 。每个单词都是一个小写字母构成的字符串。

小 S 可以做以下操作任意多次（可以不做）：选择词典中的任意一个单词，交换其中任意两个字符。

对于每个 $1 \leq i \leq n$ ，小 S 想知道，是否可以通过以上操作得到新的 $n$ 个单词 $w_{1}^{'}, w_{2}^{'}, \dots, w_{n}^{'}$ ，使得对于每个 $j \neq i$ ， $w_{i}^{'}$ 的字典序比 $w_{j}^{'}$ 都要小。对于 $n = 1$ 的情况，我们约定：上述性质是自然成立的。

对于两个同样长度的字符串 $s = s_{1} s_{2} \dots s_{L}$ 和 $t = t_{1} t_{2} \dots 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 \leq i \leq n$ ，如果题目描述中的性质成立，则 $a_{i} =$ 1，否则 $a_{i} =$ 0。

样例一

input

4 7
abandon
bananaa
baannaa
notnotn

output

提示

【样例解释 #1】

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

【样例解释 #2】

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

【样例解释 #3】

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

【样例解释 #4】

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

【数据范围】

对于所有测试数据，保证： $1 \leq n \leq 3000$ ， $1 \leq m \leq 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$

时间限制： $1s$

空间限制： $512MB$

Universal Online Judge

UOJ

#834. 【NOIP2023】词典

输入格式

输出格式

样例一

input

output

提示