题解 | 牛客周赛80 d

牛客周赛80 d题

贪心+组合数学。遍历数组并记录0和1的个数，cnt[0]>cnt[1]就必须举手，“举手”并标记每次举手位置，超过两次则不可行。

• 最终无需举手则可在任意场次举两次。
• 最终需举手一次则可在标记举手位置前败场举两次或标记举手位置前败场举一次其他场次举一次。
• 最终需举手两次则可在标记第一次举手位置前败场举两次或标记第一次举手位置前败场举一次标记两次举手位置之间败场举一次。

#define ll long long
#include<bits/stdc++.h>
using namespace std;
int main(){
    ll n;
    cin>>n;
    string s;
    cin>>s;
    int p,p2,t=0;
    int cnt[2]={0};
    for(int i=0;i<n;i++){
        cnt[s[i]-'0']++;
        if(cnt[0]>cnt[1]){
            if(t>1){
                cout<<0;
                return 0;
            }
            else{
                t++;
                cnt[1]++;
                cnt[0]--;
                if(t==1){
                    p=i+1;
                }
                else{
                    p2=i+1;
                }
            }
        }
    }
    ll ans;
    if(t==0){
        ans=n*(n-1)/2;
    }
    else{
        ll c=0;
        for(int i=0;i<p;i++){
            if(s[i]=='0'){
                c++;
            }
        }
        if(t==1){
            ans=c*(c-1)/2+c*(n-c);
        }
        else{
            ll c2=0;
            for(int i=p;i<p2;i++){
                if(s[i]=='0'){
                    c2++;
                }
            }
            ans=c*(c-1)/2+c*c2;
        }
    }
    cout<<ans;
    return 0;
}