CF148B Balanced Substring- 1500

VJ传送门

题目思路

预处理从前往后和从后往前计数 \(0\) 和 \(1\) 的个数。

从前往后枚举段的开头，找到期望中段的结尾，记录长度。用 map 记录。

然而，代码很矢。下面的Better Code里有更好的代码，思路差不多，附有详细注释。

AC Code

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,f1[N],f0[N],b1[N],b0[N],s1,s0,ans;
unordered_map<int,int>mp;
string s;
signed main(){ios::sync_with_stdio(0),cin.tie(0);cin>>n>>s;s=" "+s;for(int i=1;i<=n;i++){f1[i]=f1[i-1];f0[i]=f0[i-1];if(s[i]=='0')	f0[i]++,s0++;else	f1[i]++,s1++;}mp[0]=n+1;for(int i=n;i>=1;i--){b1[i]=b1[i+1];b0[i]=b0[i+1];if(s[i]=='0')	b0[i]++;else	b1[i]++;if(!mp.count(b1[i]-b0[i])){mp[b1[i]-b0[i]]=i;}}for(int i=0;i<=n;i++){int w=s1-s0-f1[i]+f0[i];if(mp.count(w)){ans=max(ans,mp[w]-1-i);}}cout<<ans;return 0;
}

Better Code

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,k=0,sum,ans,a[N<<1];//细节乘2 
//a[]其实是个桶，(下面代码)需要+n是因为k有可能小于0 
string s;
signed main(){ios::sync_with_stdio(0),cin.tie(0);cin>>n>>s;s=" "+s;for(int i=1;i<=n;i++){k+=(s[i]=='0'?-1:1);if(k!=0&&a[k+n]==0)	a[k+n]=i;//从来没有出现过k(+n) ans=max(ans,i-a[k+n]);//记录长度 }cout<<ans;return 0;
}