题解：P15629 [2019 KAIST RUN Spring] Rainbow Beads

amlhdsan · 2026-03-07 23:01:05 · 题解

非常好想的一道题，在实现上有一点细节需要注意。

首先，对于一个序列，我们从三个视角来看：非色盲人士，红色盲人士和蓝色盲人士。对序列扫三遍。第一遍看是否有相邻两个字母相同，打上标记。第二遍看 R 和 V 的相邻。第三遍看 B 和 V 的相邻。

下面考虑如何打标记。

列出一个 tag 数组，当第 i 个和第 i + 1 个产生冲突时，我们标记 tag_i 为 1。否则为 0。

然后对着 tag 数组扫一遍，找出最长的连续的 0 的个数，加一即为答案。

完整代码：

#include <bits/stdc++.h>

#define N 250010

using namespace std;

int n;
string str;
bool tag[N];

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}

inline void write(int x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

inline void writeln(int x) {
    write(x);
    putchar('\n');
}

int main() {

    n = read();
    cin >> str;
    memset(tag, 0, sizeof tag);

    str = " " + str;

    for(int i = 1; i <= n - 1; ++i) {
        if(str[i] == str[i + 1]) {
            tag[i] = 1;
        }
        if(str[i] == 'R' && str[i + 1] == 'V' || str[i] == 'V' && str[i + 1] == 'R') {
            tag[i] = 1;
        }
        if(str[i] == 'B' && str[i + 1] == 'V' || str[i] == 'V' && str[i + 1] == 'B') {
            tag[i] = 1;
        }
        // writeln(tag[i]);
    }

    int maxx = 0;
    int nl = 0;

    for(int i = 1; i <= n - 1; ++i) {
        if(tag[i] == 0) {
            ++nl;
        }
        else {
            maxx = max(maxx, nl);
            nl = 0;
        }
    }
    maxx = max(maxx, nl);

    writeln(maxx + 1);

    return 0;
}