洛谷 NOIP 2023 模拟赛-汪了个汪-题解

简要题意

棋盘上有 $n$ 行，第 $i$ 行有 $i$ 个格子。你要在格子填 $1\sim n$，满足：

• 每行第一个数互不相同
• 所有在行上相邻的两个数所组成的无序对互不相同
• 每行的数互不相同

$n\le 4000$

题解

容易发现棋盘上的无序对与总的无序对数量是相同的，也就是说，要全部填满。可以考虑把它们分类，然后再按规律放数。

我们发现，无序对中两数差为 $1$ 有 $n-1$ 个，差为 $2$ 有 $n-2$ 个，$\dots$，差为 $n-1$ 有 $1$ 个，看上去很巧，如果能把它们按行归类，就好了。但是显然 $2,5,3,6,\dots$ 是放不进的。

考虑能否这样，第 $i$ 行有差为 $1\sim i-1$ 的无序对各 $1$ 个。发现如果这样构造：$x,x+1,x-1,x+2,x_2,\dots$，是符合条件的。于是就做完了。

#include<bits/stdc++.h>
using namespace std;
int n,t;
vector<int> v[4001];
bool cmp(vector<int> v1,vector<int> v2)
{return v1.size()<v2.size();
}
int main()
{cin>>n>>t;for(int i=1;i<=n;i++){int x=0,now=i,y=1;while(now>0&&now<=n){v[i].push_back(now);now=now+(x&1?1:-1)*y;y++;x++;}}sort(v+1,v+1+n,cmp);for(int i=1;i<=n;i++){for(auto j:v[i]){printf("%d ",j);}puts("");}
}