题解：P16866 [GKS 2021 #H] Painter

dgz61 · 2026-06-10 22:37:22 · 题解

题意

这道题的背景是在一块长度为 N 的一维画布上作画。初始时，画布上的所有格子都是未涂色的。我们每次可以使用三种原色之一（红色 R、黄色 Y、蓝色 B），对画布上的一个连续区间进行涂抹。下面是规则。

• 红色 + 黄色 = 橙色
• 红色 + 蓝色 = 紫色
• 黄色 + 蓝色 = 绿色
• 红色 + 黄色 + 蓝色 = 灰色

  思路

  因为对一个连续区间涂抹且每一个点的三原色顶多涂抹一次，所以可以枚举整个序列并用三个变量记录三原色连续用了几次，遇到没有用这种颜色的变量清零重新计算并且答案加一。对于每种颜色处理放代码中了，毕竟有了思路就很好实现了。

  代码

  注意枚举结束后还要再处理一遍三原色变量防止最后一笔未计入答案。

  #include<bits/stdc++.h>
  #define ll int64_t
  #define endl '\n'
  using namespace std;
  ll t,n;
  string p;
  int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);cout.tie(0);
  cin>>t;
  ll T=t;
  while(t--){
      cin>>n>>p;
      ll r=0,y=0,b=0,ans=0;
      for(ll i=1;i<=n;i++){
          if(p[i-1]=='U'){
              if(r>0) r=0,ans++;
              if(y>0) y=0,ans++;
              if(b>0) b=0,ans++;
          }//处理无颜色，三原色一个不用，变量全部清空，答案增加
          else if(p[i-1]=='R'){
              r++;
              if(y>0) y=0,ans++;
              if(b>0) b=0,ans++;
          }//处理红色，只用红色，黄蓝变量清空，答案增加
          else if(p[i-1]=='Y'){
              y++;
              if(r>0) r=0,ans++;
              if(b>0) b=0,ans++;
          }//处理黄色，只用黄色，红蓝变量清空，答案增加
          else if(p[i-1]=='B'){
              b++;
              if(r>0) r=0,ans++;
              if(y>0) y=0,ans++;
          }//处理蓝色，只用蓝色，红黄变量清空，答案增加
          else if(p[i-1]=='O'){
              r++;
              y++;
              if(b>0) b=0,ans++;
          }//处理橙色，用红黄色，蓝色变量清空，答案增加
          else if(p[i-1]=='P'){
              r++;
              b++;
              if(y>0) y=0,ans++;
          }//处理紫色，用红蓝色，黄色变量清空，答案增加
          else if(p[i-1]=='G'){
              y++;
              b++;
              if(r>0) r=0,ans++;
          }//处理绿色，用黄蓝色，红色变量清空，答案增加
          else{
              r++;
              y++;
              b++;
          }//处理灰色，三原色全用，ryb全部累加
      }
      if(r>0) ans++;
      if(y>0) ans++;
      if(b>0) ans++;//注意最后还要再处理一遍防止最后一笔未计入答案
      cout<<"Case #"<<T-t<<": "<<ans<<endl;
  }
  return 0;
  }

  总体来说题目思维难度与实现难度都不大，算个下位黄吧。