Part 1

下面的「最大编号原子」代指链中编号最大的原子。

首先不难发现：$n!>(n-1)!+(n-2)!+\ldots+1!$。证明不给了。

于是原子的运动方式简化为：

• 最大编号原子向远离第二大（次大）编号原子的方向移动。
• 其他原子向远离最大编号原子的方向移动。

由于初始状态（$n$ 个原子）和最终状态（$0/1$ 个原子）中的原子都形成一个区间，我们考虑区间 DP。先看一看，当原子形成一个区间时，是什么情况（以下是一个例子）：

(n = 14)
Start:
(--) -- -- -- 08 04 02 09 14 06 11 05 -- (--)
Steps:
[Stage 1]
(--) -- -- -- 08 04 02 09 14 06 11 05 -- (--)
(--) -- -- 08 04 02 09 14 -- -- 06 11 05 (--)
[Stage 2]
(--) -- 08 04 02 09 14 -- -- -- -- 06 11 (05)
(--) 08 04 02 09 14 -- -- -- -- -- -- 06 (11)
(08) 04 02 09 -- -- 14 -- -- -- -- -- -- (06)
[Stage 3]
(04) 02 09 -- -- -- -- 14 -- -- -- -- -- (--)
(02) 09 -- -- -- -- -- -- 14 -- -- -- -- (--)
(09) -- -- -- -- -- -- -- -- 14 -- -- -- (--)
Stop:
(--) -- -- -- -- -- -- -- -- 14 -- -- -- (--)

不难发现，这个区间被分裂成三段，其中最大编号原子是分界线：

• 最大编号原子左边的所有原子构成一段（08 04 02 09）；
• 最大编号原子单独构成一段（14）；
• 最大编号原子右边的所有原子构成一段（06 11 05）。

这个运动过程也先后分为三个阶段：

• 最大编号原子推动其他原子向两端运动（Stage 1）；
• 原子开始被移出，直至其中一段原子全部被移出（Stage 2）；
• 原子继续被移出，直至其中两段原子全部被移出（Stage 3）。

此外，还有以下特点：

• 同一段中的原子总是成一个区间，从不分开；
• 原子从不会相互越过对方；
• 第一段全部被移出的原子不会是最大编号原子单独构成的那一段；
• 在有限的时间后，其中两段的原子被全部移走，剩下的原子又形成一个区间。

于是我们可以区间 DP 了。定义 $g_{i,j}(2 \le i \le j \le n-1)$ 为：当剩下的原子形成区间 $[i,j]$ 且不能确定任何原子的编号及其相对大小关系时，所经过的最长可能时间（$g_{2,n-1}=0$）。

在状态转移时，分 $10$ 种情况枚举下列维度即可：

• 最大编号原子的位置；（$k$）
• 最大编号原子的运动方向（左 $0$ / 右 $1$）；（$w$）
• 最大编号原子在第二阶段的位移量。（$l$）

这 $10$ 种情况分别是：

• 最大编号原子在最左端；（L）
• 最大编号原子在最右端；（R）
• 最大编号原子在第一阶段中向左运动，第一个被移出的原子位于最大编号原子左侧，最大编号原子左边的那段原子率先被全部移出；（LLL）
• 最大编号原子在第一阶段中向左运动，第一个被移出的原子位于最大编号原子左侧，最大编号原子右边的那段原子率先被全部移出；（LLR）
• 最大编号原子在第一阶段中向左运动，第一个被移出的原子位于最大编号原子右侧，最大编号原子左边的那段原子率先被全部移出；（LRL）
• 最大编号原子在第一阶段中向左运动，第一个被移出的原子位于最大编号原子右侧，最大编号原子右边的那段原子率先被全部移出；（LRR）
• 最大编号原子在第一阶段中向右运动，第一个被移出的原子位于最大编号原子左侧，最大编号原子左边的那段原子率先被全部移出；（RLL）
• 最大编号原子在第一阶段中向右运动，第一个被移出的原子位于最大编号原子左侧，最大编号原子右边的那段原子率先被全部移出；（RLR）
• 最大编号原子在第一阶段中向右运动，第一个被移出的原子位于最大编号原子右侧，最大编号原子左边的那段原子率先被全部移出；（RRL）
• 最大编号原子在第一阶段中向右运动，第一个被移出的原子位于最大编号原子右侧，最大编号原子右边的那段原子率先被全部移出。（RRR）

例如，上面的例子属于 LRR。

至于构造，大体上把握以下要点即可：

• 在一次转移内，总可以让最大编号原子改变至多一次方向来满足 $l$ 的要求；
• 从两边开始从大往小（即从最大编号原子开始）向构造方案（$arr$）中填写原子编号（$lf$）；
• 每次只填写被移除的原子的编号，这样才没有后效性；
• 当不希望某个原子对运动产生影响（即不成为最大 / 次大编号原子）时，可以填写最小编号 （$llf$）；
• 最后可能会有 $1$ 个或 $2$ 个编号漏填，需要补填（$2$ 个编号的顺序任意）。

最终的时间复杂度为 $O(n^4)$，空间复杂度为 $O(n^2)$。

上面的 DP 状态设计沿用了区间 DP 的传统思路。此外，还有另一种思路（写在最后），它与传统思路代码量相当（都是 $10$ 种情况，基本一致），时间和空间复杂度也相同，并且输入 $n=100$ 就可以同时得到 $100$ 个测试点的答案。然而，由于它的常数较大（根据循环次数估计，约为传统思路的 $4$ 倍），并且它是在我写完 std 之后才想到的，所以就没写代码了。感兴趣的可以试一试。

Part 2

std：

#include <bits/stdc++.h>
using namespace std;
const int N = 100 + 12;
int g[N][N], arr[N], ans = -1;
struct REC
{
    int i;
    int j;
    int k;
    int l;
    int w;
};
REC recs[N][N], ansrec;
int main()
{
    int n;
    cin >> n;
    if (n == 1) cout << "1";
    if (n == 2) cout << "1 2";
    if (n <= 2) return 0;
    memset (g, -1, sizeof g);
    arr[1] = n - 1, arr[n] = n;
    recs[2][n - 1] = (REC) {1, n, 0, 0, 0}, g[2][n - 1] = 0;
    for (int len = n - 2; len >= 3; len--)
        for (int i = 2, j = 2 + len - 1; j <= n - 1; i++, j++)
        {
            int c = min (i - 1, n - j);
            if (g[i][j] == -1) continue;
            for (int k = i; k <= j; k++)
            {
                if (k != i && k != j)
                {
                    int d = min (k - 2, n - k - 1);
                    for (int l = -(d - c); l <= d - c; l += 2)
                    {
                        int r = min (d, n - j) - c;
                        if ((l + d - c) / 2 > d - c - r) continue;
                        int p = k - c + l;
                        if (k + 1 + d == n)
                        {
                            if (k - 1 - d - n + p <= 1)
                            {
                                if (ans < g[i][j] + k - 2)
                                {
                                    ans = g[i][j] + k - 2;
                                    ansrec = (REC) {i, j, k, l, 0};
                                }
                            }
                            else if (g[max (2, i - d - n + p)][k - 1 - d - n + p] < g[i][j] + d + n - p)
                            {
                                g[max (2, i - d - n + p)][k - 1 - d - n + p] = g[i][j] + d + n - p;
                                recs[max (2, i - d - n + p)][k - 1 - d - n + p] = (REC) {i, j, k, l, 0};
                            }
                        }
                        else
                        {
                            if (k + 1 + d + p - 1 >= n)
                            {
                                if (ans < g[i][j] + n - k - 1)
                                {
                                    ans = g[i][j] + n - k - 1;
                                    ansrec = (REC) {i, j, k, l, 0};
                                }
                            }
                            else if (g[k + 1 + d + p - 1][min (n - 1, j + d + p - 1)] < g[i][j] + d + p - 1)
                            {
                                g[k + 1 + d + p - 1][min (n - 1, j + d + p - 1)] = g[i][j] + d + p - 1;
                                recs[k + 1 + d + p - 1][min (n - 1, j + d + p - 1)] = (REC) {i, j, k, l, 0};
                            }
                        }
                    }
                    for (int l = -(d - c); l <= d - c; l += 2)
                    {
                        int r = min (d, i - 1) - c;
                        if ((l + d - c) / 2 < r) continue;
                        int p = k + c + l;
                        if (k + 1 + d == n)
                        {
                            if (k - 1 - d - n + p <= 1)
                            {
                                if (ans < g[i][j] + k - 2)
                                {
                                    ans = g[i][j] + k - 2;
                                    ansrec = (REC) {i, j, k, l, 1};
                                }
                            }
                            else if (g[max (2, i - d - n + p)][k - 1 - d - n + p] < g[i][j] + d + n - p)
                            {
                                g[max (2, i - d - n + p)][k - 1 - d - n + p] = g[i][j] + d + n - p;
                                recs[max (2, i - d - n + p)][k - 1 - d - n + p] = (REC) {i, j, k, l, 1};
                            }
                        }
                        else
                        {
                            if (k + 1 + d + p - 1 >= n)
                            {
                                if (ans < g[i][j] + n - k - 1)
                                {
                                    ans = g[i][j] + n - k - 1;
                                    ansrec = (REC) {i, j, k, l, 1};
                                }
                            }
                            else if (g[k + 1 + d + p - 1][min (n - 1, j + d + p - 1)] < g[i][j] + d + p - 1)
                            {
                                g[k + 1 + d + p - 1][min (n - 1, j + d + p - 1)] = g[i][j] + d + p - 1;
                                recs[k + 1 + d + p - 1][min (n - 1, j + d + p - 1)] = (REC) {i, j, k, l, 1};
                            }
                        }
                    }
                }
                if (k == i)
                {
                    if (k + k + 1 - 1 >= n)
                    {
                        if (ans < g[i][j] + n - k - 1)
                        {
                            ans = g[i][j] + n - k - 1;
                            ansrec = (REC) {i, j, k, 0, 0};
                        }
                    }
                    else if (g[k + k + 1 - 1][min (n - 1, j + k - 1)] < g[i][j] + k - 1)
                    {
                        g[k + k + 1 - 1][min (n - 1, j + k - 1)] = g[i][j] + k - 1;
                        recs[k + k + 1 - 1][min (n - 1, j + k - 1)] = (REC) {i, j, k, 0, 0};
                    }
                }
                if (k == j)
                {
                    if (k + k - 1 - n <= 1)
                    {
                        if (ans < g[i][j] + k - 2)
                        {
                            ans = g[i][j] + k - 2;
                            ansrec = (REC) {i, j, k, 0, 1};
                        }
                    }
                    else if (g[max (2, i - n + k)][k + k - 1 - n] < g[i][j] + n - k)
                    {
                        g[max (2, i - n + k)][k + k - 1 - n] = g[i][j] + n - k;
                        recs[max (2, i - n + k)][k + k - 1 - n] = (REC) {i, j, k, 0, 1};
                    }
                }
            }
        }
    for (int i = 2; i <= n - 2; i++)
    {
        if (ans < g[i][i + 1] + min (i - 1, n - i - 1))
        {
            ans = g[i][i + 1] + min (i - 1, n - i - 1);
            ansrec = recs[i][i + 1];
        }
    }
    for (int i = 2; i <= n - 1; i++)
    {
        if (ans < g[i][i])
        {
            ans = g[i][i];
            ansrec = recs[i][i];
        }
    }
    stack <REC> st;
    REC cur = ansrec;
    while (cur.k)
    {
        st.push(cur);
        cur = recs[cur.i][cur.j];
    }
    int cl = 2, cr = n - 1, lf = n - 2, llf = 1;
    while (!st.empty())
    {
        int nc = 0;
        cur = st.top();
        st.pop();
        if (cur.k == cur.i)
        {
            arr[cl] = lf, cl++, lf--;
            if (cur.k + cur.k + 1 - 1 < n) nc = min (n - 1, cur.j + cur.k - 1) - (cur.k + cur.k + 1 - 1) + 1;
            for (int i = cl, j = 1; i <= cr; i++, j++)
                if (j > nc) arr[i] = lf, lf--;
            cr = cl + nc - 1;
            continue;
        }
        if (cur.k == cur.j)
        {
            arr[cr] = lf, cr--, lf--;
            if (cur.k + cur.k - 1 - n) nc = cur.k + cur.k - 1 - n - max (2, cur.i - n + cur.k) + 1;
            for (int i = cr, j = 1; i >= cl; i--, j++)
                if (j > nc) arr[i] = lf, lf--;
            cl = cr - nc + 1;
            continue;
        }
        int d = min (cur.k - 2, n - cur.k - 1);
        int c = min (cur.i - 1, n - cur.j);
        int rt = (cur.l + d - c) / 2;
        int lt = d - c - rt;
        int ck = cl + cur.k - cur.i;
        int p;
        arr[ck] = lf, lf--;
        if (cur.w == 0)
        {
            p = cur.k - c + cur.l;
            if (cur.i - 1 < n - cur.j && cur.k - 2 < n - cur.k - 1)
            {
                if (cur.k + 1 + d + p - 1 < n) nc = min (n - 1, cur.j + d + p - 1) - (cur.k + 1 + d + p - 1) + 1;
                for (int i = ck + 1, j = 1; i <= cr; i++, j++)
                    if (j > nc)
                    {
                        if (cur.k + j + c <= n - lt - 1) arr[i] = llf, llf++;
                        else arr[i] = lf, lf--;
                    }
                for (int i = ck - 1; i >= cl; i--)
                {
                    if (rt) arr[i] = lf, lf--;
                    else arr[i] = llf, llf++;
                }
                cl = ck + 1, cr = cl + nc - 1;
            }
            if (cur.i - 1 < n - cur.j && cur.k - 2 >= n - cur.k - 1)
            {
                for (int i = d - c, j = 1; i >= lt + 2; i--, j++)
                    arr[ck + j] = llf, llf++;
                for (int j = d - c + 1 - lt; ck + j <= cr; j++)
                    arr[ck + j] = lf, lf--;
                for (int i = 0; i <= d - c; i++)
                    arr[cl] = lf, cl++, lf--;
                cr = ck - 1;
                if (cur.k - 1 - d - n + p > 1) nc = cur.k - 1 - d - n + p - max (2, cur.i - d - n + p) + 1;
                for (int i = cr, j = 1; i >= cl; i--, j++)
                    if (j > nc) arr[i] = lf, lf--;
                cl = cr - nc + 1;
            }
            if (cur.i - 1 >= n - cur.j && cur.k - 2 < n - cur.k - 1)
            {
                for (int i = 0; i <= lt; i++)
                    arr[cr] = lf, cr--, lf--;
                for (int i = lt + 1; i <= d - c; i++)
                    arr[cr] = llf, cr--, llf++;
                for (int i = ck - 1; i >= cl; i--)
                    arr[i] = lf, lf--;
                cl = ck + 1;
                if (cur.k + 1 + d + p - 1 < n) nc = min (n - 1, cur.j + d + p - 1) - (cur.k + 1 + d + p - 1) + 1;
                for (int i = cl, j = 1; i <= cr; i++, j++)
                    if (j > nc) arr[i] = lf, lf--;
                cr = cl + nc - 1;
            }
            if (cur.i - 1 >= n - cur.j && cur.k - 2 >= n - cur.k - 1)
            {
                for (int i = 0; i <= lt; i++)
                    arr[cr] = lf, cr--, lf--;
                for (int i = lt + 1; i <= d - c; i++)
                    arr[cr] = llf, cr--, llf++;
                cr = ck - 1;
                if (cur.k - 1 - d - n + p > 1) nc = cur.k - 1 - d - n + p - max (2, cur.i - d - n + p) + 1;
                for (int i = cr, j = 1; i >= cl; i--, j++)
                    if (j > nc) arr[i] = lf, lf--;
                cl = cr - nc + 1;
            }
        }
        if (cur.w == 1)
        {
            p = cur.k + c + cur.l;
            if (cur.i - 1 < n - cur.j && cur.k - 2 < n - cur.k - 1)
            {
                for (int i = 0; i <= rt; i++)
                    arr[cl] = lf, cl++, lf--;
                for (int i = rt + 1; i <= d - c; i++)
                    arr[cl] = llf, cl++, llf++;
                cl = ck + 1;
                if (cur.k + 1 + d + p - 1 < n) nc = min (n - 1, cur.j + d + p - 1) - (cur.k + 1 + d + p - 1) + 1;
                for (int i = cl, j = 1; i <= cr; i++, j++)
                    if (j > nc) arr[i] = lf, lf--;
                cr = cl + nc - 1;
            }
            if (cur.i - 1 < n - cur.j && cur.k - 2 >= n - cur.k - 1)
            {
                for (int i = 0; i <= rt; i++)
                    arr[cl] = lf, cl++, lf--;
                for (int i = ck + 1; i <= cr; i++)
                    arr[i] = lf, lf--;
                for (int i = rt + 1; i <= d - c; i++)
                    arr[cl] = llf, cl++, llf++;
                cr = ck - 1;
                if (cur.k - 1 - d - n + p > 1) nc = cur.k - 1 - d - n + p - max (2, cur.i - d - n + p) + 1;
                for (int i = cr, j = 1; i >= cl; i--, j++)
                    if (j > nc) arr[i] = lf, lf--;
                cl = cr - nc + 1;
            }
            if (cur.i - 1 >= n - cur.j && cur.k - 2 < n - cur.k - 1)
            {
                for (int i = d - c, j = 1; i >= rt + 2; i--, j++)
                    arr[ck - j] = llf, llf++;
                for (int j = d - c + 1 - rt; ck - j >= cl; j++)
                    arr[ck - j] = lf, lf--;
                for (int i = 0; i <= d - c; i++)
                    arr[cr] = lf, cr--, lf--;
                cl = ck + 1;
                if (cur.k + 1 + d + p - 1 < n) nc = min (n - 1, cur.j + d + p - 1) - (cur.k + 1 + d + p - 1) + 1;
                for (int i = cl, j = 1; i <= cr; i++, j++)
                    if (j > nc) arr[i] = lf, lf--;
                cr = cl + nc - 1;
            }
            if (cur.i - 1 >= n - cur.j && cur.k - 2 >= n - cur.k - 1)
            {
                if (cur.k - 1 - d - n + p > 1) nc = cur.k - 1 - d - n + p - max (2, cur.i - d - n + p) + 1;
                for (int i = ck - 1, j = 1; i >= cl; i--, j++)
                    if (j > nc)
                    {
                        if (cur.k - j - c >= rt + 2) arr[i] = llf, llf++;
                        else arr[i] = lf, lf--;
                    }
                for (int i = ck + 1; i <= cr; i++)
                {
                    if (lt) arr[i] = lf, lf--;
                    else arr[i] = llf, llf++;
                }
                cr = ck - 1, cl = cr - nc + 1;
            }
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if (!arr[i]) arr[i] = llf, llf++;
        cout << arr[i] << ' ';
    }
    return 0;
}

Part 3

放一个你们估计喜闻乐见的东西！

#include <bits/stdc++.h>
using namespace std;
const int N = 100 + 12;
const string ans[N] =
{
"",
"1",
"1 2",
"2 1 3",
"3 1 2 4",
"4 1 3 2 5",
"5 2 4 1 3 6",
"6 4 2 3 1 5 7",
"7 5 3 4 2 1 6 8",
"8 6 5 3 1 2 4 7 9",
"9 7 6 3 1 4 2 5 8 10",
"10 9 6 3 1 2 5 4 7 8 11",
"11 9 8 1 6 3 4 2 5 7 10 12",
"12 10 9 6 7 2 3 1 5 4 8 11 13",
"13 12 9 5 6 2 3 1 4 8 7 10 11 14",
"14 12 11 8 9 5 2 3 1 4 7 6 10 13 15",
"15 13 12 9 10 6 3 4 2 1 5 8 7 11 14 16",
"16 15 12 8 9 6 3 4 2 5 1 7 11 10 13 14 17",
"17 15 14 11 12 8 1 6 3 4 2 5 7 10 9 13 16 18",
"18 16 15 12 13 9 7 5 3 2 4 1 6 8 11 10 14 17 19",
"19 18 15 11 12 9 7 2 3 1 6 4 5 8 10 14 13 16 17 20",
"20 19 16 12 13 10 8 4 2 3 1 6 5 7 9 11 15 14 17 18 21",
"21 19 18 15 16 12 10 8 6 7 2 3 1 5 4 9 11 14 13 17 20 22",
"22 20 19 16 17 13 11 9 7 8 2 3 1 6 4 5 10 12 15 14 18 21 23",
"23 22 19 15 16 13 11 6 7 4 2 3 1 5 9 8 10 12 14 18 17 20 21 24",
"24 22 21 18 19 15 13 11 9 10 6 2 3 1 5 4 8 7 12 14 17 16 20 23 25",
"25 24 21 17 18 15 13 8 9 5 6 2 3 1 4 7 11 10 12 14 16 20 19 22 23 26",
"26 24 23 20 21 17 15 13 11 12 8 5 2 3 1 4 7 6 10 9 14 16 19 18 22 25 27",
"27 25 24 21 22 18 16 14 12 13 9 7 3 4 2 6 5 8 11 1 10 15 17 20 19 23 26 28",
"28 26 25 22 23 19 17 15 13 14 10 7 5 3 1 2 4 6 9 8 12 11 16 18 21 20 24 27 29",
"29 27 26 23 24 20 18 16 14 15 11 8 6 4 2 3 1 5 7 10 9 13 12 17 19 22 21 25 28 30",
"30 29 26 22 23 20 18 13 14 10 11 8 6 3 1 2 5 4 7 9 12 16 15 17 19 21 25 24 27 28 31",
"31 30 27 23 24 21 19 14 15 11 12 9 7 4 2 3 1 6 5 8 10 13 17 16 18 20 22 26 25 28 29 32",
"32 30 29 26 27 23 21 19 17 18 14 11 9 6 7 3 1 2 5 4 8 10 13 12 16 15 20 22 25 24 28 31 33",
"33 31 30 27 28 24 22 20 18 19 15 12 10 7 8 3 1 4 2 6 5 9 11 14 13 17 16 21 23 26 25 29 32 34",
"34 32 31 28 29 25 23 21 19 20 16 13 11 8 9 6 4 2 3 5 7 10 1 12 15 14 18 17 22 24 27 26 30 33 35",
"35 34 31 27 28 25 23 18 19 15 16 13 11 7 1 8 4 2 3 6 5 10 9 12 14 17 21 20 22 24 26 30 29 32 33 36",
"36 35 32 28 29 26 24 19 20 16 17 14 12 10 6 7 4 2 3 5 9 8 11 13 1 15 18 22 21 23 25 27 31 30 33 34 37",
"37 35 34 31 32 28 26 24 22 23 19 16 14 11 12 7 8 4 2 3 6 5 10 1 9 13 15 18 17 21 20 25 27 30 29 33 36 38",
"38 36 35 32 33 29 27 25 23 24 20 17 1 15 13 10 11 7 3 4 2 6 5 9 8 12 14 16 19 18 22 21 26 28 31 30 34 37 39",
"39 38 35 31 32 29 27 22 23 19 20 17 15 13 9 10 6 7 3 4 2 5 8 12 11 14 16 1 18 21 25 24 26 28 30 34 33 36 37 40",
"40 38 37 34 35 31 29 27 25 26 22 19 1 17 15 12 13 8 6 4 2 3 5 7 11 9 10 14 16 18 21 20 24 23 28 30 33 32 36 39 41",
"41 40 37 33 34 31 29 24 25 21 22 19 1 17 14 12 9 7 8 3 4 2 6 5 11 10 13 16 15 18 20 23 27 26 28 30 32 36 35 38 39 42",
"42 41 38 34 35 32 30 25 26 22 23 20 18 16 12 13 9 10 7 4 5 2 3 6 8 11 15 14 17 19 1 21 24 28 27 29 31 33 37 36 39 40 43",
"43 42 39 35 36 33 31 26 27 23 24 21 1 19 16 14 11 9 10 6 3 4 2 5 8 7 13 12 15 18 17 20 22 25 29 28 30 32 34 38 37 40 41 44",
"44 42 41 38 39 35 33 31 29 30 26 23 1 21 19 16 17 13 10 8 4 5 3 7 6 9 2 12 11 15 14 18 20 22 25 24 28 27 32 34 37 36 40 43 45",
"45 43 42 39 40 36 34 32 30 31 27 24 22 19 20 15 16 9 10 6 7 2 3 1 5 4 8 12 11 14 13 18 17 21 23 26 25 29 28 33 35 38 37 41 44 46",
"46 45 42 38 39 36 34 29 30 26 27 24 22 18 19 14 15 12 13 9 5 6 2 3 1 4 8 7 11 10 17 16 21 20 23 25 28 32 31 33 35 37 41 40 43 44 47",
"47 46 43 39 40 37 35 30 31 27 28 25 23 21 17 18 14 15 12 10 8 9 3 4 2 6 5 7 11 13 16 20 19 22 24 1 26 29 33 32 34 36 38 42 41 44 45 48",
"48 46 45 42 43 39 37 35 33 34 30 27 1 25 23 20 21 17 14 12 8 6 7 3 4 2 5 10 9 11 13 16 15 19 18 22 24 26 29 28 32 31 36 38 41 40 44 47 49",
"49 48 45 41 42 39 37 32 33 29 30 27 25 23 19 20 16 17 14 12 10 11 6 3 4 2 5 8 7 9 13 15 18 22 21 24 26 1 28 31 35 34 36 38 40 44 43 46 47 50",
"50 48 47 44 45 41 39 37 35 36 32 29 1 27 25 22 23 19 16 14 11 9 7 8 4 5 3 6 10 13 12 15 2 18 17 21 20 24 26 28 31 30 34 33 38 40 43 42 46 49 51",
"51 49 48 45 46 42 40 38 36 37 33 30 1 28 26 23 24 20 17 15 11 6 7 3 4 2 5 9 8 10 14 12 13 16 19 18 22 21 25 27 29 32 31 35 34 39 41 44 43 47 50 52",
"52 50 49 46 47 43 41 39 37 38 34 31 1 29 27 24 25 21 18 16 13 11 9 10 7 4 5 3 6 8 12 15 14 17 2 20 19 23 22 26 28 30 33 32 36 35 40 42 45 44 48 51 53",
"53 51 50 47 48 44 42 40 38 39 35 32 1 30 28 25 26 22 19 2 17 13 10 11 7 8 5 3 4 6 9 12 15 14 16 18 21 20 24 23 27 29 31 34 33 37 36 41 43 46 45 49 52 54",
"54 52 51 48 49 45 43 41 39 40 36 33 1 31 29 26 27 23 20 18 14 9 10 7 5 3 4 2 6 8 12 11 13 17 15 16 19 22 21 25 24 28 30 32 35 34 38 37 42 44 47 46 50 53 55",
"55 53 52 49 50 46 44 42 40 41 37 34 1 32 30 27 28 24 21 19 16 14 12 13 3 10 8 5 6 4 7 9 11 15 18 17 20 2 23 22 26 25 29 31 33 36 35 39 38 43 45 48 47 51 54 56",
"56 54 53 50 51 47 45 43 41 42 38 35 1 33 31 28 29 25 22 20 16 11 12 9 6 7 3 4 2 5 8 10 14 13 15 19 17 18 21 24 23 27 26 30 32 34 37 36 40 39 44 46 49 48 52 55 57",
"57 56 53 49 50 47 45 40 41 37 38 35 33 31 27 28 24 25 22 19 18 20 16 14 15 11 9 6 3 4 2 5 8 7 10 13 12 17 21 23 26 30 29 32 34 1 36 39 43 42 44 46 48 52 51 54 55 58",
"58 56 55 52 53 49 47 45 43 44 40 37 1 35 33 30 31 27 24 22 18 13 14 11 8 9 6 3 4 2 5 7 10 12 16 15 17 21 19 20 23 26 25 29 28 32 34 36 39 38 42 41 46 48 51 50 54 57 59",
"59 58 55 51 52 49 47 42 43 39 40 37 35 33 29 30 26 27 24 21 20 22 18 16 17 13 11 8 6 3 4 2 5 7 10 9 12 15 14 19 23 25 28 32 31 34 36 1 38 41 45 44 46 48 50 54 53 56 57 60",
"60 58 57 54 55 51 49 47 45 46 42 39 37 34 35 30 31 24 25 21 22 17 14 15 10 11 5 6 3 1 2 4 8 7 9 13 12 16 20 18 19 23 27 26 29 28 33 32 36 38 41 40 44 43 48 50 53 52 56 59 61",
"61 59 58 55 56 52 50 48 46 47 43 40 1 38 36 33 34 30 27 25 21 16 17 14 11 12 2 9 7 4 5 3 6 8 10 13 15 19 18 20 24 22 23 26 29 28 32 31 35 37 39 42 41 45 44 49 51 54 53 57 60 62",
"62 60 59 56 57 53 51 49 47 48 44 41 1 39 37 34 35 31 28 26 22 17 18 15 12 13 10 8 5 6 3 4 2 7 9 11 14 16 20 19 21 25 23 24 27 30 29 33 32 36 38 40 43 42 46 45 50 52 55 54 58 61 63",
"63 62 59 55 56 53 51 46 47 43 44 41 39 37 33 34 30 31 28 25 24 26 22 20 21 17 15 12 10 8 4 2 3 6 5 7 9 11 14 13 16 19 18 23 27 29 32 36 35 38 40 1 42 45 49 48 50 52 54 58 57 60 61 64",
"64 63 60 56 57 54 52 47 48 44 45 42 40 38 34 35 31 32 2 29 26 27 24 20 18 16 14 10 8 5 6 4 7 9 12 11 13 15 17 19 3 22 21 23 25 28 30 33 37 36 39 41 1 43 46 50 49 51 53 55 59 58 61 62 65",
"65 63 62 59 60 56 54 52 50 51 47 44 42 39 40 35 36 29 30 26 27 22 19 20 15 16 10 11 7 8 2 3 1 5 4 6 9 13 12 14 18 17 21 25 23 24 28 32 31 34 33 38 37 41 43 46 45 49 48 53 55 58 57 61 64 66",
"66 64 63 60 61 57 55 53 51 52 48 45 1 43 41 38 39 35 32 30 26 21 22 19 16 17 14 12 10 8 7 9 3 4 2 6 5 11 13 15 18 20 24 23 25 29 27 28 31 34 33 37 36 40 42 44 47 46 50 49 54 56 59 58 62 65 67",
"67 66 63 59 60 57 55 50 51 47 48 45 43 41 37 38 34 35 2 32 29 30 27 23 21 19 17 13 11 9 6 7 4 5 8 10 12 15 14 16 18 20 22 3 25 24 26 28 31 33 36 40 39 42 44 1 46 49 53 52 54 56 58 62 61 64 65 68",
"68 66 65 62 63 59 57 55 53 54 50 47 1 45 43 40 41 37 34 32 28 23 24 21 18 19 16 2 14 11 12 8 9 6 4 5 3 7 10 13 15 17 20 22 26 25 27 31 29 30 33 36 35 39 38 42 44 46 49 48 52 51 56 58 61 60 64 67 69",
"69 68 65 61 62 59 57 52 53 49 50 47 45 43 39 40 36 37 34 31 30 32 28 26 27 23 21 18 16 14 12 7 8 5 3 4 6 10 9 11 13 15 17 2 20 19 22 25 24 29 33 35 38 42 41 44 46 1 48 51 55 54 56 58 60 64 63 66 67 70",
"70 69 66 62 63 60 58 53 54 50 51 48 46 44 40 41 37 38 35 32 31 33 29 27 28 24 22 19 17 15 12 9 6 4 5 3 8 7 11 10 14 13 16 2 18 21 20 23 26 25 30 34 36 39 43 42 45 47 1 49 52 56 55 57 59 61 65 64 67 68 71",
"71 69 68 65 66 62 60 58 56 57 53 50 1 48 46 43 44 40 37 35 31 26 27 24 21 22 2 19 17 15 13 11 12 8 4 5 3 7 6 10 9 14 16 18 20 23 25 29 28 30 34 32 33 36 39 38 42 41 45 47 49 52 51 55 54 59 61 64 63 67 70 72",
"72 70 69 66 67 63 61 59 57 58 54 51 49 46 47 42 43 36 37 33 34 29 26 27 22 23 17 18 14 15 8 9 5 3 1 2 4 7 6 12 10 11 13 16 20 19 21 25 24 28 32 30 31 35 39 38 41 40 45 44 48 50 53 52 56 55 60 62 65 64 68 71 73",
"73 72 69 65 66 63 61 56 57 53 54 51 49 47 43 44 40 41 2 38 35 36 33 29 27 25 23 19 17 4 15 12 13 10 8 6 7 5 9 11 14 16 18 21 20 22 24 26 28 3 31 30 32 34 37 39 42 46 45 48 50 1 52 55 59 58 60 62 64 68 67 70 71 74",
"74 72 71 68 69 65 63 61 59 60 56 53 1 51 49 46 47 43 40 38 34 29 30 27 24 25 2 22 20 18 16 14 15 3 11 8 5 6 4 7 10 9 13 12 17 19 21 23 26 28 32 31 33 37 35 36 39 42 41 45 44 48 50 52 55 54 58 57 62 64 67 66 70 73 75",
"75 74 71 67 68 65 63 58 59 55 56 53 51 49 45 46 42 43 40 37 36 38 34 32 33 29 27 24 22 20 15 16 11 8 9 4 5 3 7 6 10 13 12 14 2 18 17 19 21 23 26 25 28 31 30 35 39 41 44 48 47 50 52 1 54 57 61 60 62 64 66 70 69 72 73 76",
"76 74 73 70 71 67 65 63 61 62 58 55 1 53 51 48 49 45 42 40 36 31 32 29 26 27 2 24 22 20 18 16 17 3 13 10 8 5 6 4 7 9 12 11 15 14 19 21 23 25 28 30 34 33 35 39 37 38 41 44 43 47 46 50 52 54 57 56 60 59 64 66 69 68 72 75 77",
"77 76 73 69 70 67 65 60 61 57 58 55 53 51 47 48 44 45 42 39 38 40 36 34 35 31 29 26 24 22 17 18 13 10 11 7 5 3 4 6 9 8 12 15 14 16 2 20 19 21 23 25 28 27 30 33 32 37 41 43 46 50 49 52 54 1 56 59 63 62 64 66 68 72 71 74 75 78",
"78 76 75 72 73 69 67 65 63 64 60 57 1 55 53 50 51 47 44 42 39 37 35 36 3 33 31 29 27 25 26 23 21 19 16 14 11 6 7 5 9 8 10 13 12 15 18 17 20 4 22 24 28 30 32 34 38 41 40 43 2 46 45 49 48 52 54 56 59 58 62 61 66 68 71 70 74 77 79",
"79 77 76 73 74 70 68 66 64 65 61 58 1 56 54 51 52 48 45 43 39 34 35 32 29 30 2 27 25 23 21 19 20 3 16 13 11 9 7 5 6 4 8 10 12 15 14 18 17 22 24 26 28 31 33 37 36 38 42 40 41 44 47 46 50 49 53 55 57 60 59 63 62 67 69 72 71 75 78 80",
"80 78 77 74 75 71 69 67 65 66 62 59 1 57 55 52 53 49 46 44 40 35 36 33 30 31 28 26 24 22 23 2 19 17 18 15 11 12 9 6 4 5 3 8 7 10 14 13 16 21 20 25 27 29 32 34 38 37 39 43 41 42 45 48 47 51 50 54 56 58 61 60 64 63 68 70 73 72 76 79 81",
"81 79 78 75 76 72 70 68 66 67 63 60 1 58 56 53 54 50 47 45 41 36 37 34 31 32 2 29 27 25 23 21 22 3 18 15 13 11 8 9 6 4 5 7 10 12 14 17 16 20 19 24 26 28 30 33 35 39 38 40 44 42 43 46 49 48 52 51 55 57 59 62 61 65 64 69 71 74 73 77 80 82",
"82 81 78 74 75 72 70 65 66 62 63 60 58 56 52 53 49 50 47 44 43 45 41 39 40 36 34 31 29 27 25 20 21 17 18 15 10 11 8 5 6 4 7 9 13 12 14 16 3 19 23 22 24 26 28 30 2 33 32 35 38 37 42 46 48 51 55 54 57 59 1 61 64 68 67 69 71 73 77 76 79 80 83",
"83 82 79 75 76 73 71 66 67 63 64 61 59 57 53 54 50 51 48 45 44 46 42 40 41 37 35 32 30 28 26 21 22 18 19 16 14 12 9 6 4 5 8 7 11 10 13 15 17 20 3 24 23 25 27 29 31 2 34 33 36 39 38 43 47 49 52 56 55 58 60 1 62 65 69 68 70 72 74 78 77 80 81 84",
"84 82 81 78 79 75 73 71 69 70 66 63 1 61 59 56 57 53 50 48 44 39 40 37 34 35 2 32 30 28 26 24 25 3 21 18 4 16 14 12 9 10 6 7 5 8 11 13 15 17 20 19 23 22 27 29 31 33 36 38 42 41 43 47 45 46 49 52 51 55 54 58 60 62 65 64 68 67 72 74 77 76 80 83 85",
"85 83 82 79 80 76 74 72 70 71 67 64 1 62 60 57 58 54 51 49 45 40 41 38 35 36 2 33 31 29 27 25 26 3 22 19 17 15 12 13 9 10 5 6 4 8 7 11 14 16 18 21 20 24 23 28 30 32 34 37 39 43 42 44 48 46 47 50 53 52 56 55 59 61 63 66 65 69 68 73 75 78 77 81 84 86",
"86 85 82 78 79 76 74 69 70 66 67 64 62 60 56 57 53 54 51 48 47 49 45 43 44 40 38 35 33 31 29 24 25 21 22 19 17 15 12 8 9 5 6 4 7 11 10 14 13 16 18 20 23 3 27 26 28 30 32 34 2 37 36 39 42 41 46 50 52 55 59 58 61 63 1 65 68 72 71 73 75 77 81 80 83 84 87",
"87 85 84 81 82 78 76 74 72 73 69 66 1 64 62 59 60 56 53 51 47 42 43 40 37 38 2 35 33 31 29 27 28 3 24 21 19 17 14 15 11 12 8 6 4 5 7 10 9 13 16 18 20 23 22 26 25 30 32 34 36 39 41 45 44 46 50 48 49 52 55 54 58 57 61 63 65 68 67 71 70 75 77 80 79 83 86 88",
"88 86 85 82 83 79 77 75 73 74 70 67 1 65 63 60 61 57 54 52 48 43 44 41 38 39 2 36 34 32 30 28 29 3 25 22 20 18 15 16 12 13 9 7 5 6 4 8 11 10 14 17 19 21 24 23 27 26 31 33 35 37 40 42 46 45 47 51 49 50 53 56 55 59 58 62 64 66 69 68 72 71 76 78 81 80 84 87 89",
"89 88 85 81 82 79 77 72 73 69 70 67 65 63 59 60 56 57 54 51 50 52 48 46 47 43 41 38 36 34 32 27 28 24 25 22 17 18 15 13 10 11 8 6 4 5 7 9 12 14 16 20 19 21 23 3 26 30 29 31 33 35 37 2 40 39 42 45 44 49 53 55 58 62 61 64 66 1 68 71 75 74 76 78 80 84 83 86 87 90",
"90 88 87 84 85 81 79 77 75 76 72 69 1 67 65 62 63 59 56 54 50 45 46 43 40 41 2 38 36 34 32 30 31 3 27 24 22 20 17 18 14 15 11 8 9 5 6 4 7 10 13 12 16 19 21 23 26 25 29 28 33 35 37 39 42 44 48 47 49 53 51 52 55 58 57 61 60 64 66 68 71 70 74 73 78 80 83 82 86 89 91",
"91 90 87 83 84 81 79 74 75 71 72 69 67 65 61 62 58 59 56 53 52 54 50 48 49 45 43 40 38 36 34 29 30 26 27 24 22 20 17 13 14 11 8 5 6 4 7 10 9 12 16 15 19 18 21 23 25 28 3 32 31 33 35 37 39 2 42 41 44 47 46 51 55 57 60 64 63 66 68 1 70 73 77 76 78 80 82 86 85 88 89 92",
"92 90 89 86 87 83 81 79 77 78 74 71 1 69 67 64 65 61 58 56 52 47 48 45 42 43 2 40 38 36 34 32 33 3 29 26 24 22 19 20 16 17 13 10 11 8 5 6 4 7 9 12 15 14 18 21 23 25 28 27 31 30 35 37 39 41 44 46 50 49 51 55 53 54 57 60 59 63 62 66 68 70 73 72 76 75 80 82 85 84 88 91 93",
"93 92 89 85 86 83 81 76 77 73 74 71 69 67 63 64 60 61 58 55 54 56 52 50 51 47 45 42 40 38 36 31 32 28 29 26 24 22 19 15 16 13 10 8 6 4 5 7 9 12 11 14 18 17 21 20 23 25 27 30 3 34 33 35 37 39 41 2 44 43 46 49 48 53 57 59 62 66 65 68 70 1 72 75 79 78 80 82 84 88 87 90 91 94",
"94 93 90 86 87 84 82 77 78 74 75 72 70 68 64 65 61 62 59 56 55 57 53 51 52 48 46 43 41 39 37 32 33 29 30 27 25 23 20 16 17 14 11 9 7 5 6 4 8 10 13 12 15 19 18 22 21 24 26 28 31 3 35 34 36 38 40 42 2 45 44 47 50 49 54 58 60 63 67 66 69 71 1 73 76 80 79 81 83 85 89 88 91 92 95",
"95 93 92 89 90 86 84 82 80 81 77 74 1 72 70 67 68 64 61 59 55 50 51 48 45 46 2 43 41 39 37 35 36 3 32 29 27 25 22 23 19 20 16 13 14 11 9 5 6 4 8 7 10 12 15 18 17 21 24 26 28 31 30 34 33 38 40 42 44 47 49 53 52 54 58 56 57 60 63 62 66 65 69 71 73 76 75 79 78 83 85 88 87 91 94 96",
"96 95 92 88 89 86 84 79 80 76 77 74 72 70 66 67 63 64 61 58 57 59 55 53 54 50 48 45 43 41 39 34 35 31 32 29 27 25 22 18 19 16 13 11 8 9 5 6 4 7 10 12 15 14 17 21 20 24 23 26 28 30 33 3 37 36 38 40 42 44 2 47 46 49 52 51 56 60 62 65 69 68 71 73 1 75 78 82 81 83 85 87 91 90 93 94 97",
"97 95 94 91 92 88 86 84 82 83 79 76 1 74 72 69 70 66 63 61 57 52 53 50 47 48 2 45 43 41 39 37 38 3 34 31 29 27 24 25 21 22 18 15 16 13 11 8 6 4 5 7 10 9 12 14 17 20 19 23 26 28 30 33 32 36 35 40 42 44 46 49 51 55 54 56 60 58 59 62 65 64 68 67 71 73 75 78 77 81 80 85 87 90 89 93 96 98",
"98 96 95 92 93 89 87 85 83 84 80 77 1 75 73 70 71 67 64 62 58 53 54 51 48 49 2 46 44 42 40 38 39 3 35 32 30 28 25 26 22 23 19 16 17 14 12 9 7 5 6 4 8 11 10 13 15 18 21 20 24 27 29 31 34 33 37 36 41 43 45 47 50 52 56 55 57 61 59 60 63 66 65 69 68 72 74 76 79 78 82 81 86 88 91 90 94 97 99",
"99 97 96 93 94 90 88 86 84 85 81 78 1 76 74 71 72 68 65 63 59 54 55 52 49 50 2 47 45 43 41 39 40 3 36 33 31 29 26 27 23 24 20 17 18 15 13 9 10 6 7 5 8 12 11 14 4 16 19 22 21 25 28 30 32 35 34 38 37 42 44 46 48 51 53 57 56 58 62 60 61 64 67 66 70 69 73 75 77 80 79 83 82 87 89 92 91 95 98 100"
};
int main()
{
    int n;
    cin >> n;
    cout << ans[n];
    return 0;
}

Part 4

接下来给出验题人 irris 所写的 SPJ：

#include "testlib.h"
#include <bits/stdc++.h>
#define MAXN 111
int pa[MAXN], ja[MAXN];
bool perm[MAXN];
bool checkPerm(int *a, int N) {
    memset (perm, 0, sizeof perm);
    for (int i = 1; i <= N; ++i)
        perm[a[i]] = true;
    for (int i = 1; i <= N; ++i)
        if (!perm[i]) return false;
    return true;
}
int getCnt(int *a, int N) {
    int cnt = 0;
    while (true) {
        a[1] = a[N] = 0;
        int m1 = 0, p1 = 0, m2 = 0, p2 = 0;
        for (int i = 1; i <= N; ++i)
            if (a[i] > m1) m1 = a[i], p1 = i;
        for (int i = 1; i <= N; ++i)
            if (a[i] > m2 && i != p1) m2 = a[i], p2 = i;
        if (p1 == 0 || p2 == 0) break;
        for (int i = 1; i < p1; ++i) a[i] = a[i + 1];
        for (int i = N - 1; i > p1; --i) a[i + 1] = a[i];
        a[p1 - 1] = a[p1 + 1] = 0;
        a[p1 < p2 ? p1 - 1 : p1 + 1] = a[p1], a[p1] = 0;
        int lf = 0;
        for (int i = 1; i <= N; ++i) lf += (a[i] != 0);
        if (lf <= 1) break;
        ++cnt;
    }
    return cnt;
}
int main(int argc, char* argv[]) {
    registerTestlibCmd(argc, argv);
    int N = inf.readInt();
    for (int i = 1; i <= N; ++i) ja[i] = ans.readInt(1, N);
    for (int i = 1; i <= N; ++i) pa[i] = ouf.readInt(1, N);
    if (!checkPerm(ja, N)) quitf(_fail, "The jury breaks down!");
    if (!checkPerm(pa, N)) quitf(_wa, "Your answer is invalid!");
    int J = getCnt(ja, N), P = getCnt(pa, N);
    if (P > J) quitf(_fail, "You beat the jury! (%02d\'%02d\" / %02d\'%02d\")", P / 60, P % 60, J / 60, J % 60);
    if (P == J) quitf(_ok, "Congratulations! (%02d\'%02d\" / %02d\'%02d\")", P / 60, P % 60, J / 60, J % 60);
    quitf(_wa, "Your answer is worse than the jury! (%02d\'%02d\" / %02d\'%02d\")", P / 60, P % 60, J / 60, J % 60);
}

这个 SPJ 是 $O(n^3)$ 的。感兴趣的可以帮我们写一写 $\sout{O(n)}$ 的 SPJ，做法与 std 类似。

Part 5

从这里开始，忽略做法在 $n \to \infty$ 时的正确性，但经过验证在 $n=200,300,400,500,600$ 时也成立。

你可能会认为，std 代码很长（326 Lines / 13.22 KB），时间复杂度也很高，因此这是 trash 题。

但实际上，DP 找出的最优解只有以下 $6$ 种情况：

• $k=i,l=0$；（L）
• $k=i+1,l=-1$；（LLL）
• $k=i+1,l=1$；（LRR）
• $k=j,l=0$；（R）
• $k=j-1,l=-1$；（RLL）
• $k=j-1,l=1$。（RRR）

其中，即使只考虑 L 和 R 两种情况（贪心），也能得到 $35$ 分。

用以上情况代替 $k$ 和 $l$ 的循环，时间复杂度就变成了 $O(n^2)$。

此外，由于前 $3$ 种情况还和后 $3$ 种情况对称，代码量可以减少 $70\%$。如果再进行一番合理的压缩（例如把所有的空格换成 Tab），代码量甚至可以减少 $80\%$！

Part 6

下面有两句题外话：

• 出题人偶然发现，如果将最优解的瘫痪用时（$ans$）记为函数 $f(n)$，那么 $f(n)$ 有一个优秀的近似拟合：$f(n)\approx \dfrac{n^2}{7}$。例如，$f(50)=340\approx\dfrac{50^2}{7}=357$，$f(100)=1390\approx \dfrac{100^2}{7}=1429$。
• 我们可以重新定义 $g_{i,j}$ 中的 $i,j$ 为左端和右端的空结点个数（$g_{0,0}=0$，$n$ 不确定，最终状态为 $i+j=n-1/n$，其余类似）。

最后的最后，来玩个大冒险吧：取一张纸条，然后以秒为单位，接连写下 $n=62$ 和 $n=97$ 时答案的瘫痪用时，第二天把纸条扔给你的同桌。看看你的同桌是什么反应，回来后在这里分享！