AcWing 3777. 砖块
本文最后更新于501 天前,其中的信息可能已经过时,如有错误请发送邮件到1739584917@qq.com

题目

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≤20。

输入样例:

4
8
BWWWWWWB
4
BWBB
5
WWWWW
3
BWB

输出样例:

3
6 2 4
-1
0
2
2 1

思路:

对于最终的字符串,只有两种,要么全为W,要么全为B;

那么,可以对两种转化方法分别模拟,一种以目标为白色进行转化,一种以目标为黑色进行转化

以目标为白色为例:从前往后进行遍历字符串,如果s[i]==‘B’,就对当前位置进行操作,将i,i+1的颜色变成另一种颜色,如果遍历完,字符串末尾不为‘W’,则不能完全转化为白色。目标为黑色同理。如果既不能转化为完全转化为黑色,也不能完全转化为白色,则输出-1;

代码:

#include<iostream>
#include<string>
#include<vector>
using namespace std;
string s;
int t, n;
int main()
{
	cin >> t;
	while (t--)
	{
		int op1 = 0, op2 = 0;
		cin >> n;
		cin >> s;
		string strw = s, strb = s;
		vector<int>w, b;
		for (int i = 0; i < n - 1; i++)
		{
			//全部变成W
			if (strw[i] == 'B')
			{
				strw[i] = 'W';
				if (strw[i + 1] == 'W')strw[i + 1] = 'B';
				else strw[i + 1] = 'W';
				w.push_back(i + 1);
				op1++;
			}
			//全部变成B
			if (strb[i] == 'W')
			{
				strb[i] = 'B';
				if (strb[i + 1] == 'W')strb[i + 1] = 'B';
				else strb[i + 1] = 'W';
				b.push_back(i + 1);
				op2++;
			}
		}
		if (strw[n - 1] != 'W' && strb[n - 1] != 'B')cout << -1 << endl;
		else if (strw[n - 1] == 'W')
		{
			cout << op1 << endl;
			for (int op : w)
			{
				cout << op << " ";
			}
			if(op1)cout << endl;
		}
		else if (strb[n - 1] == 'B')
		{
			cout << op2 << endl;
			for (int op : b)
			{
				cout << op << " ";
			}
			if(op2)cout << endl;
		}
	}
}

也可以对W与B的个数的奇偶性进行判断:

1.如果个数都是奇数次,则不可能构造出来

2.如果W是奇数个。那就转化为W

3.如果B是奇数个,或者B和W都是偶数个。那就转化为B

代码大同小异,就不再写了

如果觉得本文对您有所帮助,可以支持下博主,一分也是缘
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇