题解：P16866 [GKS 2021 #H] Painter

Zxc1234567 · 2026-06-11 13:33:58 · 题解

前言

看到题目有点懵，最后发现是一道水题，根据题意模拟即可。

题目大意

有一块长度为 N 个格子的画布，一开始全都没上色。每次只能选红、黄、蓝其中一种颜色，涂抹成一块与 P 相等的画布，求所需的最少笔划数。

思路

题目告诉我们怎么染色的步骤很清楚，无需多解释。因此我们可以建立三个变量分别表示红色、黄色、蓝色。

将这三个变量初始化为零。接下来遍历字符串 P，判断当前用到的画笔是否为零，若为零是则变成一，且步数加一；反之不变，并将不用的画笔归零。

根据这种思路模拟即可，最终便能得出答案。

AC Code

# include <bits/stdc++.h>
using namespace std;
int main(){
    int T,N,ans;
    string s;
    cin>>T;
    for(int d=1;d<=T;d++){
        cin>>N>>s;
        bool R=0,Y=0,B=0;
        ans=0;
        for(int i=0;i<s.size();i++){
            if(s[i]=='U') R=0,Y=0,B=0;//将所有的画笔全部归零
            if(s[i]=='R'){
                if(R==0) ans++,R=1;
                Y=0,B=0;//将不用的画笔归零
            }
            if(s[i]=='Y'){
                if(Y==0) ans++,Y=1;
                R=0,B=0;
            }
            if(s[i]=='B'){
                if(B==0) ans++,B=1;
                R=0,Y=0;
            }
            if(s[i]=='O'){
                if(R==0) ans++,R=1;
                if(Y==0) ans++,Y=1;
                B=0;
            }
            if(s[i]=='P'){
                if(R==0) ans++,R=1;
                if(B==0) ans++,B=1;
                Y=0;
            }
            if(s[i]=='G'){
                if(Y==0) ans++,Y=1;
                if(B==0) ans++,B=1;
                R=0;
            }
            if(s[i]=='A'){
                if(R==0) ans++,R=1;
                if(Y==0) ans++,Y=1;
                if(B==0) ans++,B=1;
            }
        }
        cout<<"Case #"<<d<<": "<<ans<<'\n';//输出
    }
    return 0;
}