2020牛客NOIP赛前集训营-普及组（第五场） B

B T2 交换

题面

https://ac.nowcoder.com/acm/contest/7612/B

思路

非常裸的一个贪心思想。

观察操作，事实上它将序列首尾相连。故维护一个数组 ， 为以第位为截止同时为最后一位的连续1的个数，更新 和答案，同时去计算以第位为开头的连续1的个数 。复杂度 。

特判 的情况，此时序列全为 。

剩下的情况均为有0的情况，更新一次首尾相接的情况 。

代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <map>

using std::cin;using std::cout;using std::cerr;using std::endl;

#define rep(i,a,b) for(int i = a;i <= b;++i)
#define per(i,a,b) for(int i = a;i >= b;--i)

const int mmax = 1e5;

char s[mmax + 10];int b[mmax + 10],n,ans,temp;

int main(){

    std::ios::sync_with_stdio(0);
    cin.tie(0);

    cin>>(s + 1);

    bool f = 1;

    n = std::strlen(s + 1);

    rep(i,1,n){
        if(s[i] == '1') {
            if(f) temp++;
            b[i] = b[i - 1] + 1;
            ans = std::max(ans,b[i]);
        }
        else f = 0;
    }

    if(temp == n){
        cout<<temp;
        return 0;
    }

    ans =std::max(ans,b[n] + temp);
    cout<<ans;
    return 0;
}