Crazy Binary String 思维

题意

给出01串，给出定义：一个串里面0和1的个数相同，求满足定义的最长子序列和子串

分析

子序列好求，就是0 1个数，字串需要思考一下。实在没有思路可以看看数组范围(n<=1e5)，很像nlogn或者n的算法，这个时候就要考虑一下二分和前缀和优化，二分感觉⑧太行，这个时候研究一下前缀和的性质，发现0 为-1，1为1的时候，前缀和相同的两个位置中间恰好可以构成一个满足定义的串，所以这题就解决了。没有思路的时候多发散一下思维，从多角度思考一下问题。

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e5+4;

char s[maxn];

map<int,int>mp;

int main(){

	int n;

	scanf("%d",&n);

	scanf("%s",s+1);

	int tmp=0;

	int ans=0;

	int ling =0,yi=0;

	mp[0]=0;

	for(int i=1;i<=n;i++){

		if(s[i]=='1')tmp++,yi++;

		else tmp--,ling++;

		if(!mp.count(tmp)){

			mp[tmp]=i;

		}

		else

		ans=max(ans,i-mp[tmp]);

	}

	printf("%d %d\n",ans,2*min(ling,yi));

	return 0;

}

巴特西

2019牛客多校第三场B Crazy Binary String 思维

Crazy Binary String 思维

题意

分析

最新文章

热门文章