题目链接
题意:给定一个01串S,求出它的一个尽可能长的子串S[i..j],满足存在一个位置i<=x <=j, S[i..x]中0比1多,而S[x + 1..j]中1比0多。求满足条件的最长子串长度。
初步分析:假设子串S[i..j]是满足条件的一个最长子串,且i和j均不是边界(0<i && j<n-1),则S[i-1]一定是1,否则S[i-1, j]也满足条件且比S[i, j]长,矛盾。同理可推出S[j+1]是0。用类似的逻辑进一步可推出存在一个位置i<=x <=j, S[i..x]中0比1恰好多1个,而S[x + 1..j]中1比0恰好多1个。把原数组中所有的0用-1代替,子串01个数的比较就可以转换为子串和的正负。
思路:先处理i和j不是边界的情况,根据上面的初步分析,可以枚举x,然后分别考虑到x结尾的和为-1的最长子串的长度,以x+1开头的和为1的最长子串的长度。这两个子问题都可以通过hash来解决(类似于求最长01子串,使得0和1个数相等)。i,j是边界的情况特殊处理就好。
代码虽然写得挫,还是忍不住贴一个:

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + ;
char s[N];
int a[N];
int pre[N], suf[N];
int start[N], end[N];
int f[*N];
int main()
{
freopen("in.txt", "r", stdin);
while(==scanf("%s", s+)){
int n = strlen(s+);
for(int i=; i<=n; i++){
a[i] = s[i]=='' ? : -;
}
memset(f, 0x3f, sizeof(f));
memset(end, , sizeof(end));
pre[] = ;
for(int i=; i<=n; i++){
pre[i] = pre[i-] + a[i];
int tmp = pre[i] + N;
end[i] = max(, i - f[tmp+]);
f[tmp] = min(f[tmp], i);
}
memset(f, , sizeof(f));
memset(start, , sizeof(start));
suf[n+] = ;
for(int i=n; i>=; i--){
suf[i] = suf[i+] + a[i];
int tmp = suf[i] + N;
start[i] = max(, f[tmp-] - i);
f[tmp] = max(f[tmp], i);
}
int ans = ;
for(int i=; i<=n; i++){
if(pre[i]< && suf[i+]>) ans = n;
}
for(int i=; i<=n; i++){
if(pre[i]< && start[i+]>){
ans = max(ans, i+start[i+]);
}
}
for(int i=n; i>=; i--){
if(suf[i]> && end[i-]>){
ans = max(ans, n+-i + end[i-]);
}
}
for(int i=; i<=n; i++){
if(end[i]> && start[i+]>){
ans = max(ans, end[i]+start[i+]);
}
}
printf("%d\n", ans);
}
return ;
}
05-11 17:34