[构造] P9837

_Cheems · 2023-11-12 14:33:18 · 个人记录

牛马构造题。

思路

首先应想到：

• 无序二元组数量 =\frac {n(n-1)}2= 金字塔相邻位置总数。所以可将题意转化为：让这 \frac {n(n-1)}2 个无序二元组不重不漏地出现。

• 无序二元组中，相差为 i 的二元组数量 =i-1= 金字塔第 i 行相邻位置总数。

结合上述几点，可以想到去构造第 i 行刚好有 i-1 个相差为 i 的二元组。不过这样行不通，难以满足一行内元素不重。

注意到题目对列的限制很松，尝试围绕列构造。由于金字塔是对称的，因此也有：相差为 i 的二元组数量 = 第 i 列相邻位置总数。注意此处所说第 i 列是实际的第 i 到第 i+1 列。

那么再回到行。构造思路如下：令第 i 行的第 j 个二元组相差 j，j 每次递增 1。

至此问题被简化，可以加减交替构造：

于是对每个 i 都这样构造（元素超出边界就停止），最后按长度排序并输出即可。

当然，这道题也可转化为图论模型（ducati 讲的）：让所有点都相互连边，用长度分别为 0,1...n-1 的链恰好遍历每条边一次，且链的开头不一样。构造思路和上文差不多。