题目

n 个砖块排成一排，从左到右编号依次为 1∼n。

每个砖块要么是黑色的，要么是白色的。

现在你可以进行以下操作若干次（可以是 0 次）：

选择两个相邻的砖块，反转它们的颜色。（黑变白，白变黑）

你的目标是通过不超过 3n 次操作，将所有砖块的颜色变得一致。

输入格式

第一行包含整数 T，表示共有 T 组测试数据。

每组数据第一行包含一个整数 n。

第二行包含一个长度为 n 的字符串 s。其中的每个字符都是 W 或 B，如果第 i 个字符是 W，则表示第 i 号砖块是白色的，如果第 i 个字符是 B，则表示第 i 个砖块是黑色的。

输出格式

每组数据，如果无解则输出一行 −1。

否则，首先输出一行 k，表示需要的操作次数。

如果 k>0，则还需再输出一行 k 个整数，p₁,p₂,…,p_k。其中 p_i 表示第 i 次操作，选中的砖块为 p_i 和 p_i+1 号砖块。

如果方案不唯一，则输出任意合理方案即可。

数据范围

1≤T≤10，
2≤n≤20。

输入样例：

4
8
BWWWWWWB
4
BWBB
5
WWWWW
3
BWB

				

					
				
				

					
				
				

					
				
				

					
				
			

输出样例：

3
6 2 4
-1
0
2
2 1

				

					
				
				

					
				
				

					
				
				

					
				
			

思路：

对于最终的字符串，只有两种，要么全为 W，要么全为 B；

那么，可以对两种转化方法分别模拟，一种以目标为白色进行转化，一种以目标为黑色进行转化

以目标为白色为例：从前往后进行遍历字符串，如果 s [i]==‘B’，就对当前位置进行操作，将 i，i+1 的颜色变成另一种颜色，如果遍历完，字符串末尾不为‘W’，则不能完全转化为白色。目标为黑色同理。如果既不能转化为完全转化为黑色，也不能完全转化为白色，则输出 - 1；

代码：

#include<iostream>
#include<string>
#include<vector>
using namespace std;
string s;
int t, n;
int main()
{
	cin >> t;
	while (t--)
	{
		int op1 = 0, op2 = 0;
		cin >> n;
		cin >> s;
		string strw = s, strb = s;
		vector<int>w, b;
		for (int i = 0; i < n - 1; i++)
		{
			//全部变成W
			if (strw[i] == 'B')
			{
				strw[i] = 'W';
				if (strw[i + 1] == 'W')strw[i + 1] = 'B';
				else strw[i + 1] = 'W';
				w.push_back(i + 1);
				op1++;
			}
			//全部变成B
			if (strb[i] == 'W')
			{
				strb[i] = 'B';
				if (strb[i + 1] == 'W')strb[i + 1] = 'B';
				else strb[i + 1] = 'W';
				b.push_back(i + 1);
				op2++;
			}
		}
		if (strw[n - 1] != 'W' && strb[n - 1] != 'B')cout << -1 << endl;
		else if (strw[n - 1] == 'W')
		{
			cout << op1 << endl;
			for (int op : w)
			{
				cout << op << " ";
			}
			if(op1)cout << endl;
		}
		else if (strb[n - 1] == 'B')
		{
			cout << op2 << endl;
			for (int op : b)
			{
				cout << op << " ";
			}
			if(op2)cout << endl;
		}
	}
}

				

					
				
				

					
				
				

					
				
				

					
				
			

也可以对 W 与 B 的个数的奇偶性进行判断：

1. 如果个数都是奇数次，则不可能构造出来

2. 如果 W 是奇数个。那就转化为 W

3. 如果 B 是奇数个，或者 B 和 W 都是偶数个。那就转化为 B

代码大同小异，就不再写了