【题解】B-交换（7612. 2020牛客NOIP赛前集训营-普及组（第五场））

B-交换

思路

给定的字符串首尾相接就会成一个环，那么可以破环成列，在 s 的末尾在添加一个 s，以样例 10111010 为例，处理过后则变成了 1011101010111010，那么这样就可以找出最长的全为 的子区间长度。

注意当给定的字符串全为 时，有可能会出现 的情况，按照题意， ，所以当 为 '1' 时，递推式为 。

最终的答案就是

代码

#include<bits/stdc++.h>

using namespace std;

int main() {
    int ans = 0, cnt = 0;
    string s;
    cin >> s;
    int n = s.size()-1;
    s += s;
    int i = 0, f[200005];
    memset(f, 0x00, sizeof(f));
    for(int i = 1 ; i < s.size() ; i++) {
        if(s[i] == '1') {
            f[i] = min(f[i-1]+1, n);
        }
    }
    for(int i = 0 ; i <= 2*n ; i++) {
        ans = max(f[i], ans);
    }
    cout << ans << endl;
    return 0;
}