「NOIP2023」词典

#题面

#题目描述

小 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$，使得对于每个 $j \neq i$，$w'_i$ 的字典序比 $w'_j$ 都要小。对于 $n = 1$ 的情况，我们约定：上述性质是自然成立的。

对于两个同样长度的字符串 $s = s_1 s_2\cdots s_L$ 和 $t = t_1 t_2 \cdots 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 \le i \le n$，如果题目描述中的性质成立，则 $a_i =$ 1，否则 $a_i =$ 0。

#输入输出样例

样例输入 #1

4 7
abandon
bananaa
baannaa
notnotn

样例输出 #1

1110

样例解释 #1

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

样例 #2

见选手目录下的 dict/dict2.in 和 dict/dict2.ans。

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

样例 #3

见选手目录下的 dict/dict3.in 和 dict/dict3.ans。

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

样例 #4

见选手目录下的 dict/dict4.in 和 dict/dict4.ans。

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

#数据范围与约定

对于所有测试数据，保证：$1 \le n \le 3000$，$1 \le m \le 3000$，$w_i$ 为长度为 $m$ 的小写字母字符串且两两不同。

#思路

先让每个字符串达到其字典序最大的状态，然后再判断当该字符串处于字典序最小状态时是否是所有字符串当中最小的即可。

#代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#include <iostream>
#include <algorithm>
#include <functional>
#include <string>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 3005;

int n, m;
std::string w[N];

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        std::sort(w[i].begin(), w[i].end(), std::greater<>());
    }

    for (int i = 1; i <= n; i++) {
        std::sort(w[i].begin(), w[i].end());
        cout << (*std::min_element(w + 1, w + 1 + n) == w[i] ? 1 : 0);
        std::sort(w[i].begin(), w[i].end(), std::greater<>());
    }

    cout << endl;

    return 0;
}