#NOIP2023A. 词典(dict)
词典(dict)
题目描述
小 S 的词典里有 个两两不同的、长度均为 的单词 。每个单词都是一个小写字母构成的字符串。
小 S 可以做以下操作任意多次(可以不做):选择词典中的任意一个单词,交换其中任意两个字符。
对于每个 ,小 S 想知道,是否可以通过以上操作得到新的 个单词 ,使得对于每个 , 的字典序比 都要小。对于 的情况,我们约定:上述性质是自然成立的。
对于两个同样长度的字符串 和 ,称字符串 字典序小于字符串 ,当且仅当以下条件成立:存在位置 ,在第 个字符之前 和 都相同,而且 ,即小写字母 在英文字母顺序中先于 。
输入格式
输入的第一行包含两个正整数 和 ,分别表示单词个数和单词长度。
接下来 行,每行包含一个长度为 的小写字母字符串 , 表示一个单词。
输出格式
输出一行,其中包含一个长度为 的 01
字符串 ;对于 ,如果题目描述中的性质成立,则 1
,否则 0
。
样例 #1
样例输入 #1
4 7
abandon
bananaa
baannaa
notnotn
样例输出 #1
1110
提示
【样例解释 #1】
- 不做任何操作,第一个单词字典序最小,因此输出第一个字符为
1
; - 交换
bananaa
的前两个字符以及abandon
的第三个和第六个字符,得到abondan
,abnanaa
,baannaa
,notnotn
,此时第二个单词字典序最小,因此输出第二个字符为1
; - 交换
baannaa
的第一个和最后一个字符得到aaannab
,其余字符串不变,此时第三个单词字典序最小,因此输出第三个字符为1
; - 无论如何操作,第四个单词不会小于第二个单词,因此输出第四个字符为
0
。
【样例解释 #2】
该组样例满足测试点 的限制。
【样例解释 #3】
该组样例满足测试点 的限制。
【样例解释 #4】
该组样例满足测试点 的限制。
【数据范围】
对于所有测试数据,保证:,, 为长度为 的小写字母字符串且两两不同。
测试点编号 | ||
---|---|---|