P6892 [ICPC2014 WF] Baggage 题解

· · 题解

很有意思的构造题。

思路

首先考虑最小步数。

由于最终要达到的状态相邻部分相同的对数需要为 2\times n-2。

我们的操作中，第一次操作最多产生 1 对相同，其余操作最多产生 2 对相同。

所以我们有了最小步数的下界 n。

考虑能否达到这个最小步数。

考虑状态：

\color{black}OOBABABABABABABABABABABABA

一个较长的序列，O 代表空位，A 代表一，B 代表二。

考虑构造：

\color{red}AB\color{black}BABABABABABABABABABAB\color{blue}OO\color{black}A \color{black}ABBA\color{blue}OO\color{black}BABABABABABABABAB\color{red}BA\color{black}A

发现了什么。

\color{black}ABBA\color{red}OOBABABABABABABABA\color{black}BBAA

红色段变成了一个相同的子问题，n\rightarrow n-4。

假如我们把红色段排好序之后。

\color{black}ABBA\color{red}AAAAAAAABBBBBBBBOO\color{black}BBAA

很容易继续构造。

\color{black}A\color{blue}OO\color{black}AAAAAAAAABBBBBBBB\color{red}BB\color{black}BBAA \color{black}A\color{red}AA\color{black}AAAAAAAAABBBBBBBBBBBB\color{blue}OO

这样就做到了在四步的操作下将 n\rightarrow n-4。

由于 n=1,2 无法操作且 n=3 无法再仅空两格的情况下复原。

所以我们只在 n\ge 8 的情况下递归求解。

至于 n<8 的情况可以直接暴搜求解。

Code

由于 n=7 跑的不是很快（几百毫秒），所以追求速度也可以打表（不打表也能过）。

#include <cstdio>
#include <vector>
using namespace std;

const int N = 5010;

int *a, d[N << 1];
vector<pair<int, int>> res;
vector<pair<int, int>> ans;

inline bool dfs(int l, int r, int k) {
    // if (k == 7) {
    //  res.emplace_back(l + 9, l);
    //  res.emplace_back(l + 6, l + 9);
    //  res.emplace_back(l + 13, l + 6);
    //  res.emplace_back(l + 4, l + 13);
    //  res.emplace_back(l + 10, l + 4);
    //  res.emplace_back(l + 1, l + 10);
    //  res.emplace_back(l + 14, l + 1);
    //  return 1;
    // }
    int x = l + k, y = l + k + k, flag = 1;
    for (int i = l; i < x && flag; i++) if (a[i] != 1) flag = 0;
    for (int i = x; i < y && flag; i++) if (a[i] != 2) flag = 0;
    if (flag == 1) return 1;
    if (res.size() == k) return 0;
    vector<int> id;
    for (int i = l; i <= r; i++) {
        if (a[i] == 0 && a[i + 1] == 0) {
            id.emplace_back(i);
        }
    }
    for (int i = l; i <= r; i++) {
        if (a[i] != 0 && a[i + 1] != 0) {
            for (auto j : id) {
                swap(a[i], a[j]), swap(a[i + 1], a[j + 1]);
                res.emplace_back(i, j);
                if (dfs(l, r, k)) return 1;
                res.pop_back();
                swap(a[i], a[j]), swap(a[i + 1], a[j + 1]);
            }
        }
    }
    return 0;
}
inline void get(int x, int y) { ans.emplace_back(x, y); }
inline void sol(int l, int r) {
    if (r - l + 1 >= 16) {
        get(r - 2, l - 2), get(l + 2, r - 2);
        sol(l + 4, r - 4);
        get(l - 1, r - 5), get(r - 1, l - 1);
    } else {
        a[l - 2] = a[l - 1] = 0, res.clear();
        for (int i = l; i <= r; i++) a[i] = (i & 1 ? 2 : 1);
        if ((r - l + 1) / 2 != 3) dfs(l - 2, r, (r - l + 1) / 2);
        if ((r - l + 1) / 2 == 3) dfs(l - 4, r, (r - l + 1) / 2);
        for (auto i : res) get(i.first, i.second);
    }
}

int main() {
    int n;
    scanf("%d", &n), a = d + N, sol(1, n * 2);
    for (auto i : ans) {
        printf("%d to %d\n", i.first, i.second);
    }
    return 0;
}