P15629 [2019 KAIST RUN Spring] Rainbow Beads

cjz1234 · 2026-03-06 17:25:40 · 题解

问题概述

我们需要找到一个最长的连续子串，使得这个子串同时对三类人来说都是色彩丰富的

1. 正常人：能看到 R、B、V 三种颜色。
2. 红色盲：将 V 看作 R。
3. 蓝色盲：将 V 看作 B。

思路

同时满足三类人，不允许任何两个相邻颜色相同，同时

• 不允许 R 和 V 相邻，因为违反红色盲。
• 不允许 B 和 V 相邻，因为违反蓝色盲。

这意味着，V 只能单独出现，不能和其他任何颜色相邻，并且相邻的颜色只能是 R 和 B 交替。

AC Code

#include<bits/stdc++.h>

using namespace std;

int main(){

    int N;
    string s;
    cin>>N>>s;
    int ans=1; //一个珠子总是有效
    int i=0;
    while(i<N){
        if(s[i]=='V'){
            // 单个V总是有效
            i++;
            continue;
        }
        int j=i;
        while(j<N && s[j]!='V') j++;
        if(i<j){
            int l=1; // 当前交替序列长度
            for(int k=i+1;k<j;k++){ 
                if(s[k]!=s[k-1]){ // 如果相邻不同
                    l++;
                    ans=max(ans,l);
                }else{ // 如果相邻相同，重新开始计数
                    l=1;
                }
            }
        }
        i=j;
    }
    cout<<ans<<endl;
    return 0;
}

本蒟蒻的第 11 篇题解，管理员大大求过。