P9837 [lg noip B] 汪了个汪

· · 题解

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

首先，我们知道有 \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;
}