{"problem":{"name":"[NOIP2023] 词典","description":{"content":"小 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","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P2"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9868"},"statements":[{"statement_type":"Markdown","content":"小 S 的词典里有 $n$ 个两两不同的、长度均为 $m$ 的单词 $w_1,w_2,\\cdots,w_n$。每个单词都是一个小写字母构成的字符串。\n\n小 S 可以做以下操作任意多次（可以不做）：选择词典中的任意一个单词，交换其中任意两个字符。\n\n对于每个 $1 \\le i \\le n$，小 S 想知道，是否可以通过以上操作得到新的 $n$ 个单词 $w'_1,w'_2,\\cdots , w'_n$，使得对于每个 $j \\neq i$，$w'_i$ 的字典序比 $w'_j$ 都要小。**对于 $n=1$ 的情况，我们约定：上述性质是自然成立的。**\n\n对于两个同样长度的字符串 $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\n## Input\n\n输入的第一行包含两个正整数 $n$ 和 $m$，分别表示单词个数和单词长度。\n\n接下来 $n$ 行，每行包含一个长度为 $m$ 的小写字母字符串 $w_i$， 表示一个单词。\n\n## Output\n\n输出一行，其中包含一个长度为 $n$ 的 `01` 字符串 $a$；对于 $1 \\le i \\le n$，如果题目描述中的性质成立，则 $a_i =$ `1`，否则 $a_i =$ `0`。\n\n[samples]\n\n## Note\n\n**【样例解释 #1】**\n\n- 不做任何操作，第一个单词字典序最小，因此输出第一个字符为 `1`；\n- 交换 `bananaa` 的前两个字符以及 `abandon` 的第三个和第六个字符，得到 `abondan`, `abnanaa`, `baannaa`, `notnotn`，此时第二个单词字典序最小，因此输出第二个字符为 `1`；\n- 交换 `baannaa` 的第一个和最后一个字符得到 `aaannab`，其余字符串不变，此时第三个单词字典序最小，因此输出第三个字符为 `1`；\n- 无论如何操作，第四个单词不会小于第二个单词，因此输出第四个字符为 `0`。\n\n**【样例解释 #2】**\n\n该组样例满足测试点 $4$ 的限制。\n\n**【样例解释 #3】**\n\n该组样例满足测试点 $7$ 的限制。\n\n**【样例解释 #4】**\n\n该组样例满足测试点 $10$ 的限制。\n\n**【数据范围】**\n\n对于所有测试数据，保证：$1 \\le n \\le 3000$，$1 \\le m \\le 3000$，$w_i$ 为长度为 $m$ 的小写字母字符串且两两不同。\n\n| 测试点编号 | $n\\leq$ | $m\\leq$ |\n| :----------: | :----------: | :----------: |\n| $1$ | $1$ | $1$ |\n| $2\\sim 4$ | $26$ | $1$ |\n| $5\\sim 7$ | $15$ | $2$ |\n| $8$ | $300$ | $300$ |\n| $9$ | $10^3$ | $10^3$ |\n| $10$ | $3000$ | $3000$ |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9868","tags":["贪心","2023","NOIP 提高组","O2优化"],"sample_group":[["4 7\nabandon\nbananaa\nbaannaa\nnotnotn\n","1110"]],"created_at":"2026-03-03 11:09:25"}}