「分治」黑白棋子的移动
本题为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 <bits/stdc++.h>
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 << "step" << setw(2) << i++ << ":" << s << "\n";
if (n > 4) {
// 当规模大于4时进行正常操作,将最后的**和--交换
s[n - 1] = '*';
s[n] = '*';
s[2 * n - 1] = '-';
s[2 * n - 2] = '-';
cout << "step" << setw(2) << i++ << ":" << s << "\n";
// 此时左边成为一个问题规模缩小的相同问题,递归调用函数解决
solve(s, n - 1);
} else {
// 特判,当规模为4时不进行正常的分治策略,下面的具体操作看样例即可
s[7] = '-';
s[8] = '-';
s[3] = '*';
s[4] = 'o';
cout << "step" << setw(2) << i++ << ":" << s << "\n";
s[1] = '-';
s[2] = '-';
s[7] = 'o';
s[8] = 'o';
cout << "step" << setw(2) << i++ << ":" << s << "\n";
s[1] = '*';
s[2] = 'o';
s[6] = '-';
s[7] = '-';
cout << "step" << setw(2) << i++ << ":" << s << "\n";
s[0] = '-';
s[1] = '-';
s[6] = 'o';
s[7] = '*';
cout << "step" << setw(2) << i++ << ":" << s << "\n";
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
cin >> n;
// 生成初始状态
string s;
for (int i = 0; i < n; i++) {
s += "o";
}
for (int i = 0; i < n; i++) {
s += "*";
}
s += "--"; // 因为每次移动两个,所以一定是要两个空位
cout << "step" << setw(2) << i++ << ":" << s << "\n";
solve(s, n);
return 0;
}
"正是我们每天反复做的事情,最终造就了我们,优秀不是一种行为,而是一种习惯" ---亚里士多德
这里是浙江理工大学22届ACM集训队的成员一枚鸭!
本文首发于博客园,作者:星双子,除了我自己的转载请注明原文链接:https://www.cnblogs.com/geministar/p/zstu23_3_23_A.html