CodeForces-873B Balanced Substring 题解

一开始我以为这是一条简单的模拟题,然后我是这样写的:

#include<bits\stdc++.h>

int seq[100002]={0},n;
char seq_temp[100002];
using namespace std;

int search_max(int a,int b,int c0,int c1)
{
	if(c0==c1)return c0+c1;
	else if(!c0 || !c1) return 0;
	else return max(seq[a] ? search_max(a+1,b,c0,c1-1) : search_max(a+1,b,c0-1,c1),seq[b] ? search_max(a,b-1,c0,c1-1) : search_max(a,b-1,c0-1,c1));
	//前面删除一个与后面删除一个相比较
	//seq[a]为0,search(a+1,b,c0-1,c1)
	//seq[a]为1,search(a+1,b,c0,c1-1)
	//seq[b]为0,search(a,b-1,c0-1,c1)
	//seq[b]为1,search(a,b-1,c0,c1-1)
}

int main()
{
	cin >> n ;
	int c1=0,c0=0;
	scanf("%s",seq_temp+1);
	for(int i=1;i<=n;i++)
	{
		if(seq_temp[i]=='1')
		{
			seq[i]=1;
			c1++;
		}
		else
		{
			seq[i]=0;
			c0++;
		}
	}
	cout << search_max(1,n,c0,c1) << endl;
	return 0;
} 

当然,最后结果肯定是我炸了,在第20个测试点(似乎是最后一个),我的程序TLE了。
然后我又分析了一遍,想到:将0变为-1,则某段序列和为0则可以,那么可以通过将末尾前面的和减去起始前面的和得到。于是我修改代码为此。

#include<bits\stdc++.h>

int seq[2][100002],seq_appear[2][200002],n;
char seq_temp[100002];
using namespace std;

int main()
{
	cin >> n ;
	int c1=0,c0=0;
	scanf("%s",seq_temp+1);
	for(int i=1;i<=n;i++)
	{
		if(seq_temp[i]=='1')
		{
			seq[0][i]=1;
			c1++;
		}
		else seq[0][i]=-1;
	}
	int count_seq=0,count_seq_max=0,count_seq_min=200000;
	for(int i=0;i<=200001;i++)
	{
		seq_appear[0][i]=200002;
		seq_appear[1][i]=0;
	}
	for(int i=1;i<=n+1;i++)
	{
		seq[1][i]=count_seq;
		seq_appear[0][count_seq+100000]=min(seq_appear[0][count_seq+100000],i);//值为count_seq的起始坐标 
		seq_appear[1][count_seq+100000]=max(seq_appear[1][count_seq+100000],i);//值为count_seq的结束坐标 
		count_seq_max=max(count_seq_max,count_seq+100000);
		count_seq_min=min(count_seq_min,count_seq+100000);
		count_seq+=seq[0][i];

	}
	int ans=0; 
	for(int i=count_seq_min;i<=count_seq_max;i++)
	{
		ans=max(ans,seq_appear[1][i]-seq_appear[0][i]);
	}
	cout << ans << endl;
	return 0;
} 

留下你的评论呗...

电子邮件地址不会被公开。 必填项已用*标注