#2922. [NOIP2023] 词典

[NOIP2023] 词典

说明

本题需要使用文件重定向,输入文件名dict.in,输出文件名dict.out

题目描述

小 S 的词典里有 nn 个两两不同的、长度均为 mm 的单词 w1,w2,,wnw_1,w_2,\cdots,w_n。每个单词都是一个小写字母构成的字符串。

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

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

对于两个同样长度的字符串 s=s1s2sLs = s_1s_2\cdots s_Lt=t1t2tLt = t_1t_2 \cdots t_L,称字符串 ss 字典序小于字符串 tt,当且仅当以下条件成立:存在位置 ii,在第 ii 个字符之前 sstt 都相同,而且 si<tis_i < t_i,即小写字母 sis_i 在英文字母顺序中先于 tit_i

输入格式

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

接下来 nn 行,每行包含一个长度为 mm 的小写字母字符串 wiw_i, 表示一个单词。

输出格式

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

样例

4 7
abandon
bananaa
baannaa
notnotn
1110

提示

【样例解释 #1】

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

【样例解释 #2】

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

【样例解释 #3】

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

【样例解释 #4】

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

数据范围

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

测试点编号 nn\leq mm\leq
11 11
242\sim 4 2626
575\sim 7 1515 22
88 300300
99 10310^3
1010 30003000