题解：CF2145C Monocarp's String

考虑赋权，把所有的 a 设成

1

，把所有的 b 设成

-1

，题意就转化成需要删除一段区间

[l,r]

，使得

[1,l-1]

的前缀和与

[r+1,n]

的后缀和之和为

0

。

考虑把每一个点的后缀和算出来，然后开

n

个桶，

id_i

表示后缀和为

i

的所有下标。这个可以 vector 或者 set 之类的维护。

然后从前往后枚举

l

，顺便计算前缀和

pre

，然后再对应的桶

id_{-pre}

查询大于等于

l

的最小值就是确定这个左端点的最优的

[l,r]

。

然后把所有的

l

，算出最优的

r

，计算

r-l-1

（注意这个时候

l

和

r

是不能删除的）的最小值就是答案。

通过代码

CPP

#include<bits/stdc++.h>
#define ll long long
using namespace std;
constexpr ll maxn=2e5+5;
ll T,n,arr[maxn];
char ch[maxn];
set<ll> id[maxn<<2]; 
void solve(){
	cin>>n>>(ch+1);
	for(int i=1;i<=n;i++){
		if(ch[i]=='a')arr[i]=1;
		if(ch[i]=='b')arr[i]=-1;
	}	
	for(int i=-n;i<=n;i++){
		id[i+maxn].clear();
	}
	ll suf=0,ans=n,pre=0;
	id[0+maxn].insert(n+1);
	for(int i=n;i>=1;i--){
		suf+=arr[i];
		id[suf+maxn].insert(i);
	}
	if(suf==0){
		cout<<0<<"\n";
		return;
	}
	for(int i=0;i<=n;i++){
		pre+=arr[i];
		auto nxt=id[-pre+maxn].upper_bound(i);
		if(nxt==id[-pre+maxn].end())continue;
		ll pp=*nxt;
		ans=min(ans,pp-i-1);
	}
	if(ans==n){
		cout<<-1<<"\n";
		return;
	}
	cout<<ans<<"\n";
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	return 0;
}

题解：CF2145C Monocarp's String

文章操作

相关推荐

评论

题解：CF2145C Monocarp's String