自动搬运

查看原文

来自洛谷，原作者为

	lovelyboy **

搬运于2025-08-24 21:46:30，当前版本为作者最后更新于2018-12-13 13:31:57，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

调一年后终于过了，兴奋地点开了题解，然后居然是

dfs+剪枝

然后楼下大神的代码只有60行，emm

哎简单讲一下我的做法，2-sat+前缀和优化建图+bitset压位 首先发现确定第一行和第一列就可以确定整个矩阵，而且矩阵第i行第j列的值一定可以通过$(1,1)(i,1)(1,j)$三个值算出来。由于每个格子的取值范围很小，我们不妨枚举第一个格子的取值，那么整个矩阵的限制就会转化为$l\leq(i,1)\pm(1,j)\leq r$ 其中$l$和$r$都是可以通过矩阵的信息算出来的。

然后对于将每个$(1,j)$和$(i,1)$的取值拆成$P$个状态，第$i$状态表示这个格子是否可以取小于等于$i$的值，根据2-sat对每个状态建$true$和$false$两个点，然后$i$的$true$向$i+1$的$true$连边，因为如果取了小于等于$i$那一定取$i+1$，同时第$p-1$个格子一定选，那么将$p-1$的$false$向$p-1$的$true$连边。

对于节点之间不等式的关系我们将大于和小于拆成两条限制，然后建边。不妨以 $l\leq(i,1)+(1,j)$为例（$(i,1)+(1,j)\leq r$和这个是一样的）。我们枚举$(i,1)$的取值。假设我们令$(i,1)\leq k$，那么可得$(1,j)\gt l-k-1$ 所以我们将$(i,1)$的$k$号节点的$true$向$(1,j)$的$l-k-1$的$false$连边（false表示小于等于不成立也就是大于）即可。

最后跑2-sat，由于要求字典序最小所以需要用$O(VE)$的那个暴力算法，但是这样过不了所以可以用bitset压一下变成$O(\frac{VE}{64})$就可以过了