https://codeforces.com/contest/1669/problem/D
好像历史上只有两场div4？
感觉E需要想一下，其他还好
input
12
5
BRBBW
1
B
2
WB
2
RW
3
BRB
3
RBB
7
WWWWWWW
9
RBWBWRRBW
10
BRBRBRBRRB
12
BBBRWWRRRWBR
10
BRBRBRBRBW
5
RBWBW
output
YES
NO
NO
NO
YES
YES
YES
NO
YES
NO
YES
NO
题意
题目给定一串长度为
n
n
n 由
W
W
W、
B
B
B 、
R
R
R 组成的字符串，你需要判断是否能通过操作使得一个长度为
n
n
n，仅由
W
W
W 构成的串变成该串， 操作如下：
- 选择两个连续的位置变成 R B RB RB 或者 B R BR BR，且能重复选择位置
思路
首先对于目标串 ‘
W
W
W’ 的位置，我们显然不能染色，因为我们不能将某个位置变成
W
W
W
所以我们肯定是针对由 W W W 分隔开，只剩 R 、 B R、B R、B 的子串来进行讨论
试想一下：
- 长度为 1 1 1 ， 显然我们不可能实现只对长度为1的进行染色
- 长度为 2 2 2 ， 对于 R B RB RB 与 B R BR BR 这两种肯定可以，但 R R RR RR 或 B B BB BB 并不行，因为我们每次染色都会产生一个 R R R and B B B 所以不可能在染色之后只留下 R R R 或 B B B
- 长度为 3 3 3 ，对于 R R B RRB RRB ，我们可以先染色位置 1 1 1 和 2 2 2 为 R B RB RB ， 再染色位置 2 2 2 和 3 3 3 为 R B RB RB 即可， 对于 R B R RBR RBR ，我们可以先染色位置 1 1 1 和 2 2 2 为 R B RB RB ， 再染色位置 2 2 2 和 3 3 3 为 B R BR BR 即可， 但对于 R R R RRR RRR ，由长度 2 2 2 中可知并不存在
- …
综上可知道，如果对于单一字串只存在一种字符 R R R 或 B B B ，则是不成立的，否则都可以凑出来
最后我们只用取出字串然后跑一边判断即可
AC代码
vector里面存放每一个由
W
W
W 分隔的子串
#include <bits/stdc++.h>
#include <vector>
#define endl '\n'
#define AC return 0;
using namespace std;
//#define ll long long
//#define int long long
void slove()
{
int n;
cin >> n;
string s;
cin >> s;
s = 'W' + s;
s += 'W';
// cout << s << endl;
int l = 0;
vector<string>v;
string now = "";
for(int i = 0; i < n + 2; i++)
{
if(s[i] == 'W')
{
if(now.length() > 0)
v.push_back(now);
now = "";
}
else
{
now += s[i];
}
}
for(auto t : v)
{
bool fl1 = true;
bool fl2 = true;
for(auto i : t)
{
if(i == 'R')
fl1 = false;
if(i == 'B')
fl2 = false;
}
if(fl1 || fl2)
{
cout << "NO" << endl;
return;
}
}
cout << "YES" << endl;
}
signed main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int T;cin >> T; while(T--)
slove();
AC
}
