自动搬运

查看原文

来自洛谷，原作者为

	樱雪喵 无尽欺骗，无限祈愿 | AFOed | qq: 3480681868

搬运于2025-08-24 22:52:17，当前版本为作者最后更新于2023-11-11 19:44:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

感觉这个构造挺人类智慧，可能脑电波一下跟出题人对上就会了。
不会基于严谨理论的做法，大致阐述一下猜到这个东西的过程吧。

首先，我们知道有 $\dfrac{n(n-1)}{2}$ 个横向相邻数对，$\dfrac{n(n-1)}{2}$ 个本质不同二元组。这两个数量是相等的，也就是说每种本质不同二元组在棋盘中恰好出现了一次。

那或许可以尝试把这些二元组进行分类，按照相同的类别来摆放。
进一步瞎猜，发现：两个元素差为 $1$ 的有 $n-1$ 对，差为 $2$ 的有 $n-2$ 对，同理，差为 $n-1$ 的有 $1$ 对。我们把这些数对分成了大小分别为 $1,2,\dots,n-1$ 的组。
然后你发现这和棋盘上每行的相邻棋子数正好对上了！
但是没做完，因为 $(1,4),(2,5),(3,6),\dots$ 这堆东西显然没法放到一行里。再继续找能和这个分组形式对上的东西。

考虑转一下方向，棋盘每列能放下的二元组数量同样满足这个性质。
也就是说，我们试图在第 $1$ 列放 $n-1$ 个差为 $1$ 的数对，第 $2$ 列放 $n-2$ 个差为 $2$ 的数对，以此类推。
知道了大致方向，我们再考虑对于每一行的构造，设这一行有 $n$ 个数。我们要让其形如第一对差为 $1$，第二对差为 $2$，并始终在 $[1,n]$ 范围内，不难想到加减交替构造。
设开头为 $x$，则这一行的值为：

$$x\quad x+1\quad x-1\quad x+2\quad x-2\quad \dots\ $$

又因为已知每行开头的数不相同，我们依次枚举每个 $x$，重复构造上述序列直到超出范围。例如 $n=7$，可以写出：

$$\begin{aligned} &1\quad 2\\ &2\quad 3\quad 1\quad 4\\ &3\quad 4\quad 2\quad 5\quad 1\quad 6\\ &4\quad 5\quad 3\quad 6\quad 2\quad 7\quad 1\\ &5\quad 6\quad 4\quad 7\quad 3\\ &6\quad 7\quad 5\\ &7\\ \end{aligned} $$

把它们按长度顺序排序，即为答案。

$$\begin{aligned} &7\\ &1\quad 2\\ &6\quad 7\quad 5\\ &2\quad 3\quad 1\quad 4\\ &5\quad 6\quad 4\quad 7\quad 3\\ &3\quad 4\quad 2\quad 5\quad 1\quad 6\\ &4\quad 5\quad 3\quad 6\quad 2\quad 7\quad 1\\ \end{aligned} $$

时间复杂度 $O(n^2)$。

const int N=4005;
int n,t,a[N][N];
int main()
{
    n=read(),t=read();
    for(int i=1;i<=n;i++,cout<<endl)
    {
        int st=(i&1)?(2*n-i+1)/2:(i>>1);
        for(int j=1,len=1;j<=i;j++,len++)
        {
            cout<<st<<" ";
            if(j&1) st+=len; else st-=len;
        }
    }
    return 0;
}