题目描述
$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
算法
(暴力枚举) $O(n^2)$
write here…
时间复杂度
write here…
空间复杂度
write here…
两种情况
结果要么全是黑 要么全是白
把两种情况全部模拟一遍 统计一下操作数
如果这两种情况都不满足(s[n] != ‘B’ && t[n] != ‘W’) –> -1;
满足全是白色的情况就是 s[n] != ‘B’
满足全是黑色的情况就是 t[n] != ‘W’
C++ 代码
#include "bits/stdc++.h"
using namespace std;
int n;
string s;
void solve() {
vector<int> w, v;
cin >> n >> s;
s = "?" + s;
string t = s;
int res1 = 0, res2 = 0;
for (int i = 1; i < n; i++) {
// 黑
if (s[i] == 'W') {
s[i] = 'B';
if (s[i + 1] == 'B') s[i + 1] = 'W';
else s[i + 1] = 'B';
v.push_back(i);
res1++;
}
// 白
if (t[i] == 'B') {
t[i] = 'W';
if (t[i + 1] == 'B') t[i + 1] = 'W';
else t[i + 1] = 'B';
w.push_back(i);
res2++;
}
}
if (s[n] != 'B' && t[n] != 'W') {
cout << -1 << '\n';
} else if (s[n] != 'B') {
cout << res2 << '\n';
for (auto op : w) cout << op << " ";
if (res2) cout << '\n';
} else {
cout << res1 << '\n';
for (auto op : v) cout << op << " ";
if (res1) cout << '\n';
}
}
int main() {
int T; cin >> T;
while (T --) {
solve();
}
return 0;
}