侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 663 篇文章
  • 累计创建 128 个标签
  • 累计收到 15 条评论

目 录CONTENT

文章目录

【递推】砖块

GabrielxD
2023-02-17 / 0 评论 / 0 点赞 / 145 阅读 / 729 字
温馨提示:
本文最后更新于 2023-02-17,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

3777. 砖块 - AcWing题库


nn 个砖块排成一排,从左到右编号依次为 1n1 \sim n

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

现在你可以进行以下操作若干次(可以是 00 次):

选择两个相邻的砖块,反转它们的颜色。(黑变白,白变黑)

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

输入格式

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

每组数据第一行包含一个整数 nn

第二行包含一个长度为 nn 的字符串 ss 。其中的每个字符都是 WB,如果第 ii 个字符是 W,则表示第 ii 号砖块是白色的,如果第 ii 个字符是 B,则表示第 ii 个砖块是黑色的。

输出格式

每组数据,如果无解则输出一行 1-1

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

如果 k>0k>0 ,则还需再输出一行 kk 个整数, p1,p2,,pkp_1,p_2,…,p_k 。其中 pip_i 表示第 ii 次操作,选中的砖块为 pip_ipi+1p_i+1 号砖块。

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

数据范围

1T101 \le T \le 10
2n2002 \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");
        }
    }
}
0

评论区