题解 AGC047F 【Rooks】

· · 题解

题意

有 N 个车在一张无限大的棋盘上，第 i 个在 (X_i,Y_i)。每行每列最多一个车。

有一个卒，会替换第 s 个车，可以走八连通，但是不能走到被车攻击的地方。吃车的时候可以走对角，否则只能走上下左右。

对于 s=1\dots N，求出吃掉最多的车时的最小步数。

2\le N\le 10^6,1\le X_i,Y_i\le 10^6 \forall 1\le i<j\le N,X_i\ne X_j,Y_i\ne Y_j

题解

对于复杂度还是很迷。毛估估是对的。但是我不知道怎么严谨证明。

首先可以把 X_i 排序，然后 X,Y 离散化。以下内容假设 X_i=i,Y_i\in[1,N]，dis(i,j) 表示 i 和 j 的曼哈顿距离（离散化之前）。下面从简单的子问题入手分析这个问题。

子问题 1：N\le 300

考虑枚举起点 s， f_{i,j,isRight} 表示当前吃掉了 [i,j] 所有子，isRight 表示现在在 j 还是 i，最少的步数。

然后转移就设 mn=\min_{i\le k\le j}Y_k,mx=\max_{i\le k\le j}Y_k，如果 Y_{i-1}=mn-1 或 Y_{i-1}=mx+1，那么就可以转移：

f_{i-1,j,0}\leftarrow f_{i,j,isRight}+dis(i-1,i+isRight\times(j-i))

然后对于 f_{i,j+1,1} 也是同样的。初始值是 f_{s,s,0}=0。

朴素实现是 \mathcal O(N^3) 的。

注意如果最后最大的区间是 [L,R]，那么需要减去 R-L 步，因为每一次吃子的时候是两步一起走的。

子问题 2：N\le 3000

这个要求 \mathcal O(N^2) 捏，也就是不能枚举起点。

首先手玩一下发现每次扩展的方向顺序是无关的，也就是对于刚刚的 dp，肯定存在一个极大的可以到达的区间，不管按什么顺序操作最后都能到这个极大的区间。

所以我们可以倒过来 dp，转移的时候从大区间往小区间转移，方程是类似的，只是反过来：

f_{i-1,j,0}+dis(i-1,i+isRight\times(j-i))\rightarrow f_{i,j,isRight}

另一种转移同理。初始值是对于极大的区间[i,j] f_{i,j,0/1}=-(j-i)。起点为 s 的答案就是 f_{s,s,0}。

这个直接做就是 \mathcal O(N^2) 了。

子问题 3：Y_i=i

这个就比较憨憨。对于起点 s，方案一定是 s\to 1\to n 或 s\to n\to 1，最后的答案就是：

\min(dis(s,1),dis(s,n))+dis(1,n)-(n-1)

原问题

子问题 3 看起来非常憨对不对。为什么要有这个子问题呢。这个其实是启示我们，如果 [i,j] 满足 \forall i\le k<j,|Y_k-Y_{k+1}|=1，那么如果在子问题 2 的dp的时候我们扩展了 j，可以直接把 [i,j] 整一段扩展。

这个有什么用呢？一个令人惊讶的事实是，现在的状态数变成了 \mathcal O(N)！也就是直接记忆化dp就可以过了。

下面说明一下为什么是对的。感觉比较意识流，感性理解一下。。

考虑对于起点 s 最后扩展到的极大区间一定是类似下图的：

对于这个东西，里面的每个点作为起点，按照上面的算法，最后得到的状态数是层数级别的。

然后对于所有的点，一定会形成若干个极大矩形。

可能会有上面的情况，也就是一些点同时在两个矩形里。但是最多也就只有两个矩形。所以层数和还是 \mathcal O(N) 的。所以总的状态数也是 \mathcal O(N) 的。

用 map 记忆化最后的复杂度是 \mathcal O(N\log N)。

代码

说了这么多但是代码还是很好写的，直接按上面的做法模拟即可。

洛谷博客太垃圾了贴了代码就提交不了

代码去 AT 看吧。