题解：P15246 [WC2026] 猫和老鼠

· · 题解

本蒟蒻第一次写黑题题解，希望能够通过

本题解参考了官解以及UOJ群里部分讨论的内容，可能表述较为繁杂且病句较多，但是对像我这样的蒟蒻还算比较清晰。

题目点评：本题考查知识点全面，部分分区分度明显，代码实现难度较大。同时也是我个人认为是在AI辅助测试里人机合作比较顺畅的题目，对于网络流部分不会的选手可以完全交给AI完成。

第一步：转化题目

首先，我们看到这种位移的题目，构建 时间—位移 坐标系，考虑转化为线段。这基本算是一个比较常用的小技巧了，关于坐标系旋转的小trick 里面有另外两个例题，希望能够有所帮助。

此时我们可以使用 \pm 1 斜率的直线来刻画这样一个问题，但是斜线不是很好处理，考虑旋转坐标系，变成垂直于坐标轴的线段。(说句题外话，可能当时首想就是能不能扫描线数据结构维护，尽管最终思路错了，但是还是歪打正招，这一步走对了)。

于是就会转化为上面的这些线段，此时可以把题目转化为正好是官解所说的内容：

耗子只能向右或向上移动。则问题变为：是否存在从左下走到右上，且穿越不超过 k 条线段的路径。

考虑建图

很明显此时的两个边界转化为两个平行的斜线，而且在斜线中间有若干条垂直于坐标轴的线段。

什么时候可以让老鼠的任意路径必然会穿过至少 k 个节点？

我们先思考 k=1 的时候如果猫能拦住老鼠，那么老鼠就一定不能从缝隙穿过。那么如何才能不让他穿过呢？

很明显，如果老鼠左侧有比他高的线段，就会被直接挡住而没有任何影响。

可能会有一个疑问，会不会出现下面的情况？

很显然是不对的，因为如果老鼠不想被包裹，那么最外面势必要形成封闭区域，而对于无法产生封闭的连边可以视为无效连边，而因为无法到达下斜线，所以就对答案没有影响。

对于上图的 FG，NO：我们会将 FG 向 NO 连边，但是由于 NO 无法连接新的有效线段，从而无法到达出点，于是就对答案没有影响。

我们可以得到结论：从左上边界出发，可以任意向左或向上，或根据机器猫形成的线段向右或向下移动，直到抵达右下边界。

而走到端点并不会对答案造成任何影响。

下面开始考虑 k=1 的情况：

我们首先想到暴力连边，每次对每个端点，向左上方一个矩形区域的所有端点连边以及向右下相交的线段端点连边，然后就会得到 O(n^2 \log n) 的最短路算法。

我们考虑将问题扩展到任意 k，发现大体思路是对的，考虑使用网络流：

实际上，我们将源点和汇点交换，本质是考虑逆时针定向，这对答案没有影响。

优化建图

很明显可以考虑优化建图，我一开始想着是不是要把横竖的分开处理，实际上lhx在群里说这个需要连边的前缀区域实际上是一个矩形。

于是我们可以考虑离散化后用树状数组优化建图，然后跑Primal-Dual原始对偶算法，时间复杂度 O(nk\log^2 n)。

我们还可以发现，这个连边条件是一个二维偏序，我不想写离散化可以考虑 CDQ 分治来实现，这样比较方便。

反正这里好多种优化方法，本质还是 2side 的优化建图。

这个代码写起来确实比较繁琐，不过如果你是AI营员，网络流和优化建图的部分完全可以交给AI。

同时，我尝试了其他网络流算法，好像最多只能拿79分？

代码太难看了，就不挂了……想要的可以私信喵。