Abstract
传送门
本题定义平衡串为 0 和 1 数量相等的字符串,要求我们找出给定 01 串中含有的最大平衡串。
Idea
如果把 1 视为 +1 ,0视为 -1,那么一个 01 串是平衡串当且仅当其和值为 0 ,那么问题就转变为寻找给定 01 串中和值为 0 的最长子段。
首先做一个前缀和,a[i] 表示前 i 项的和值,那么对于区间 [l,r] ,只要 a[r] - a[l-1] == 0,它就是一个平衡串,暴力枚举 l 和 r ,时间复杂度是 O(n^2),显然超时。实际上,对于每一个 a[i] ,我们只希望找到一个 a[j] ,使得 a[i] == a[j] ,那么我们可以考虑存储 a[i] 出现的最大序号和最小序号,然后取其差值即可得到答案,细节见代码。
Code
#include <bits/stdc++.h>
using namespace std;
// buyy
int a[300000];
int mint[300000];
int maxt[300000];
int main()
{
int n;
memset(mint, 0x3f3f3f3f, sizeof mint);
memset(maxt, -0x3f3f3f3f, sizeof maxt);
scanf("%d\n", &n);
int sum = 0;
int ans = 0;
for (int i = 1; i < n + 1; i++)
{
char c = getchar();
if (c == '1')
{
sum++;
}
else
{
sum--;
}
if (sum > 0)
{
mint[sum] = min(mint[sum], i);
maxt[sum] = max(maxt[sum], i);
}
else if (sum == 0)
{
ans = i;
}
else
{
int p = -sum + n;
mint[p] = min(mint[p], i);
maxt[p] = max(maxt[p], i);
}
a[i] = sum;
}
for (int i = 1; i <= n; i++)
{
if (a[i] == 0)
{
continue;
}
if (a[i] < 0)
{
a[i] = -a[i] + n;
}
ans = max(ans, maxt[a[i]] - mint[a[i]]);
}
cout << ans;
return 0;
}
标签:01,CF873B,int,sum,maxt,Substring,Balanced,mint,300000
From: https://www.cnblogs.com/carboxylBase/p/18335703