1.題目

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。

輸入樣例1：
4
8
BWWWWWWB
4
BWBB
5
WWWWW
3
BWB

輸出樣例1：

3
6 2 4
-1
0
2
2 1

2.基本思想

思路：貪心

• 最終的字符串，要么全為白色，要么全為黑色。
• 以目標全為白色為例，遍歷字符串的前 n?1個磚塊，每遇到一個黑色磚塊，就對其進行一次操作，將該磚塊和下一個磚塊變為另一種顏色，并將結果記錄到數組中。如果發現最后一個磚塊不為白色，那說明無法將磚塊全部轉化為白色；黑色同理。
• 若最終全轉化為白色和全轉化為黑色均不可行，則輸出 ?1，否則輸出一種可行的方案即可。

3.代碼實現

import java.util.ArrayList;
import java.util.Scanner;public class Main {static Scanner sc = new Scanner(System.in);static char[]ss;static void update(int i){if (ss[i]=='W'){ss[i] = 'B';}else {ss[i] = 'W';}}static boolean check(String temp ,char c) {ArrayList<Integer> res = new ArrayList<>();ss = temp.toCharArray();int n = ss.length;for (int i = 0; i + 1 < n; i++) {if (ss[i] != c) {update(i);update(i+1);res.add(i);}}if (ss[ss.length-1]!=ss[0]){return false;}System.out.println(res.size());for (Integer re : res) {System.out.print(re+1 +" ");}if (res.size()!=0){System.out.println();}return true;}public static void main(String[] args) {int t = sc.nextInt();while (t-- > 0) {int n = sc.nextInt();String temp = sc.next();if (!check(temp, 'W') && !check(temp, 'B')) {System.out.println("-1");}}}
}