重庆企业网站建设官网,网站建设大概价格,娄底企业网站建设公司,百度网站地图在线生成作者#xff1a;指针不指南吗 专栏#xff1a;Acwing 蓝桥集训每日一题 #x1f43e;或许会很慢#xff0c;但是不可以停下来#x1f43e; 文章目录1.砖块递推算法是一种简单的算法#xff0c;通过已知条件#xff0c;利用特定关系得出中间推论#xff0c;逐步递推指针不指南吗 专栏Acwing 蓝桥集训每日一题 或许会很慢但是不可以停下来 文章目录1.砖块递推算法是一种简单的算法通过已知条件利用特定关系得出中间推论逐步递推直到得到结果为止1.砖块 n 个砖块排成一排从左到右编号依次为 1∼n。 每个砖块要么是黑色的要么是白色的。 现在你可以进行以下操作若干次可以是 00 次 选择两个相邻的砖块反转它们的颜色。黑变白白变黑 你的目标是通过不超过 3n 次操作将所有砖块的颜色变得一致。 输入格式 第一行包含整数 T表示共有 T 组测试数据。 每组数据第一行包含一个整数 n。 第二行包含一个长度为 n 的字符串 s。其中的每个字符都是 W 或 B如果第 i 个字符是 W则表示第 i 号砖块是白色的如果第 i 个字符是 B则表示第 i 个砖块是黑色的。 输出格式 每组数据如果无解则输出一行 −1。 否则首先输出一行 k表示需要的操作次数。 如果 k0则还需再输出一行 k 个整数p1,p2,…,pk。其中 pi 表示第 i 次操作选中的砖块为 pi 和 pi1 号砖块。 如果方案不唯一则输出任意合理方案即可。 数据范围 1≤T≤10 2≤n≤200。 输入范围 4
8
BWWWWWWB
4
BWBB
5
WWWWW
3
BWB输出样例 3
6 2 4
-1
0
2
2 1思路 最后的结果可以分成两种情况全白或者是全黑 我们操作的位置只有 n-1 种所以不用考虑 3n 的情况 每个位置反转两次相当于没有反转所以我们只要考虑每个位置要不要操作就可以0或者1 如果 i 位置和我们想要的颜色不同则操作否则不所以说每个位置的操作都是确定的 把每一个位置递推一下到最后一个 最后一个在前一个位置操作或者是没有操作过后不能操作判断一下如果与第一个相同则说明符合题意。 代码实现 #includebits/stdc.h
using namespace std;int n;void update(char a)
{if(aW) aB;else aW;
}bool check(string s,char x)
{vectorint ans; //数组 ans 存操作的位置 for(int i0;i1n;i){ if(s[i]!x){ //如果不是我们想要的则更新update(s[i]);update(s[i1]);ans.push_back(i); //把操作位置放入数组中}}if(s.back()!s[0]) return false; //最后一个无法改变如果与前面不同则不能实现coutans.size()endl;for(auto i:ans) couti1 ; //输出结果return true;
}int main()
{int T;cinT;while(T--){string s;cinns;if(!check(s,W)!check(s,B)) puts(-1); //如果全白或者是全黑都不可以则输出 -1} return 0;}
