题目描述
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
(讨论奇偶性，遍历) $O(n)$
1.如果个数都是奇数次，则不可能构造出来
2.如果w是奇数个。那就把b变成w
3.如果b是奇数个，或者b和w都是偶数个。把w都变成b即可
时间复杂度
参考文献
python3 代码
T = int(input())
for _ in range(T):
n = int(input())
s = input()
s = list(s)
w_cnt = 0
b_cnt = 0
for c in s:
if c == 'W':
w_cnt += 1
else:
b_cnt += 1
if w_cnt % 2 == 1 and b_cnt % 2 == 1:
print(-1)
else:
res_cnt = 0
res = []
if w_cnt % 2 == 1: #w是奇数个，b是偶数个。则b要变w
i = 0
while i < n - 1:
if s[i] == 'B' and s[i+1] == 'B':
s[i] = 'W'
s[i+1] = 'W'
res_cnt += 1
res.append(i + 1)
i += 2
elif s[i] == 'B' and s[i+1] == 'W':
s[i] = 'W'
s[i+1] = 'B'
res_cnt += 1
res.append(i + 1)
i += 1
elif s[i] == 'W':
i += 1
# 则w要变b
else:
i = 0
while i < n - 1:
if s[i] == 'W' and s[i+1] == 'W':
s[i] = 'B'
s[i+1] = 'B'
res_cnt += 1
res.append(i + 1)
i += 2
elif s[i] == 'W' and s[i+1] == 'B':
s[i] = 'B'
s[i+1] = 'W'
res_cnt += 1
res.append(i + 1)
i += 1
elif s[i] == 'B':
i += 1
if res_cnt > 0:
print(res_cnt)
for x in res:
print(x, end = ' ')
print()
else:
print(0)
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
int T; cin >> T;
while (T --)
{
int n; cin >> n;
string s; cin >> s;
int w_cnt = 0;
int b_cnt = 0;
for (char c : s)
{
w_cnt += (c == 'W');
b_cnt += (c == 'B');
}
if (w_cnt % 2 == 1 && b_cnt % 2 == 1)
{
cout << -1 << endl;
}
else
{
int res_cnt = 0;
vector<int> res;
if (w_cnt % 2 == 1) //w是奇数个，b是偶数个。则b要变w
{
int i = 0;
while (i < n - 1)
{
if (s[i] == 'B' && s[i+1] == 'B')
{
s[i] = 'W';
s[i+1] = 'W';
res_cnt ++ ;
res.push_back(i + 1);
i += 2;
}
else if (s[i] == 'B' && s[i+1] == 'W')
{
s[i] = 'W';
s[i+1] = 'B';
res_cnt ++;
res.push_back(i + 1);
i ++;
}
else if (s[i] == 'W')
{
i ++;
}
}
}
else //w要变b
{
int i = 0;
while (i < n - 1)
{
if (s[i] == 'W' && s[i+1] == 'W')
{
s[i] = 'B';
s[i+1] = 'B';
res_cnt ++;
res.push_back(i + 1);
i += 2;
}
else if (s[i] == 'W' && s[i+1] == 'B')
{
s[i] = 'B';
s[i+1] = 'W';
res_cnt ++;
res.push_back(i + 1);
i += 1;
}
else if (s[i] == 'B')
{
i ++;
}
}
}
if (res_cnt > 0)
{
cout << res_cnt << endl;
for (int x : res)
{
cout << x << ' ';
}
cout << endl;
}
else
{
cout << 0 << endl;
}
}
}
return 0;
}
java 代码
import java.util.* ;
public class Main
{
public static void main(String [] args)
{
Scanner scan = new Scanner(System.in);
int T = scan.nextInt();
while (T -- > 0)
{
int n = scan.nextInt();
String ss = scan.next();
char [] s = ss.toCharArray();
int w_cnt = 0;
int b_cnt = 0;
for (int i = 0; i < n ; i ++)
{
if (s[i] == 'W')
w_cnt ++;
else
b_cnt ++;
}
if (w_cnt % 2 == 1 && b_cnt % 2 == 1)
{
System.out.println(-1);
}
else
{
int res_cnt = 0;
List<Integer> res = new ArrayList();
if (w_cnt % 2 == 1) ////w是奇数个，b是偶数个。则b要变w
{
int i = 0;
while (i < n - 1)
{
if (s[i] == 'B' && s[i+1] == 'B')
{
s[i] = 'W';
s[i+1] = 'W';
res_cnt ++ ;
res.add(i + 1);
i += 2;
}
else if (s[i] == 'B' && s[i+1] == 'W')
{
s[i] = 'W';
s[i+1] = 'B';
res_cnt ++;
res.add(i + 1);
i ++;
}
else if (s[i] == 'W')
{
i ++;
}
}
}
else //w要变b
{
int i = 0;
while (i < n - 1)
{
if (s[i] == 'W' && s[i+1] == 'W')
{
s[i] = 'B';
s[i+1] = 'B';
res_cnt ++;
res.add(i + 1);
i += 2;
}
else if (s[i] == 'W' && s[i+1] == 'B')
{
s[i] = 'B';
s[i+1] = 'W';
res_cnt ++;
res.add(i + 1);
i += 1;
}
else if (s[i] == 'B')
{
i ++;
}
}
}
if (res_cnt > 0)
{
System.out.println(res_cnt);
for (int x : res)
{
System.out.print(x);
System.out.print(" ");
}
System.out.println();
}
else
{
System.out.println(0);
}
}
}
}
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
### 好好好
请问res修改的时候为什么下标是i+1而不是i
###orz