题解：P9921 [POI 2023/2024 R1] Budowa lotniska

· · 题解

我的做法不多见哦 ovo。

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

题意

形式化题意：

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

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

思路

$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)。常数较小。

代码

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

闲话

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