学会 01 串
学会 01 串
51node 上的一道题目 01 串[1]
给定一个 01 串 S,求出它的一个尽可能长的子串 S[i..j]，满足存在一个位置 i<=x <j, S[i..x]中 0 比 1 多，而 S[x + 1..j]中 1 比 0 多。求满足条件的最长子串长度。 输入
一行包含一个只由 0 和 1 构成的字符串 S。S 的长度不超过 1000000。
输出
一行包含一个整数，表示满足要求的最长子串的长度。
输入样例
10
输出样例
0
时间限制 1s 空间 131,072.0 KB
为了方便操作我们可以把字符串先转成 int 数组的类型，同时把 0 记录-1 后边方便我们判断 0 和 1 谁比较多
int a[i]; //a[i]用来存储0变成-1 1变成1的值
string s;
cin>>s;
int len=s.length();
for (int i = 1; i <= len; i++)
{
if (s[i-1] == '0')
a[i] = -1;
else
a[i] = 1;
}观察一下这道题，想一下 x 点的下标可能是 中的任何一个位置 (读题可知不能是不能是 len-1 这个下标)
所以我们可以做一下预处理，然后对每个点进行枚举，看 x 取哪个点的时候字串的位置最大
我们先假设一个最终下标是 y 点 假设 s[i...x]为 s1,s[x+1....j]为 s2 先看一下 s1 情况有两种
- 0-y 之间 0 的个数比 1 的个数要多 这时候 s1 长度是
- 0-y 之间 1 的个数比 0 的个数要多或者相等(这两种情况可以归结为 0 的个数没有 1 的多) 这时候 s1 的长度不能直接得出我们需要进行一下处理
第二种情况下我们需要用贪心的思想取考虑
既然这个区间上 0 没有 1 多 那么我们只能选取这个区间上的一个子区间 选取的这个子区间想要长度最大化的时候 必定是 0 的个数比 1 的个数多 1 个
先假设一个串是 111110000110
黑线部分表示的是 s1 可以看出来这时候 0 的个数比 1 的正好多 1 个 这时候 s1 中的值累加是 -1
现在我们知道如何选择了 那么我们怎么能知道 s1 的起始位置在哪?
再看一下上面我们得出 s1 是第二种情况的时候 s1 中的和是-1 那么我们扫一遍数组记录前缀和是不是就能得出 y 点的 s1 在哪了？
int index[maxn];
int now; //记录前缀和
memset(index, -1, sizeof index);
for (int i = 1; i <= len; i++) {
now += a[i];
if (now < 0)
lef[i] = i; // 如果前缀和小于0的时候 s1的起始位置就是下表为0的地方 这时候s1的长度是i
else
{
if (index[now + 1] != -1)
{
lef[i] = i - index[now + 1];
//此时长度是i-index[now+1]
//为什么是 index[now+1] 而不是index[now+2]
//读者可以用111110000110比着试一下
}
else
{
index[now] = i;
lef[i] = 0;
//这种情况下s1不存在 拿上边那个例子来说 到下标为4的时候 now=4 此时怎么选取s1都选不出来
}
}
}以上就是 s1 的寻找过程 反过来寻找 s2 的长度也是同理 下面给出完整的代码
#include<iostream>
#include<string>
#include<string>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 1000005;
int a[maxn]; //存储string转化后的值
int index[maxn]; //辅助数组
int lef[maxn];//记录每个点左边选取的序列的最长长度
int rt[maxn];//右边同理
string s;
int main()
{
cin >> s;
int len = s.length();
for (int i = 1; i <= len; i++)
{
if (s[i-1] == '0')
a[i] = -1;
else
a[i] = 1;
}
int now = 0;
memset(index, -1, sizeof index);
// 注意下面转存到int数组的时候我是从下标1开始的
// 对于每一个点 寻找它的s1长度
for (int i = 1; i <= len; i++) {
now += a[i];
if (now < 0)
lef[i] = i;
else
{
if (index[now + 1] != -1)
{
lef[i] = i - index[now + 1];
}
else
{
index[now] = i;
lef[i] = 0;
}
}
}
//寻找s2长度
memset(index, -1, sizeof index);
now = 0;
for (int i = len; i >= 1; i--)
{
now += a[i];
if (now > 0)
{
rt[i] = len - i + 1;
}
else
{
if (index[-now + 1] != -1)
rt[i] = index[-now + 1] - i;
else
{
index[-now] = i;
rt[i] = 0;
}
}
}
//最后一步就是从左往右枚举x点了 看哪个点更合适
int ans = 0;
for (int i = 1; i < len; i++)
{
if(lef[i]>0&&rt[i+1]>0) //不能忘记判断
ans = max(ans, lef[i] + rt[i + 1]);
}
printf("%d", max(ans,0));
return 0;
}最后再留一个练习了 也是 01 串的运用[2] 上面讲的这道题我们是用前缀和的形式来寻找我们想要的信息的练习是使用异或记录状态的
参考资料
[1]
01串: https://www.51nod.com/Challenge/Problem.html#problemId=1391
[2]
也是01串的运用: https://nanti.jisuanke.com/t/43513