网站专题方案,WordPress文章查询插件,图片网站建设方案,重庆建设银行网站首页AcWing《蓝桥杯集训每日一题》—— 3777. 砖块 文章目录AcWing《蓝桥杯集训每日一题》—— 3777. 砖块一、题目二、解题思路三、解题思路本次博客我是通过Notion软件写的#xff0c;转md文件可能不太美观#xff0c;大家可以去我的博客中查看#xff1a;北天的 BLOG#xf…AcWing《蓝桥杯集训·每日一题》—— 3777. 砖块 文章目录AcWing《蓝桥杯集训·每日一题》—— 3777. 砖块一、题目二、解题思路三、解题思路本次博客我是通过Notion软件写的转md文件可能不太美观大家可以去我的博客中查看北天的 BLOG持续更新中另外这是我创建的编程学习小组频道想一起学习的朋友可以一起 一、题目 $n$ 个砖块排成一排从左到右编号依次为 $1∼n$。 每个砖块要么是黑色的要么是白色的。
现在你可以进行以下操作若干次可以是 0 次
选择两个相邻的砖块反转它们的颜色。黑变白白变黑
你的目标是通过不超过 3n3n3n 次操作将所有砖块的颜色变得一致。
输入格式
第一行包含整数 TTT表示共有 TTT 组测试数据。
每组数据第一行包含一个整数 nnn。
第二行包含一个长度为 nnn 的字符串 sss。其中的每个字符都是 W 或 B如果第 iii 个字符是 W则表示第 iii 号砖块是白色的如果第 iii 个字符是 B则表示第 iii 个砖块是黑色的。
输出格式
每组数据如果无解则输出一行 −1。
否则首先输出一行 kkk表示需要的操作次数。
如果 k0k0k0则还需再输出一行 kkk 个整数p1,p2,…,pkp1,p2,…,pkp1,p2,…,pk。其中 pip_ipi 表示第 iii 次操作选中的砖块为 pip_ipi 和 pi1p_i1pi1 号砖块。
如果方案不唯一则输出任意合理方案即可。
数据范围
1≤T≤101≤T≤101≤T≤10
2≤n≤2002≤n≤2002≤n≤200。
输入样例
4
8
BWWWWWWB
4
BWBB
5
WWWWW
3
BWB输出样例
3
6 2 4
-1
0
2
2 1二、解题思路 目前来说我还不太会做这道题还没有复习到这里来在这里我参考了一下别的大佬的代码[传送门](https://www.acwing.com/solution/content/58401/)学习了一下其他大佬的代码也是可以的我在这里写一下代码的具体实现思路。 这道题目需要我们实现的是对给定字符串s进行操作使得其变成一个全为’B’或全为’W’的字符串并输出操作次数以及具体的操作。操作规则为如果s中’B’和’W’个数均为偶数则不需要进行任何操作如果’B’个数为奇数需要对相邻的两个’B’进行操作使其变成’W’或者将’B’和’W’对调使得’B’个数变为偶数然后进行相邻的’B’操作使其变成’W’。如果’W’个数为奇数操作方法与’B’个数奇数的情况相似。
具体来说我们在实现的过程是先计算’B’和’W’的个数然后根据个数的奇偶性进行分类讨论。当’B’和’W’的个数均为偶数时不需要操作。当其中一个为奇数时需要对相邻的两个颜色相同的块进行操作使其变成相反的颜色或者将两个不同颜色的块进行对调使得颜色个数为偶数。通过循环操作后最终得到一个全为’B’或者全为’W’的字符串。最后输出操作次数和具体操作的序列。
三、解题思路
具体实现代码如下如何还有可以优化的地方可以提出来 # 输入测试用例数量
T int(input())
for _ in range(T):# 输入字符串长度和字符串n int(input())s list(input())# 统计W和B的数量w_cnt s.count(W)b_cnt s.count(B)# 判断是否有解if w_cnt % 2 1 and b_cnt % 2 1:print(-1) # 没有解else:res_cnt 0 # 记录需要操作的次数res [] # 记录操作的位置if w_cnt % 2 1: # W的数量为奇数需要将一些B变成Wi 0while i n - 1:if s[i] B and s[i1] B: # 连续的两个B都变成Ws[i] Ws[i1] Wres_cnt 1res.append(i 1)i 2elif s[i] B and s[i1] W: # 只将前面的B变成Ws[i] Ws[i1] Bres_cnt 1res.append(i 1)i 1elif s[i] W: # 如果是W则不用操作i 1else: # B的数量为奇数需要将一些W变成Bi 0while i n - 1:if s[i] W and s[i1] W: # 连续的两个W都变成Bs[i] Bs[i1] Bres_cnt 1res.append(i 1)i 2elif s[i] W and s[i1] B: # 只将前面的W变成Bs[i] Bs[i1] Wres_cnt 1res.append(i 1)i 1elif s[i] B: # 如果是B则不用操作i 1# 输出结果if res_cnt 0:print(res_cnt)for x in res:print(x, end )print()else:print(0)这段代码的时间复杂度为O(Tn)O(Tn)O(Tn)其中TTT是测试用例的数量nnn是输入字符串的长度。这是因为代码中有一个外层循环循环TTT次而每次循环中都要对长度为nnn的输入字符串进行遍历所以总时间复杂度是O(Tn)O(Tn)O(Tn)。
在代码中使用了一些内置函数和操作如**s.count()和s[i]**等这些操作的时间复杂度较低可以忽略不计。因此这段代码的主要瓶颈在于对输入字符串的遍历和修改操作。
如果要优化这段代码的时间复杂度可能需要重新设计算法。可以考虑一些贪心策略如将相邻的不同颜色的棋子互换使得相邻的棋子颜色相同。这样可以尽可能地减少需要修改的棋子数量。但这个算法的正确性需要进行证明同时实现也可能会比较复杂。
