P9868题解

operator_ · 2023-11-20 09:45:22 · 题解

P9868 [NOIP2023] 词典

题目传送门

题解

T1 词典(dict)

考察：贪心

首先任意多次操作本质就是随意排序，所以如果要使 w_i 最小，我们一定会使 w_i 从 a 到 z 排，其它都 z 到 a 排。然后考虑比较字典序的实质：

• 如果 w_i 中第一个（即最小的）字符都比 w_j 中第一个（即最大的）字符大，那么显然不可能满足性质。

• 如果相同，那么若存在，我们考虑第一个不同的位置，发现一定有 w_i>w_j，而若不存在，则等价于两串相同，也不符合

因此我们只需要记录每个串的最大最小字符即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read() {
    int s=0,m=0;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-')m=1;ch=getchar();}
    while( isdigit(ch)) s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    return m?-s:s;
}
int n,m,minn[3005],maxn[3005],fl;
char s[3005];
signed main() {
    cin>>n>>m;
    for(int i=1;i<=n;i++) {
        minn[i]=27;
        scanf("%s",s+1);
        for(int j=1;j<=m;j++) 
            minn[i]=min(minn[i],s[j]-'a'+1ll),maxn[i]=max(maxn[i],s[j]-'a'+1ll);
    }
    for(int i=1;i<=n;i++) {
        fl=1;
        for(int j=1;j<=n;j++)
            fl&=(i==j||minn[i]<maxn[j]);
        printf("%lld",fl);
    }
    return 0;
}

时间复杂度 O(nm+n^2)，理论可以优化到 O(nm+n)，但完全没必要。