【AtCoder Regular Contest 081 E】Don't Be a Subsequence | Mrsrz's blog

贪心。

题目大意：

给定一个字符串，你需要输出不是这个字符串的子序列的最短串。如果有长度相同的，输出字典序最小的。

题解：

我们首先求出最短串的长度。

如果长度为 $k$，那么前 $k-1$ 个位置无论选什么都存在。说明前面至少有 $k-1$ 个包含 a..z 所有字符的不相交的段。

我们从左往右扫，看看这样的段最多有多少个即可。具体做法是记录当前字符出现的集合，如果所有字符都出现了，则段数加一并清空集合。

然后考虑确定这个字符串。

我们预处理出每个位置后面的 a..z 分别最早出现的位置，和每个后缀的上述连续段长度。

然后按顺序枚举每一位字符，如果这个字符在后面最早出现的位置的后缀是满的，则不可选。如果不满，则可以选。

这样贪心即可求出字典序最小的字符串。

时间复杂度 $O(n)$。

Code：

#include<cstdio>
#include<cstring>
const int N=2e5+7;
char s[N];
int t,l=1,n,nxt[N][26],qwq[26],qaq[N];
int main(){
    scanf("%s",s+1);
    n=strlen(s+1);
    for(int i=1;i<=n;++i)if((t|=1<<(s[i]-97))==67108863)++l,t=0;
    for(int i=0;i<26;++i)qwq[i]=n+1;
    t=0;
    for(int i=n;~i;--i){
        memcpy(nxt[i],qwq,sizeof qwq);
        qwq[s[i]-97]=i;
        qaq[i]=qaq[i+1];
        if((t|=1<<(s[i]-97))==67108863)t=0,++qaq[i];
    }
    int nw=0;
    for(int i=1;i<l;++i){
        for(int c=0;c<26;++c){
            int to=nxt[nw][c];
            if(to<=n&&qaq[to+1]<l-i){
                putchar(c+97);
                nw=to;
                break;
            }
        }
    }
    t=0;
    for(int i=nw+1;i<=n;++i)t|=1<<(s[i]-97);
    for(int i=0;i<26;++i)if(t>>i&1^1)return putchar(i+97),0;
    return 0;
}