526互联

「分治」黑白棋子的移动

发布时间 2023-03-23 21:00:12作者: 星双子

本题为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;
}

"正是我们每天反复做的事情，最终造就了我们，优秀不是一种行为，而是一种习惯" ---亚里士多德