题解：CF2121G Gangsta

· · 题解

传送门

题解

首先，将 \max(a,b) 转化为 \tfrac{a+b+\left\vert a-b\right\vert}{2} 这个式子，我们将 a+b 和 \left\vert a-b\right\vert 分开考虑。

关于 a+b 的式子，相当于每一个长度为 len 的区间有 n-len+1 个。

所以式子为：

\sum\limits_{i=1}^ni\times (n-i+1) =\sum\limits_{i=1}^n(i\times(n+1)-i\times i) =(n+1)\times \sum\limits_{i=1}^ni-\sum\limits_{i=1}^n(i\times i) =(n+1)\times\tfrac{n\times (n+1)}{2}-\tfrac{n\times(n+1)\times (2\times n+1)}{6} =\tfrac{n\times(n+1)}{6}\times(3\times n+3-2\times n-1) =\tfrac{n\times(n+1)}{6}\times (n+2) =\tfrac{n\times(n+1)\times(n+2)}{6}

这个。

关于 \left\vert a-b\right\vert 的式子，相当于每一个区间 \left\vert cha_r-cha_{l}\right\vert 的总和，其中 cha_i 表示前 i 个 1 的个数减去 0 的个数，字母 l,r 在 0 到 n 的范围内。

绝对值很烦怎么办？

排序 cha 数组即可，那么排序后 cha_i 被加了 i 次，被减了 n-i 次，所以加了 2\times i-n 次。

结果为：

\tfrac{\tfrac{n\times(n+1)\times(n+2)}{6}+\sum\limits_{i=0}^n(cha_i\times (2\times i-n))}{2}

这个式子。

AC code:

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=2e5+5;
int n;
int cha[N];
signed main(){
    //HAPPY!
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int tcase;
    cin>>tcase;
    while(tcase--){
        cin>>n;
        for(int i=1;i<=n;i++){
            char c;
            cin>>c;
            cha[i]=cha[i-1]+(c=='1'?1:-1);
        }
        sort(cha,cha+n+1);
        ll ans=n*(n+1ll)*(n+2)/6;
        for(int i=0;i<=n;i++){
            ans+=(2ll*i-n)*cha[i];
        }
        cout<<ans/2<<"\n";
    }
    return 0;
}