3923. T1-[NOIP2023] 词典(dict)
时间限制：1000 MS 内存限制：512 MB
题目描述
小 $ S $ 的词典里有 $ n $ 个两两不同的、长度均为 $ m $ 的单词 $ w_1,w_2,···,w_n $ 。 每个单词都是一个小写字母构成的字符串。 小 $ S $ 可以做以下操作任意多次（可以不做）：选择词典中的任意一个单词，交换其中任意两个字符。 对于每个 $ 1≤i≤n $ ，小 $ S $ 想知道，是否可以通过以上操作得到新的 $ n $ 个单词 $ w_1′,w_2′,···,w_n′ $ ，使得对于每个 $ j≠i $ ， $ w_i′ $ 的字典序比 $ w_j′ $ 都要小。 **对于 $ n=1 $ 的情况，我们约定：上述性质是自然成立的。** 对于两个同样长度的字符串 $ s=s_1s_2···s_L $ 和 $ t=t_1t_2···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≤i≤n $ ，如果题目描述中的性质成立，则 $ a_i $ =`1`，否则 $ a_i $ =`0`。 #### 数据范围 对于所有测试数据，保证： $ 1≤n≤3,000，1≤m≤3,000 $ ， $ w_i $ 为长度为 $ m $ 的小写字母字符串且两两不同。  #### 输入样例： ``` 4 7 abandon bananaa baannaa notnotn ``` #### 输出样例： ``` 1110 ``` #### 样例解释 不做任何操作，第一个单词字典序最小，因此输出第一个字符为 `1`； 交换 `bananaa` 的前两个字符以及 `abandon` 的第三个和第六个字符，得到 `abondan,abnanaa, baannaa, notnotn`，此时第二个单词字典序最小，因此输出第二个字符为 `1`； 交换 `baannaa` 的第一个和最后一个字符得到 `aaannab`，其余字符串不变，此时第三个单词字典序最小，因此输出第三个字符为 `1`； 无论如何操作，第四个单词不会小于第二个单词，因此输出第四个字符为 `0`。