A1283 【NOIP2023 T1】词典

#include <bits/stdc++.h>
using namespace std;

// NOIP2023 T1 词典（A1283）
//
// 任意交换字符 ⇒ 每个单词可以变成它的任意排列。
// 升序排列 s_i 是 w_i 的最小样子，降序排列 t_i 是最大样子；
// w_i 能当最小的 ⟺ s_i < t_j 对所有 j≠i 成立 ⟺ s_i < min_{j≠i} t_j。
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<string> s(n), t(n);
    for (int i = 0; i < n; i++) {
        string w;
        cin >> w;
        int cnt[26] = {0}; // 统计每个字母的个数
        for (char c : w) cnt[c - 'a']++;
        for (int c = 0; c < 26; c++) s[i].append(cnt[c], char('a' + c));  // 升序
        for (int c = 25; c >= 0; c--) t[i].append(cnt[c], char('a' + c)); // 降序
    }

    if (n == 1) { // 约定：只有一个单词时自然成立
        cout << "1\n";
        return 0;
    }

    // 找出所有 t 中字典序最小与次小的两个（线性扫描即可）
    int min1 = 0, min2 = -1;
    for (int i = 1; i < n; i++) {
        if (t[i] < t[min1]) {
            min2 = min1;
            min1 = i;
        } else if (min2 == -1 || t[i] < t[min2]) {
            min2 = i;
        }
    }

    string ans(n, '0');
    for (int i = 0; i < n; i++) {
        int lim = (i == min1 ? min2 : min1); // 排除自己之后最小的 t
        if (s[i] < t[lim]) ans[i] = '1';
    }

    cout << ans << "\n";
    return 0;
}