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

giantsoft · 2026-03-06 22:10:43 · 题解

思路

色彩丰富的串珠只需满足以下要求：

• 相邻两颗珠子颜色不同。
• 紫色珠子不能和任何其它珠子相邻。

所以我们需要扫描字符串，找所有连续的纯红色或蓝色珠子的交替段。

需注意：

• 遇到紫色珠子就跳过。
• 从当前非紫色珠子位置开始，向右扩展。
• 满足下一个不是紫色珠子，且与当前字符不同。
• 记录这段长度，更新 ans。

CODE

#include<bits/stdc++.h>
using namespace std;
int main() {
    int n;
    string s;
    cin >> n >> s;
    int ans = 1;  // 至少有一个珠子
    //找最长的纯 R/B 交替段
    for(int i = 0; i < n; ) {
        if(s[i] == 'V') {
            i++;
            continue;
        }
        // 开始一个 R/B 段
        int len = 1;
        int j = i + 1;
        while(j < n && s[j] != 'V' && s[j] != s[j - 1]) {
            len++;
            j++;
        }
        ans = max(ans, len);
        i = j;
    }
    cout << ans << endl;
    return 0;
}