一、题目
1、原题链接
3777. 砖块
2、题目描述
n 个砖块排成一排，从左到右编号依次为 1∼n。
每个砖块要么是黑色的，要么是白色的。
现在你可以进行以下操作若干次（可以是 0 次）：
选择两个相邻的砖块，反转它们的颜色。（黑变白，白变黑）
你的目标是通过不超过 3n 次操作，将所有砖块的颜色变得一致。
输入格式
第一行包含整数 T，表示共有 T 组测试数据。
每组数据第一行包含一个整数 n。
第二行包含一个长度为 n 的字符串 s 。其中的每个字符都是 W 或 B，如果第 i个字符是 W，则表示第 i 号砖块是白色的，如果第 i
个字符是 B，则表示第 i个砖块是黑色的。
输出格式
每组数据，如果无解则输出一行 −1 。
否则，首先输出一行 k ，表示需要的操作次数。
如果 k>0 ，则还需再输出一行 k 个整数，p1,p2,…,pk。其中 pi 表示第 i 次操作，选中的砖块为 pi 和 pi+1 号砖块。
如果方案不唯一，则输出任意合理方案即可。
数据范围
1≤T≤10，2≤n≤200。
输入样例：
4
8
BWWWWWWB
4
BWBB
5
WWWWW
3
BWB
输出样例：
3
6 2 4
-1
0
2
2 1
二、解题报告
1、思路分析
思路来源：y总每日一题b站视频链接
y总yyds
（1）最终结果只有两种，全黑和全白。而每个位置只会操作0或1次，如果操作多次的话，操作结果必然和操作0次或1次中其中一个结果相同。并且每个砖块的颜色只与其被操作的次数有关，而与操作的顺序无关。
（2）假设我们从前往后依次操作，来使所有砖块颜色相同，即依次遍历每个砖块，如果与预期颜色不同，则操作它和它后面一个砖块使该位置砖块的颜色满足条件，直到遍历到最后一个砖块，它的砖块颜色无法再进行改变（因为前面的砖块已经满足条件，若要改变砖块颜色只能改变它和它后面与它相邻的砖块的颜色，而它是最后一个砖块，无法再进行操作），所以如果最后一个砖块的颜色符合预期，则可以使所有砖块颜色相同；否则不能。
（3）模拟此过程，统计满足条件的结果数，输出即可。
2、时间复杂度
每次判断是否可以将砖块统一成黑色或白色的时间复杂度为O(n)
3、代码详解
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int t;
int n;
string s;
//判断砖块是否能统一成某一种颜色（全黑或全白）
bool check(char x){
vector<int> ans; //存储每次操作
string tmp=s; //因为要判断两次（全黑和全白）所以不能在原串进行操作
for(int i=0;i<n-1;i++){
if(tmp[i]!=x){
ans.push_back(i); //将当前位置记录到需要改变的答案序列中
//改变当前位置和其后边相邻位置的颜色
if(tmp[i]=='B') tmp[i]='W';
else tmp[i]='B';
if(tmp[i+1]=='B') tmp[i+1]='W';
else tmp[i+1]='B';
}
}
if(tmp.back()!=x) return false; //如果最后一个位置和预期颜色不同，则无法使全部砖块颜色一致，返回false
//如果存在就按题目要求输出
cout<<ans.size()<<endl;
for(int i=0;i<ans.size();i++){
cout<<ans[i]+1<<' ';
}
if(ans.size()) cout<<endl;
return true;
}
int main(){
cin>>t;
while(t--){
cin>>n;
cin>>s;
if(!check('B')&&!check('W')) cout<<-1<<endl; //如果全黑和全白都无法实现，则输出-1
}
return 0;
}
三、知识风暴
递推
递推可以解决从前面已知态可以逐步推导出后续未知态的问题。
