Codeforces

Luogu

分析

注意到删除的顺序不影响答案,从而可以得到一个暴力做法:设 $dp_{i,S}$ 表示前 $i$ 位用掉的操作集合为 $S$ 的最小串。这样子是 $\mathcal{O}(n^3\log n)$ 的。

考虑一个贪心。显然我们每次选的一定是能选的最小的字符。因此我们只需要求出每个连续删除长度是否合法。

假设当前在算答案的第 $i$ 位,考虑求出 $dp_S$ 表示当前用掉 $S$ 中操作是否合法,则当前这一位的答案为 $s_{i+S}$ 中最小的,其中 $dp_S=1$。在算出当前位的答案后,那些不能到达这个答案的长度全部不合法,将它们的 $dp$ 值设为 $0$ 即可。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=5000+10;

char s[N]; int dp[N];

int main() {
    scanf("%s",s+1); int n=strlen(s+1),k=log2(n);
    for (int S=0;S<1<<k;++S) dp[S]=1;
    for (int i=1;i<=n-(1<<k)+1;++i) {
        for (int S=0;S<1<<k;++S)
            if (dp[S])
                for (int j=0;j<k;++j) dp[S|(1<<j)]=1;
        char c='z';
        for (int S=0;S<1<<k;++S) if (dp[S]) c=min(c,s[i+S]);
        for (int S=0;S<1<<k;++S) if (s[i+S]!=c) dp[S]=0; 
        putchar(c);
    }
    return 0;
}
最后修改:2020 年 04 月 21 日 10 : 10 PM