NOIP2023-JZTXT

T1：词典

题意：

给定 \(n\) 个长度为 \(m\) 的字符串 \(w_1, w_2, \cdots, w_n\) 。
对于每个 \(i = 1, 2, \cdots, n\) 询问是否存在 \(w_1', w_2', \cdots, w_n'\) 使得对于每个 \(j = 1, 2, \cdots, n\)，\(w_j'\) 都可以由 \(w_j\) 交换字符得到，且对于 \(j \neq i\) 都有 \(w_i'\) 的字典序小于 \(w_j'\) 。

数据范围：

\( 1 \leqslant n \leqslant 3000 \), \( 1 \leqslant m \leqslant 3000 \), 所有字符串均由小写字母构成

算法分析

做法1：

对于每个 \(i\)，如果存在方案的话必然可以让 \(w_i'\) 字典序最小，而其他的 \(j \neq i\) 的 \(w_j'\) 字典序最大。也就是让 \(w_i\) 的字符从小到大排序得到 \(w_i'\)，让 \(w_j\) 的字符从大到小排序得到 \(w_j'\) 。

直接模拟这个过程的时间复杂度为 \(O(n^2m)\)，期望得分 \(80\) 分。
但实际上可以拿 \(100\) 分。

代码实现

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;

int main() {
    freopen("dict.in", "r", stdin);
    freopen("dict.out", "w", stdout);
    
    int n, m;
    cin >> n >> m;
    
    vector<string> w(n);
    rep(i, n) cin >> w[i];
    
    vector<string> mn(n);
    rep(i, n) {
        mn[i] = w[i];
        sort(mn[i].begin(), mn[i].end());
    }
    vector<string> mx(n);
    rep(i, n) {
        mx[i] = w[i];
        sort(mx[i].rbegin(), mx[i].rend());
    }
    
    string ans;
    rep(i, n) {
        bool ok = true;
        rep(j, n) if (j != i) {
            if (mn[i] > mx[j]) {
                ok = false;
                break;
            }
        }
        ans += ok ? '1' : '0';
    }
    
    cout << ans << '\n';
    
    return 0;
}

做法2：

实际上我们发现没有必要模拟上述过程，因为得到的 \(w_i'\) 以及 \(w_j'\) 一定是一段一段的，最多 \(\sigma = 26\) 段，使用桶存下每个字符的出现次数，之后一段一段比较即可在 \(O(nm+\sigma n^2)\) 的复杂度内解决。期望得到 \(80 \sim 100\) 分。

做法3：

不妨再深入一步，设 \(f_i\) 表示 \(w_i\) 中出现的最小字母， \(g_i\) 表示 \(w_i\) 中出现的最大字母。
如果 \(f_i < g_i\)，那么显然 \(w_i'\) 的字典序小于 \(w_j'\)，只需要将 \(f_i\) 作为 \(w_i'\) 的第一个字母，\(g_j\) 作为 \(w_j'\) 的第一个字母即可。
如果 \(f_i > g_j\)，那么显然 \(w_i'\) 的字典序大于 \(w_j'\)。
剩下最后一种情况 \(f_i = g_j\)，想要 \(w_i'\) 的字典序最小，需要将 \(f_i\) 放在最前面，此时越往后 \(w_i'\) 的字母越大。想要 \(w_j'\) 的字典序最大，需要将 \(g_j\) 放在最前面，此时越往后 \(w_j'\) 的字母越小。因此此时必然有 \(w_i'\) 的字典序大于 \(w_j'\)。
综上，如果 \(i\) 可能，当且仅当 \(f_i < \min\limits_{j \neq i} g_j\)。因此可以 \(O(n)\) 完成这个过程，总的时间复杂度为 \(O(nm+n^2)\)。
期望得分：100分。

代码实现

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;

int main() {
    freopen("dict.in", "r", stdin);
    freopen("dict.out", "w", stdout);
    
    int n, m;
    cin >> n >> m;
    
    vector<int> f(n, 26), g(n, -1);
    rep(i, n) {
        string w;
        cin >> w;
        rep(j, m) {
            f[i] = min(f[i], w[j]-'a');
            g[i] = max(g[i], w[j]-'a');
        }
    }
    
    string ans;
    rep(i, n) {
        bool ok = true;
        rep(j, n) if (j != i) {
            if (f[i] >= g[j]) {
                ok = false;
                break;
            }
        }
        ans += ok ? '1' : '0';
    }
    
    cout << ans << '\n';
    
    return 0;
}