题目链接:
https://codeforces.com/problemset/problem/873/B
tags: 前缀和 构造 *1500
题意：给一个长度为n的01串，找到其中一个最长的0的数量等于1的数量的子串。
想了个假算法wa了好多次搜了波题解才会。（自闭了）把所有0当作-1，1仍然当作1，求一波前缀和。记这个前缀和数组为a的话 如果a[i] = a[j]那么说明i+1,i+2,...,j这些点-1和1的个数一样，也就是题目中的0和1的个数一样，这就是一个符合题意的子串，长度为j-(i+1)+1，即j-i。
然后就随便操作一下，用一个vis数组来记录前缀和数组中某个值最早出现的次数（因为前缀和为[-1e5,1e5]），同时要防止负数，所以就把所有值+1e5，这样前缀和的范围就变成了[0,2e5]，就可以快乐地扔到数组里啦。
1 #include <cstdio>
2 #include <iostream>
3 #include <vector>
4 #include <cstring>
5 #include <algorithm>
6 #include <
string>
7 #include <map>
8 #include <
set>
9 #include <list>
10 #include <cmath>
11 #include <cstring>
12 #include <queue>
13 #include <stack>
14 #include <ctime>
15 #include <complex>
16 #include <random>
17 using namespace std;
18 #define rep(i,a,n) for (int i=a;i<n;i++)
19 #define per(i,a,n) for (int i=n-1;i>=a;i--)
20 #define forn(i,n) for(int i = 0;i<n;i++)
21 #define for1(i,n) for(int i = 1;i<=n;i++)
22 #define pb push_back
23 //#define mp make_p/**/air
24 #define all(x) (x).begin(),(x).end()
25 //#define fi first
26 #define se second
27 #define SZ(x) ((int)(x).size())
28 typedef vector<
int>
VI;
29 typedef
long long ll;
30 typedef
long double ld;
31 typedef pair<
int,
int>
PII;
32 typedef pair<ll,ll>
PLL;
33 typedef pair<
string,
string>
PSS;
34 typedef unsigned us;
35 typedef unsigned
int ui;
36 typedef unsigned
long long ull;
37 const ll mod=1e9+
9;
38 ll MOD=1e9+
7;
39 const ll inf =
2e18;
40 const int maxn =
200005;
41 const int maxa =
300005;
42 ll print_array(ll a[],
int t){cout<<
"[";
for(
int i =
0;i<t;i++){cout<<a[i];
if(i!=t-
1)cout<<
", ";}cout<<
"]"<<endl;
return 0;}
43 ll gcd(ll a,ll b) {
return b?gcd(b,a%
b):a;}
44 ll powmod(ll a,ll b) {ll res=
1;a%=mod;
if(b<
0)
return -
1;
for(;b;b>>=
1){
if(b&
1)res=res*a%mod;a=a*a%mod;}
return res;}
45 ll powmod2(ll a,ll b) {ll res=
1;a%=MOD;
if(b<
0)
return -
1;
for(;b;b>>=
1){
if(b&
1)res=res*a%MOD;a=a*a%MOD;}
return res;}
46
47 int n;
48 string s;
49 int a[maxn];
//前缀和
50 int vis[maxn];
51
52 int main(){
53 cin>>
n;
54 cin>>
s;
55 memset(vis,-
1,
sizeof(vis));
56 for(
int i =
1;i<=s.length();i++
){
57 if(s[i-
1] ==
'0'){
58 a[i] = a[i-
1] -
1;
59 }
60 else{
61 a[i] = a[i-
1] +
1;
62 }
63 }
64 int maxx =
0;
65 vis[
100000] =
0;
66 for(
int i =
1;i<=n;i++
){
67 if(vis[a[i]+
100000] == -
1) vis[a[i]+
100000] =
i;
68 else{
69 maxx = max(maxx,i-vis[a[i]+
100000]);
70 }
71 }
72 cout<<maxx<<
endl;
73
74
75
76 }
转载于:https://www.cnblogs.com/regen/p/10458708.html
相关资源：数据结构—成绩单生成器
