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;
}