USACO training 1.2 断开的项链

将区间n多复制一份成为2n

每次枚举一个长度是n的区间

#include<bits/stdc++.h>
using namespace std;
const int N = 710;
char s[N];

int get( char c ) {
    // 1表示蓝色，2表示红色
    if( c == 'b') return 1;
    return 2;
}
int main( ) {
    int n;
    cin >> n >> s;
    // 破链成环，构造出长度为2n的字符串
    for( int i = 0; i < n; i++ ) s[i+n] = s[i];
    int res = 0;

    for ( int i = 0; i < n; i++ ) {
        int l = i ,r = n + i - 1;

        // left用二进制状态表示从左(前一个n) 开始，拿的颜色的二进制状态，right表示右边
        int cnt = 0, left = 0, right = 0;
        // 左右指针一个向前，一个回退，在一个长度为n的区间内扫描
        while(l <= r && ( s[l] =='w' || (left | get(s[l])) != 3 )) {
            if( s[l] != 'w' ) left |= get(s[l]);
            cnt++, l++;
        }
        while( l <=r  &&( s[r] =='w' || (right | get(s[r])) != 3 ) ) {
            if( s[r] != 'w' ) right |= get(s[r]);
            cnt++, r--;
        }
        res = max( res, cnt);
    }
    cout << res;
    return 0;

}