Codeforces Round #579 (Div. 3) D题

题目大意

给定你字符串ss 与字符串tt,求解最多能从ss中删去多少个元素使得ss中仍包含tt为子串(不要求连续,保证给定的ttss的子串)。

核心思路

D1的暴力十分好写,但码量似乎比D2还大些

O(n2)O(n^2) 枚举左右端点,暴力加点然后判断加完后的串还有没有tt这个子串。正宗的暴力写法。

完整代码

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
//submit on LG

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>

using namespace std;
#define REP(i,e,s) for(register int i=e; i<=s; i++)
#define DREP(i,e,s) for(register int i=e; i>=s; i--)
#define DE(...) fprintf(stderr,__VA_ARGS__);
#define DEBUG(a) DE("DEBUG: %d\n",a)
#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
#define ll long long

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

const ll INF=0x3f3f3f,MAXN=200+10;

char s[MAXN],t[MAXN],now[MAXN];
int lens,lent;

bool check(int l,int r) {
int cnt=0;
REP(i,1,l-1) now[++cnt]=s[i];
REP(i,r+1,lens) now[++cnt]=s[i];

int find=1;
//printf("cnt: %d\n",cnt);
REP(i,1,cnt) {
if(now[i]==t[find]) find++;
}
if(find==lent+1) return 1;
return 0;
}

int main() {
scanf("%s",s+1);
scanf("%s",t+1);

lens=strlen(s+1),lent=strlen(t+1);

int ans=0;

REP(i,1,lens) REP(j,i,lens) {
if(check(i,j)) {
ans=max(ans,j-i+1);
//printf("%d %d\n",i,j);
}
}
printf("%d\n",ans);
return 0;
}

D2的数据范围很容易联想到二分答案,但是有了NOIp2018年积木大赛的教训后,看到10510^5也要提防一下是不是线性的做法。

首先线性地扫一遍对于tt中的每一个一个位置ii,求出它之前在ss中最早能够被满足的位置,再从右边扫一遍。那么得到这个位置之后我们就可以知道任意一段区间是否能够满足。最后再线性地统计一下答案即可。

评论