自动搬运

查看原文

来自洛谷，原作者为

	RainWetPeopleStart IX

搬运于2025-08-24 22:51:58，当前版本为作者最后更新于2025-07-01 19:21:22，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

个人认为本题的 $a_{i,j}=1$ 应改为在由 $a_{i,j}=1$ 的边 $(i,j)$ 构成的有向图 $G$ 中，$i$ 可以到达 $j$。

构造思路

通过观察 CF 上 std 跑样例的输出，我们可以得到如下构造思路。

下设最底层第 $i$ 行第 $j$ 列的方格为 $(i,j)$。

如图，最底层 $3n-2$ 列，第 $i$ 个数在 $(1,3i-2)$，同时下面的列留空。

有 $2n^2$ 行，第 $2k+1$ 行是隔断，第 $2k+2$ 行表示一条边。

那么高度应该设多少呢，因为表示一条边的信息量不大，$5$ 层就足够了。

隔断的构造

对于最底层的形如 $(i,3k+1)$ 位置而言，因为要确保 $i$ 能经过，所以留空，其他的位置直接放障碍即可。

效果图：

边的构造

对于 $a_{i,j}=0$，可以直接按隔断的方式构造。

不妨设 $i<j$，$i>j$ 本质一样。

设 $l=3i-2,r=3j-2$，对于 $[l,r]$ 之外的列，我们把不形如 $3k+1$ 的列全用障碍填满，这样是为了去除 $i$ 左边，$j$ 右边的数的影响。

同时，对于 $[l,r]$ 内的不形如 $3k+1$ 的列，把最底层填满即可。

然后在 $l+1$ 堆一个障碍，$l+2$ 堆两个障碍，然后搭一个“桥”到 $r-1$ 即可。

效果图：