【递推】砖块

题目

3777. 砖块 - AcWing题库

---

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

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

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

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

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

输入格式

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

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

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

输出格式

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

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

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

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

数据范围

$1 \le T \le 10$ ，
$2 \le n \le 200$ 。

输入样例：

4
8
BWWWWWWB
4
BWBB
5
WWWWW
3
BWB

输出样例：

3
6 2 4
-1
0
2
2 1

解题

方法一：递推

思路

本题相当于【递推】翻硬币的加强版。

对比翻硬币那题，这题不保证一定有解，目标状态变为了两种（砖块要么全白、要么全黑），且需要记录每一次的操作。但本题不要求最优解，只要找出是否有解，且在有解时输出操作序列即可。

具体解法及可行性证明见翻硬币那题。

代码

import java.util.*;
import java.io.*;

public class Main {
    static boolean check(char[] s, char color) {
        int n = s.length;
        List<Integer> ops = new ArrayList<>();
        for (int i = 0; i < n - 1; ++i) {
                if (s[i] != color) {
                s[i + 1] = s[i + 1] == 'W' ? 'B' : 'W';
                ops.add(i);
            }
        }
        if (s[n - 1] != color) return false;
        System.out.println(ops.size());
        for (int x : ops) System.out.print((x + 1) + " ");
        if (!ops.isEmpty()) System.out.println();
        return true;
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        in.nextToken();
        int t = (int) in.nval;
        while (t-- > 0) {
            in.nextToken();
            int n = (int) in.nval;
            char[] s = br.readLine().toCharArray();
            if (!check(s.clone(), 'W') && !check(s, 'B')) System.out.println("-1");
        }
    }
}