AT2149

WeLikeStudying · 2021-09-15 21:15:13 · 个人记录

• 全做法。
• 供各位比对和寻找思路之间的联系。
• 作者个人尝试了尽可能多的思路，个人认为还是较为连贯的，所以贴了上来。
• 可以直接看第三种做法，第一种做法的确没什么用，第二种做法的目的在于引入扫描线的思想。
• 代码存在云剪贴板防止影响排版。

题意

• 必须将每个关键点的上或下或左或右涂黑，求白色区域（可以证明一定是个矩形）周长最大值。

第一种做法

• 暴力枚举每个点的四种情况。
• 状态压缩时间复杂度 \Theta(n\cdot 4^n)。
• 代码实现。
• dfs 时间复杂度 \Theta(4^n)，因为枚举的同时就可以计算。
• 代码实现。

第二种做法

• 纯枚举显然没有做头，尝试寻找性质。
• 我们发现如果下面的点选择涂上面且上面的点图下面是没用的。
• 尝试枚举上边界使得其上的点都往上涂，再枚举左右边界……
• 我们可以发现每种合法的情况对应了一种内部没有任何点的矩形。
• 充分性：合法的矩形内部显然没有点。
• 必要性：对于内部没有点的矩形，将它上方的点的上方涂黑，下方的点下方涂黑……，也就是一种情况。
• 将坐标离散化，枚举左上，右下的端点，时间复杂度 \Theta(n^4)。
• 代码实现。
• 不过这样也太暴力了，可行的优化是很多的。
• 例如枚举长方形上边界左边界右边界，二分下边界（因为内部没有点的矩形情况是连续的），时间复杂度 \Theta(n^3\log n)。
• 代码实现。
• 例如枚举长方形上边界和左边界，通过下图可以看到，只有这些蓝色的点有用，紫色的代表每个可行解。

• 故从右往左枚举左边界，维护点集 \mathbf{P} 满足：对于其中的点 (x_i,y_i)，(x_j,y_j) 都有 x_i<x_j。
• 暴力计算的时间复杂度是 \Theta(n^3) 的。
• 代码实现。
• 但，这个暴力……也太暴力了吧（废话）。
• 来个简单的优化。
• 代码中（只有 q(j,y) 在变）：

  r[k+1].x-p[i].x+q[j].y-r[k].y

• 这个可以用数据结构优化的，这个数据结构支持最后点修改和前缀查询最大值……
• 那咱们就用一个前缀最大值查询维护一下呗，那么复杂度瓶颈在每次枚举上边界后对区域内点的排序，总时间复杂度 \Theta(n^2\log n) ……吗？
• 代码实现。
• 考虑从上往下枚举上边界的过程，我们可以先把点从左往右排序，每次取出最上面的那个点，然后把它左边的点右移一位存储，总的时间复杂度可以优化到 \Theta(n^2)。
• 代码实现。
• 发现这样下去后面就不好优化了，让我们先等一下，毕竟数据结构那东西也算往往是最后一步用的，我们先尝试发现更多有用的性质。
• 从 \Theta(n^3) 的算法重新推导（假设我们已经加上了那个去掉每次枚举同时排序的小技巧），你会发现有不少矩形的枚举是毫无必要的。举个例子：
• 在这张图里，蓝色的矩形我们完全没必要统计，因为它一旦向右边延伸，解一定会更优。
• 而这些我们需要统计的矩形所靠近的点，恰好就是我们下一步需要删除的点。
• 可以认为每个点只对答案做一次贡献，故时间复杂度为 \Theta(n^2) 。
• 代码实现。
• 下面转入第三种做法。

第三种做法

• 考虑分治，实际上，分治思想为许多算法提供了很优秀复杂度的做法。
• 一种实用的想法是在图上切一刀，比如 x=mid。
• 可以看到，有些矩形经过 x=mid 有些则没有。
• 于是我们可以先鸽着那些不经过红线的长方形，先计算经过红线的情况：同时枚举经过红线的长方形，枚举上下边界计算。
• 每层暴力枚举复杂度 \Theta(n^2)。
• 复杂度计算式 T(n)=2T(n/2)+\Theta(n^2)，解为 T(n)=\Theta(n^2)（隐含了二倍的常数因子）。
• 总时间复杂度 \Theta(n^2)，如果你使用某个操作保证对点的均分的话。