P9868 题解

· · 题解

场外人员 VP 的时候写的。

首先最优的方法肯定是用字典序最小的 i 和字典序最大的 j 做对比。

所以考虑暴力对比，但是复杂度是 O(n^2m) 的。

因此考虑优化，我们令 f_{i,j,k} 为第 k 个字符串的第 i 位的字符是否不为第 j 个小写字母。

那么判断是只需要对于枚举每一位，然后再枚举比第 i 个字符串的第 j 位大的字符串取交集（这个可以用 bitset 优化）就可以了。

最后注意判断第 i 个字符串字符集大小为 1 的情况。

但是这样的复杂度是 O(\frac{n^2m\rvert\Sigma\lvert}{\omega}) 的，感觉无法通过。

考虑优化掉复杂度中 \rvert\Sigma\lvert 的部分。

我们可以使用后缀按位与来优化，只需对 j 求一次后缀按位与即可。

代码如下：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN 3001

int n, m;
string s;
string str[MAXN], str2[MAXN];
bitset<MAXN> vis;
bitset<MAXN> f[MAXN][27];

signed main(){
//  freopen("dict.in", "r", stdin);
//  freopen("dict.out", "w", stdout);

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for (int i(0); i<n; ++i){
        cin >> s;
        sort(s.begin(), s.end());
        str[i] = s;
        reverse(s.begin(), s.end());
        str2[i] = s;
    }
    for (int i(0); i<m; ++i){
        for (int j(0); j<27; ++j){
            for (int k(0); k<n; ++k) f[i][j].set(k);
        }
    }
    for (int i(0); i<n; ++i){
        for (int j(0); j<m; ++j) f[j][str2[i][j]-'a'].reset(i);
    }
    for (int i(0); i<m; ++i){
        for (int j(25); j>=0; --j) f[i][j] &= f[i][j+1];
    }

    for (int i(0); i<n; ++i){
        vis.set();
        for (int j(0); j<m; ++j) vis &= f[j][str[i][j]-'a'+1];
        cout << ((str[i] == str2[i] && vis.count() == 1) || vis.count() == 0);
    }

    return 0;
}