题解 CF938F Erasing Substrings

题解 CF938F Erasing Substrings

题面

luogu

CF

解析

考虑最后剩下的 $n-2_k+1$ 个字符的每一位应该选什么.

显然可以用贪心,选字典序最小的字母.

但问题是删除子串会对选择有影响.

考虑到删除的顺序并不影响,因此可以状压删除的状态 $S$,即 $S$ 的第 $i$ 位二进制位为 $1/0$ 表示是否删掉了 $2^{i}$ 这一段.并且,$S$ 就是被删除的字符数.

设 $f_{i,S}$ 表示选第 $i$ 个剩下的字符,被选择的字符前面删除的情况为 $S$ 是否可行.

那么由于前面还有 $i-1$ 个被选择的字符,因此这个被选的字符是字符串中的第 $S+i$ 个.

那么我们找出字典序最小的可行的字符即可,然后更新 $f_{i+1}$.

设这次选择的字符是 ‘x’,那么 $f_{i+1,S}=1$ 的条件是 $f_{i,S}=1$ 且 $s_{S+i}=x$,$s$ 为字符串.因为这次必须选 ‘x’.

但是在这次选了以后可以删掉后面的一些无关紧要的子串.

因此在寻找字符之前,如果 $f_{i,S}=1$,那么往后面删掉长度为 $2^j$ 的字符也是可行的,即 $f_{i,S’}=1$,$S’=S|2^j$,$|$ 表示按位或.

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define ll long long
using namespace std;

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

const int N=5305;
int n,f[N],S;
char s[N];

signed main(){
scanf("%s",s+1);n=strlen(s+1);S=log2(n);
for(int i=0;i<=n;i++) f[i]=1;
for(int i=1,mx=n-(1<<S)+1;i<=mx;i++){
char ch='z';
for(int j=0;j<(1<<S);j++)
if(f[j]) for(int k=0;k<S;k++) f[j|(1<<k)]=1;
for(int j=0;j<(1<<S);j++)
if(f[j]) ch=min(ch,s[j+i]);
for(int j=0;j<(1<<S);j++) f[j]&=(s[j+i]==ch);
putchar(ch);
}
puts("");
return 0;
}
感谢您又打赏