P9837 汪了个汪

很智慧的构造。

相当于我们要将 $\frac{n(n-1)}{2}$ 个数对 $(x,y)$ ，以一定方式放入给出的方格内。一个简单的想法是，将 $(x,y)$ 按照 $|x-y|$ 分类，再以一种加减交错的方式排在一起。按照 $|x-y|=i$ 分类之后，似乎正好与每一列的二元组的个数对应起来了。

更具体一点，我们对于每一个 $x$，构造 $x,x+1,x-1,x+2,x-2,\cdots$，直到不能构造为止。这样的形式恰好满足上面所有限制。最后按照序列长度排序即可。正确性看起来真的显然，但是确实很巧妙。

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

Code

#include<iostream>
#include<cstdio>
using namespace std;
const int N=4e3+10;
int n,t;
int a[N][N];
int rk[N];
int main()
{
    scanf("%d%d",&n,&t);
    for(int i=1;i<=n;i++)
    {
        a[i][1]=i;
        int cnt=1;
        for(int j=1;j<=n;j++)
        {
            if(i+j>n)break;
            a[i][++cnt]=i+j;
            if(i-j<1)break;
            a[i][++cnt]=i-j;
        }
        rk[cnt]=i;
    }
    for(int i=1;i<=n;i++,puts(""))for(int j=1;j<=i;j++)printf("%d ",a[rk[i]][j]);
    return 0;
}