NOIP2023 T1 题解（C++）

核心思路
这道题的关键突破口：可以任意交换单词的字符，说明每个单词能重排成字符的任意排列。
要让单词 i 成为全局最小：
把 i 重排成字典序最小的形式（升序排列）；
把其他所有单词重排成字典序最大的形式（降序排列）；
如果此时 i 的最小形式 < 所有其他单词的最大形式，那么答案为 1，否则为 0。
这个判断条件是充要条件，能覆盖所有情况。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 3005;
// 存储每个单词 最小排列(升序)、最大排列(降序)
string min_s[MAXN], max_s[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);  // 加速输入输出（应对大数据）
    
    int n, m;
    cin >> n >> m;
    
    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        // 最小排列：升序排序
        min_s[i] = s;
        sort(min_s[i].begin(), min_s[i].end());
        // 最大排列：降序排序
        max_s[i] = s;
        sort(max_s[i].rbegin(), max_s[i].rend());
    }
    
    string ans;
    for (int i = 0; i < n; ++i) {
        bool ok = true;
        // 检查：当前单词最小形式 < 所有其他单词的最大形式
        for (int j = 0; j < n; ++j) {
            if (i == j) continue;
            if (min_s[i] >= max_s[j]) {
                ok = false;
                break;
            }
        }
        ans += (ok ? '1' : '0');
    }
    
    cout << ans << endl;
    return 0;
}

代码解释

输入优化
ios::sync_with_stdio(false); cin.tie(nullptr); 用于加速输入输出，应对 n,m=3000 的大数据量。

预处理最小 / 最大排列

最小排列：对字符串升序排序（如 bananaa → aaabnn）；
最大排列：对字符串降序排序（如 bananaa → nnnaaab）。

核心判断
对每个单词 i，遍历所有其他单词 j：

如果 min_s[i] >= max_s[j]，说明无论怎么排列，i 都不可能比 j 小，答案为 0；
否则答案为 1。

输出结果
拼接所有判断结果，输出 01 字符串。

复杂度分析
预处理：(O(n \cdot m \log m))（排序字符串）；
判断：(O(n^2 \cdot m))（字符串比较）；
总复杂度：(O(nm\log m + n^2m))，完全能通过 (n,m=3000) 的数据。
样例测试输入：plaintext4 7
abandon
bananaa
baannaa
notnotn
预处理后：
第 4 个单词的最小排列 >= 第 2 个单词的最大排列 → 输出 1110，与样例一致。