本题为3月23日23上半学期集训每日一题中A题的题解
题面
题目描述
有2n个棋子(n≥4)排成一行,开始位置为白子全部在左边,黑子全部在右边,如下图为n=5的情形:
○○○○○●●●●●
移动棋子的规则是:每次必须同时移动相邻的两个棋子,颜色不限,可以左移也可以右移到空位上去,但不能调换两个棋子的左右位置。每次移动必须跳过若干个棋子(不能平移),要求最后能移成黑白相间的一行棋子。如n=5时,成为:
○●○●○●○●○●
任务:编程打印出移动过程。
输入
输入n。
输出
移动过程
样例输入
7
样例输出
step 0:ooooooo*******--
step 1:oooooo--******o*
step 2:oooooo******--o*
step 3:ooooo--*****o*o*
step 4:ooooo*****--o*o*
step 5:oooo--****o*o*o*
step 6:oooo****--o*o*o*
step 7:ooo--***o*o*o*o*
step 8:ooo*o**--*o*o*o*
step 9:o--*o**oo*o*o*o*
step10:o*o*o*--o*o*o*o*
step11:--o*o*o*o*o*o*o*
提示
注意格式
思路分析
在有样例的帮助下,此题不难分析.
本题让我们通过每次将相邻两个棋子和空位交换,来将原本一色连续的棋子变成两色相间的棋子.不难想到我们可以一组一组进行.我们先通过一系列操作,将两个异色棋子移动到最右端.由于每次只能动连续的两个棋子,所以这一步移动的两个异色棋子只有一种可能,那就是两个颜色交界处那两颗,所以这次移动即为: (ooooooo*******– -> oooooo–******o*) .接着我们把最右边的两个黑色棋子和空位交换(做这步的原因你马上就知道了),这次移动为: (oooooo–******o* -> oooooo******–o*) .我们来观察一下移动的结果,此时最右边两个异色的棋子已经归位,而其余部分,正好形成了比原本棋子规模少一的连续棋子的形状,也就是说,我们接下来要求的问题就是,当前有 (n-1) 个棋子,将其变为两色相间的摆法.这和之前是同一个问题,但是规模减小了,我们目前完全可以按照同样的思路对这部分继续操作.虽然这不是严格意义上的分治法
(严格意义的分治法
是把一个问题不断划分成多个子问题,直到规模小到可以解决),但是思想上是近似的,即不断把问题分小,逐渐解决.
所以这题的基本思想就是,我们不断通过上面所说的那两步操作,将每组异色棋子归位.不过这里有个问题,当问题规模为2时,我们将一组异色棋子移动过去之后,会出现这样的情况: (o–*o*o*o*o*o*o*) ,此时我们无法通过任何操作将o复位(因为一次只能移动两个相邻棋子).这怎么办呢?索性我们有样例,仔细观察样例可知,当问题规模为4,我们将两个异色棋子放到右边之后,不再进行原本的分治策略,而是采用另一种方法(具体怎么操作看样例即可,本质上是在产生 (*o) ,来把最前面一部分变成 (o*) ,以使得最后可以移动棋子),所以当递归规模为4时,我们不进行第二步操作,而是直接按照样例进行特殊操作.
由于本题的分治法
只是在单一减小问题规模,所以除了递归之外也可以用循环来解决.这边出于习惯我个人还是写的递归.
另外注意一下输出格式,步数要占2位.
参考代码
时间复杂度: (O(N))
空间复杂度: (O(N)) (计入递归占用空间)
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include
using namespace std;
using i64 = long long;
// 当前步数
int i = 0;
// 分治
void solve(string s, int n) {
// 第一步,把o*和--交换(下标规律想不出来自己数一数应该也能发现)
s[n - 1] = '-';
s[n] = '-';
s[2 * n] = 'o';
s[2 * n + 1] = '*';
cout 4) {
// 当规模大于4时进行正常操作,将最后的**和--交换
s[n - 1] = '*';
s[n] = '*';
s[2 * n - 1] = '-';
s[2 * n - 2] = '-';
cout > n;
// 生成初始状态
string s;
for (int i = 0; i
“正是我们每天反复做的事情,最终造就了我们,优秀不是一种行为,而是一种习惯” —亚里士多德
机房租用,北京机房托管,大带宽租用,IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net