usaco/beads.cpp at master · wdskuki/usaco · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113

/*
ID: dswei191
LANG: C++
TASK: beads
*/

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

int n;
string bead;

//获得下一个index
int next(int length, int index){
    return (index + 1 + length) % length;
}

//获得上一个index
int pre(int length, int index){
    return (index - 1 + length) % length;
}

bool checkMoveNext(int length, int & index, char & color, int & ret, vector<int> & vec){
    if(vec[index] != 0){
        return false;
    }
    if(color == '\0' || color == 'w'){
        color = bead[index];
        ret += 1;
        vec[index] = 1;
        index = next(length, index);
        return true;
    }else{
        if(bead[index] == 'w' || color == bead[index]){
            ret += 1;
            vec[index] = 1;
            index = next(length, index);
            return true;
        }else{
            return false;
        }
    }
}

bool checkMovePre(int length, int & index, char & color, int & ret, vector<int> & vec){
    if(vec[index] != 0){
        return false;
    }
    if(color == '\0' || color == 'w'){
        color = bead[index];
        ret += 1;
        vec[index] = 1;
        index = pre(length, index);
        return true;
    }else{
        if(bead[index] == 'w' || color == bead[index]){
            ret += 1;
            vec[index] = 1;
            index = pre(length, index);
            return true;
        }else{
            return false;
        }
    }
}


int checkMax(int index){
    int length = bead.length();
    vector<int> check(length, 0);
    if(length <= 0){
        return 0;
    }

    int nextIndex = index;
    int preIndex;
    char nextColor = '\0';
    char preColor = '\0';

    int count = 0;
    preIndex = pre(length, nextIndex);
    while(1){
        if(!checkMoveNext(length, nextIndex, nextColor, count, check)){
            break;
        }
    }
    while(1){
        if(!checkMovePre(length, preIndex, preColor, count, check)){
            break;
        }
    }
    return count;
}

int main(){
    ofstream fout("beads.out");
    ifstream fin("beads.in");

    fin >> n >> bead;
    int ret = 0;
    for(int i = 0; i < n; i++){
        int count = checkMax(i);
        ret = (ret < count) ? count : ret;
    }
    fout << ret <<endl;
    return 0;
}