自动搬运

查看原文

来自洛谷，原作者为

	Zyc_zhouyuchen I love coding. It makes me happy!

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

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

以下是正文

我的做法不多见哦 ovo。

没有高深的算法，只有朴素的思维。

题意

形式化题意：

给出整数 $n$，$m$。$1 \le n\le 1500,1\le m\le 2$。

给出一个 $n\times n$ 的 $01$ 方格图。要取 $m$ 段在行或列上长度为 $l$ 连续的 $1$，且所取的位置不交。最大化 $l$ 的值。

思路

$m=1$ 可以直接输出最长段。

$m=2$ 比较复杂。

发现如果一个答案合法，则较小答案的也合法。于是可以二分答案。

问题是如何快速判断答案是否合法。

同向

如果选择的两段同向，就很好办。可以预处理出横向和竖向的每种段长（指极长段的长）各有多少（桶排），再对求出的横竖两个段长数组分别计算后缀和。那么 check(x) 时，如果长度 $x$ 的横后缀或竖后缀数量 $\ge 2$，或者长度 $2 \times x$ 的横或竖后缀 $\ge 1$（注意别越界），返回 true；否则返回 false。

异向

瓶颈是如何处理一横一竖的答案。观察发现，可以把横着的最长段和竖着的最长段取出来，计算这两段合起来最多放多少。计算方式如下：

称取出的最长横竖段长度分别为 $L(line),C(column)$。

若两段无交，就取较短一段的长度

若有交，取 $\min(L,\max(C1,C2))$，其中 $C1,C2$ 指竖段被横段切开的两段长度。横竖反一下也算一遍答案，两个答案取 $\max$。

而其他的横竖段都没有用。有些反直觉，但事实是这样。详细解释如下：

设其他任取的一对横竖长度分别为 $L',C'$。

如果 $L',C'$ 组成答案，那么答案一定小于等于 $\min(L',C')$，而 $L'\le L,C'\le C$，所以这对 $L',C'$ 构成的答案一定不优于 $\min(L',L)=L'$ 或者 $min(C',C)=C'$，这会在 check 同向段时被判为合法。所以 $L',C'$ 的答案不会对求出最大答案产生影响。

再解释一些可能让人起疑的细节：

Q：如果我其他任取的段，横段就是最长横 $L$，竖段 $C'$ 不是最长竖 $C$，会不会出问题？

A：并不会。假设 $L,C'$ 无交，如果 $L\ge C'$，$L,C'$ 的答案 $C'$ 可以由 $C,C'$ 得到；否则，$L,C'$ 的答案为 $L$，小于 $C,C'$ 的答案，而比一个合法答案小的长度也一定合法，所以 $L,C'$ 的答案也是没用的；若 $L,C'$ 有交，答案不会优于无交状况，所以也没用。

Q：待补充，欢迎各位在评论区提出质疑。

至于如何找到最长横竖段，扫一遍然后记录其位置即可。

综合

以异向部分求出的答案作为下界，$n$ 作为上界，二分答案即可。

时间复杂度上，

• 输入 $O(n^2)$
• 预处理最大横竖段和段长数组 $O(n^2)$
• 对段长数组求后缀和 $O(n)$
• 求最大横竖段的答案 $O(1)$
• 由于 check 是 $O(1)$，所以二分答案 $O(\log n)$。

总时间复杂度 $O(n^2)$。常数较小。

代码

代码糖分超标，不贴了，思路到了就行。

闲话

目前最优解，没怎么卡常，也没什么好卡。如果被超了麻烦告诉我，我再卡卡 awa。