专栏文章

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

ZZyc_zhouyuchen
P9921题解参与者 5已保存评论 6

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
6 条
当前快照
1 份
快照标识符
@miou5nc8
此快照首次捕获于
2025/12/03 01:12
3 个月前
此快照最后确认于
2025/12/03 01:12
3 个月前
查看原文
我的做法不多见哦 ovo。
没有高深的算法，只有朴素的思维。

题意

形式化题意：
给出整数 nn，mm。1≤n≤1500,1≤m≤21 \le n\le 1500,1\le m\le 2。
给出一个 n×nn\times n 的 0101 方格图。要取 mm 段在行或列上长度为 ll 连续的 11，且所取的位置不交。最大化 ll 的值。

思路

m=1m=1 可以直接输出最长段。
m=2m=2 比较复杂。
发现如果一个答案合法，则较小答案的也合法。于是可以二分答案。
问题是如何快速判断答案是否合法。

同向

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

异向

瓶颈是如何处理一横一竖的答案。观察发现，可以把横着的最长段和竖着的最长段取出来，计算这两段合起来最多放多少。计算方式如下：
称取出的最长横竖段长度分别为 L(line),C(column)L(line),C(column)。
若两段无交，就取较短一段的长度
若有交，取 min⁡(L,max⁡(C1,C2))\min(L,\max(C1,C2))，其中 C1,C2C1,C2 指竖段被横段切开的两段长度。横竖反一下也算一遍答案，两个答案取 max⁡\max。
而其他的横竖段都没有用。有些反直觉，但事实是这样。详细解释如下：
设其他任取的一对横竖长度分别为 L′,C′L',C'。
如果 L′,C′L',C' 组成答案，那么答案一定小于等于 min⁡(L′,C′)\min(L',C')，而 L′≤L,C′≤CL'\le L,C'\le C，所以这对 L′,C′L',C' 构成的答案一定不优于 min⁡(L′,L)=L′\min(L',L)=L' 或者 min(C′,C)=C′min(C',C)=C'，这会在 check 同向段时被判为合法。所以 L′,C′L',C' 的答案不会对求出最大答案产生影响。
再解释一些可能让人起疑的细节：
Q：如果我其他任取的段，横段就是最长横 LL，竖段 C′C' 不是最长竖 CC，会不会出问题？
A：并不会。假设 L,C′L,C' 无交，如果 L≥C′L\ge C'，L,C′L,C' 的答案 C′C' 可以由 C,C′C,C' 得到；否则，L,C′L,C' 的答案为 LL，小于 C,C′C,C' 的答案，而比一个合法答案小的长度也一定合法，所以 L,C′L,C' 的答案也是没用的；若 L,C′L,C' 有交，答案不会优于无交状况，所以也没用。
Q：待补充，欢迎各位在评论区提出质疑。
至于如何找到最长横竖段，扫一遍然后记录其位置即可。

综合

以异向部分求出的答案作为下界，nn 作为上界，二分答案即可。
时间复杂度上，
  • 输入 O(n2)O(n^2)
  • 预处理最大横竖段和段长数组 O(n2)O(n^2)
  • 对段长数组求后缀和 O(n)O(n)
  • 求最大横竖段的答案 O(1)O(1)
  • 由于 check 是 O(1)O(1)，所以二分答案 O(log⁡n)O(\log n)。
总时间复杂度 O(n2)O(n^2)。常数较小。

代码

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

闲话

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

评论

共 6 条评论，欢迎与作者交流。

正在加载评论...