题解：P6892 [ICPC 2014 WF] Baggage

· · 题解

构造题。

首先我们知道达到终态需要满足相邻元素相同的对数为 2\times(n-1)，初态为 0 对，操作过程中除第一次操作外（1 对）其余每次最多产生 2 对，所以答案的下界为 n。考虑如何构造达到下界的方案。

先手模样例，以 n=8 为例，按如下步骤置换：

\texttt{\textcolor{blue}{\_\_}BABABABABABABABA}\\ \texttt{\textcolor{red}{AB}BABABABABABAB\textcolor{blue}{\_\_}A}\\ \texttt{ABBA\textcolor{blue}{\_\_}BABABABAB\textcolor{red}{BA}A}\\

此时，中间的 \texttt{\textcolor{blue}{\_\_}BABABABA} 变成了一个类似的子问题，长度为 n-4。我们继续往下递归，直到中间部分有序：

\texttt{ABBA\textcolor{red}{AAAABBBB}\textcolor{blue}{\_\_}BBAA}

继续构造。

\texttt{A\textcolor{blue}{\_\_}AAAAABBBB\textcolor{red}{BB}BBAA}\\ \texttt{A\textcolor{red}{AA}AAAAABBBBBBBB\textcolor{blue}{\_\_}}\\

可以从上例中发现一个更为通用的解法：

\texttt{\_\_BA|BA...BA|BABA}\\ \texttt{\textcolor{red}{AB}BA|BA...BA|B\textcolor{blue}{\_\_}A}\\ \texttt{ABBA|\textcolor{blue}{\_\_}...BA|B\textcolor{red}{BA}A}\\ ...\\ \texttt{ABBA|AAAA...BB\textcolor{blue}{\_\_}|BBAA}\\ \texttt{A\textcolor{blue}{\_\_}A|AAAA...BB\textcolor{red}{BB}|BBAA}\\ \texttt{A\textcolor{red}{AA}A|AAAA...BBBB|BB\textcolor{blue}{\_\_}}\\

考虑 n=3 的情况，模拟可以发现，我们无法在左侧拓展 2 格的条件下完成转移，特判一下即可。

初始时有 2n 个位置，我们每次递归需要隔离出 8 个位置，我们要保证下一次递归序列有效需满足 2n-8\ge8,n\ge8。如果 n \in [3,7]，则 n-4\le3 方案对此序列无效。所以对于 n\ge 8 的序列进行递归操作，3\le n \le 7 的序列直接打表输出方案即可。

void work(int l, int r) {
    if (r - l + 1 == 8) {
        cout << r - 2 << " to " << l - 2 << endl;
        cout << l + 2 << " to " << r - 2 << endl;
        cout << l - 1 << " to " << l + 2 << endl;
        cout << r - 1 << " to " << l - 1 << endl;
    } else if (r - l + 1 == 10) {
        cout << r - 2 << " to " << l - 2 << endl;
        cout << l + 2 << " to " << r - 2 << endl;
        cout << r - 4 << " to " << l + 2 << endl;
        cout << l - 1 << " to " << r - 4 << endl;
        cout << r - 1 << " to " << l - 1 << endl;
    } else if (r - l + 1 == 12) {
        cout << r - 2 << " to " << l - 2 << endl;
        cout << r - 5 << " to " << r - 2 << endl;
        cout << l + 1 << " to " << r - 5 << endl;
        cout << r - 6 << " to " << l + 1 << endl;
        cout << l - 1 << " to " << r - 6 << endl;
        cout << r - 1 << " to " << l - 1 << endl;
    } else if (r - l + 1 == 14) {
        cout << l + 7 << " to " << l - 2 << endl;
        cout << l + 4 << " to " << l + 7 << endl;
        cout << r - 2 << " to " << l + 4 << endl;
        cout << l + 2 << " to " << r - 2 << endl;
        cout << r - 5 << " to " << l + 2 << endl;
        cout << l - 1 << " to " << r - 5 << endl;
        cout << r - 1 << " to " << l - 1 << endl;
    } else {
        cout << r - 2 << " to " << l - 2 << endl;
        cout << l + 2 << " to " << r - 2 << endl;
        work(l + 4, r - 4);
        cout << l - 1 << " to " << r - 5 << endl;
        cout << r - 1 << " to " << l - 1 << endl;
    }
    return;
}
/*====================*/
void Solve() {
    cin >> n;
    if (n == 3) {
        cout << "2 to -1\n" << "5 to 2\n" << "3 to -3\n";
    } else {
        work(1, 2 * n);
    }
    return;
}