526互联

1699D - Colorful Stamp

发布时间 2023-06-18 12:40:24作者: Cruzz

题目链接：https://codeforces.com/problemset/problem/1669/D

题意：有n个初始为白色的方格组成一个方格串，即 WWWWW； 你可以无限次的为2个相邻的方格涂上颜色BR或RB，涂色可以覆盖。输入t串涂色了的方格串，求每个方格串是否能仅用RB和BR涂色得出。

思路：因为你无法将有颜色的格子（R,B）涂成白色（W），所以输入的方格串中的W肯定是没被涂色的，所以我们只要确定2个W之间的格子能涂成目标色就好。同时，经过试验可以发现一个规律，就是1个格子是无法涂色的，2个格子只能涂WW,RB,BR,3个格子或以上只要出现R和B就都可以涂成任意颜色。

AC代码：

//首先排除暴力枚举的做法 绝对难写+超时 一定是找规律 
//多试几次之后发现  1）全部是单色是不可能实现的 2）只要有2个颜色 而且数量在3个或以上 都可以实现 3）“W”不能上色 所以就看“W”两边的是不是有2颜色 
#include <bits/stdc++.h>
using namespace std;
int n,x,cnt,r,b,flag,f;
string a;
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>x>>a;
        cnt=0,r=0,b=0,flag=0;
//这么写的话会出问题 就是比如WW这种能过的 会输出no 
//        if(x<3){
//            cout<<"NO"<<endl;
//            continue;
//        }
        if(x==1){
            if(a[0]=='W'){
                cout<<"YES"<<endl;
            }
            else{
                cout<<"NO"<<endl; 
            }
            continue;
        }
        if(x==2){
            if((a[0]=='W'&&a[1]=='W')||(a[0]=='R'&&a[1]=='B')||(a[0]=='B'&&a[1]=='R')){
                cout<<"YES"<<endl;
            }
            else{
                cout<<"NO"<<endl;
            }
            continue;
        }
        a=a+"W"; //为了解决RBWR这种检测不到最后一个R的情况，在结尾加上一个W 对计算是没影响的 
        x++; 
        for(int j=0;j<x;j++){
            if(a[j]=='R'){
                r=1;
                cnt++;
            }
            else if(a[j]=='B'){
                b=1;
                cnt++;
            }
            else{
                if(cnt==0){
                    continue;
                }
                if(r==0||b==0){
                    flag=1;
                    break;
                }
                cnt=0;
                r=0;
                b=0;
            }
        }
        if(flag==0){
            cout<<"YES"<<endl;
        }
        else{
            cout<<"NO"<<endl;
        }
    }
    return 0;
}