[牛客暑期多校第三场][思维]B-Crazy Binary String

发布于 2019-07-29  144 次阅读


https://ac.nowcoder.com/acm/contest/883/B

题意:给定一个只含有01的字符串 求01相等的最长子串和最长子序列
子序列明显是01中出现较少的数字
子串的求法参考代码吧
两个前缀和相等说明 两个前缀和之间的01个数相等 因为既然前缀和相等 那么其中的01必定相等 而前缀和相等的这一段序列中 只有 01个数相等才能保证前缀和相等 了不起的做法!

#include<algorithm>
#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<ctime>
#include<map>
#include<stack>
#include<set>
#include<cstring>
#include<sstream>
#include<queue>
using namespace std;
typedef long long ll;
const int maxn = 1e5+5;
map<int, int> mp;

int a[maxn];
int n;
char s[maxn];

int main() {
	cin >> n;
	cin >> s + 1;
	for (int i = 1; i <= n; i++) {
		a[i] = a[i - 1] + ((s[i] == '1') ? 1 : -1);
	}
	int ans = 0;
	mp[0] = 0;
	for (int i = 1; i <= n; i++) {
		if (mp.find(a[i]) != mp.end()) {//寻找这个前缀和第一次出现的位置
			ans = max(ans, i - mp[a[i]]);//两次位置之差 即这一段距离
		}
		else {//如果不存在 则存入
			mp[a[i]] = i;
		}
	}
	int zero = 0;
	int one = 0;
	for (int i = 1; i <= n; i++)
		if (s[i] == '0') zero++; else one++;
	printf("%d %d\n", ans, min(zero, one) * 2);
	return 0;
}

愿风指引你的道路,愿你的刀刃永远锋利。