120563C

https://ac.nowcoder.com/acm/contest/120563/C

最终情况只有可能是或，所以分两种情况抽出不正确的位置，记为，记为，求最大子段和即可。

子段和：

注意是求最大子段和，而不是连续或的最大长度，因为中间的消去后会消失。比如抽出的是：，最长是，但把消去后拼接在了一起，不能一起消去。时间复杂度。

#include<bits/stdc++.h>
using namespace std;
int a[1000100],b[1000100];
int read(){
	char ch=getchar();int x=0,f=1;
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch<='9'&&ch>='0'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
int f(int n){
	int res=0,ans=0,anss=0;
	for(int i=1;i<=n;i++){
		if(b[i]) res++;
		else res--;
		if(res<0) res=0;
		ans=max(ans,res);
	}
	res=0;
	for(int i=1;i<=n;i++){
		if(b[i]) res++;
		else res--;
		if(res>0) res=0;
		anss=min(anss,res);
	}
	return max(ans,abs(anss));
}
void work(){
	int n=read();
	int tot=0,ans=0;
	for(int i=1;i<=n;i++){
		scanf("%1d",&a[i]);
	}
	for(int i=1;i<=n;i++){
		if((i&1)&&(a[i]&1)) b[++tot]=a[i];
		if((!(i&1))&&(!(a[i]&1))) b[++tot]=a[i];
	}
	ans=f(tot);
	tot=0;
	for(int i=1;i<=n;i++){
		if((i&1)&&(!(a[i]&1))) b[++tot]=a[i];
		if((!(i&1))&&((a[i]&1))) b[++tot]=a[i];
	}
	ans=min(ans,f(tot));
	printf("%d\n",ans);
}
int main(){
	int t=read();
	while(t--){
		work();
	}
	return 0;
}