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

wsy_algorithm · 2026-03-06 18:52:39 · 题解

此题使用的是 ICPC 赛制。

题目传送门 & 可能更好的阅读体验

思路

这道题可以用滑动窗口，也就是双指针的方法解决。

具体步骤

• 遍历整个字符串，检查每一个相邻的字符，也就是 s_i 和 s_{i-1}。
• 然后就要开始判断了。如果是在普通人视角，就直接判断是否不同。如果是在红色盲视角，就要把 V 当成 R，再判断是否不同。如果是在蓝色盲视角，就要把 V 当成 B，再判断是否不同。
• 如果 s_i 和 s_{i-1} 这两个相邻字符在三种视角下都不同，就扩展当前窗口，而且要更新最大长度。
• 只要有一个条件不满足，就把框子左边直接挪到当前这个珠子的位置，重新框。
• 最后框子最长的长度，就是题目要的答案。输出即可。

  AC Code

  #include<bits/stdc++.h>
  using namespace std;
  int main(){
  int n;
  string s;
  cin>>n>>s;
  //7-10行其实可以不需要
  if(n==0){
      cout<<0;
      return 0;
  }
  int l=0;
  int maxlen=1;
  for(int i=1;i<n;i++){
      char c=s[i];
      char p=s[i-1];
      //检查在三种视角下，当前字符和前一个字符是否都不同
      bool f1=(c!=p); //普通人视角 
      bool f2=((c=='V'?'R':c)!=(p=='V'?'R':p)); //红色盲视角
      bool f3=((c=='V'?'B':c)!=(p=='V'?'B':p)); //蓝色盲视角
      if(f1&&f2&&f3){
          //更新最大长度
          maxlen=max(maxlen,i-l+1);
      } else {
          // 窗口不合法，重置左指针到当前右指针，开始新的窗口
          l=i;
      }
  }
  //输出 
  cout<<maxlen;
  return 0;
  }

  完结撒花！(^v^)
  祝大家 AC 本题！