P9868 题解

FurippuWRY · 2023-11-24 00:23:35 · 题解

题意：给定 n 个长度为 m 的字符串 w_1,w_2,...,w_n，对于每个 i\in[1,n]，求字符串 w_i 是否可以通过数次排列使其字典序在 n 个字符串中最小。

思路：对于每个 i\in[1,n]，记录 w_i 中字典序最小和最大的字符 min_i 和 max_i，然后遍历每个字符串，如果遍历到一个字符串 w_j，min_i \ge max_j，则字符串 w_i 无法成为字典序最小的字符串，此时输出 0。否则，遍历一圈下来，\forall max_j > min_i，此时就输出 1。复杂度 O(n\times\max(n,m))。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll N = 3009;

ll n, m;
string w[N];
char maxn[N], minn[N];

int main() {
    cin >> n >> m;
    memset(minn, 'z', sizeof minn);
    for (ll i = 1; i <= n; ++i) {
        cin >> w[i];
        for (ll j = 0; j < m; ++j) {
            minn[i] = min(minn[i], w[i][j]);
            maxn[i] = max(maxn[i], w[i][j]);
        }
    }
    for (ll i = 1; i <= n; ++i) {
        bool flag = 1;
        for (ll j = 1; j <= n; ++j) {
            if (i == j) continue;
            if (minn[i] >= maxn[j]) {
                flag = 0;
            }
        }
        cout << flag;
    }   
    return 0;
}