T1题解

大头 · 2019-11-13 19:55:18 · 题解

算法1

考虑预处理字符串‘0’,'1'个数的前缀和。

询问时枚举左端点和右端点，根据预处理的前缀和计算价值。

时间复杂度O(n^2)

算法2

设前缀‘0’的数量为S0_i,前缀‘1’的数量为S1_i。

则区间[l,r]对答案的贡献为S0_{r}-S0_{l-1}-S1_{r}+S1_{l-1}。

设V_i=S0_i-S1_i，则贡献可以改写为V_r-V_{l-1}。

对于固定的右端点r，显然需要找到权值最小的V_{l-1}。

一遍扫过去即可。

时间复杂度O(n)。

注意特判-1的情况

code:

#include<bits/stdc++.h>
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define ll long long
using namespace std;
const int N=100005;
char s[N];
int n,S,mx,ans;
int main(){
    scanf("%s",s+1);
    n=strlen(s+1);
    S=mx=0; ans=-1;
    For(i,1,n){
        S+=(s[i]=='0'?1:-1);
        ans=max(ans,S-mx);
        mx=min(mx,S);
    }
    printf("%d",ans);
}