Atcoder ARC-065

ARC065(2020.8.3)

尛你 \(\%\%\%\)

翻译是错的，自闭了好久。先并查集将地铁连接的连通块联通，再枚举每条道路边判断是否在同一连通块即可。

这翻译不知道在讲什么，建议看原题面。

可以发现对于每个点以哈密顿距离 \(d\) 画圆是一个以该点为几何中心，将对角线长度为 \(2d\) 的正方形旋转 \(45 \degree\) 的一个图形。可以发现我们要做的实际上是一个 \(bfs\) 的扩展过程，现在问题转化为如何快速求出满足条件的点的数量，不难发现这实际上是统计四条线段上的点的个数，并且这四条线段斜率都为 \(+1 / -1\) 实际上这样的直线都是有非常优秀的性质的，可以发现这些直线上的点都会满足 \(x + y = k / x - y = k\) 的性质，于是我们可以考虑分别维护斜率为 \(+1, -1\) 的直线，将每个点按照截距为第一关键字 \(x\) 为第二关键字排序，每次查询只需要在数组上 \(lower\_bound / upper\_bound\) 即可。但为了保证复杂度正确，我们只能让每个点入队一次，因此还需要开个 \(set\) 实时维护剩余的点，注意可能顶点上会算两次，在查询斜率为 \(-1\) 的直线时将左边界 \(+1\) 右边界 \(-1\) 即可。

看了题解后学到一种更为牛逼的做法，可以发现我们不好统计是因为这些线段是有斜率的，我们可以直接旋转坐标轴，让直线没有斜率。例如在本题中，我们坐标轴整体向右旋转 \(45 \degree\)，接下来我们可以使用相似将新点坐标算出来，但此时坐标中可能带有 \(\sqrt{2}\) 这样不方便统计，于是我们可以再将点坐标整体放大 \(\sqrt{2}\) 倍，那么再根据相似可以发现每个点会从 \((x, y)\) 到 \((x - y, x + y)\)。那么我们现在就只需要统计正着的正方形上的点即可，分横着的线和竖着的线维护，以竖着的为例，按照 \(x\) 为第一关键字 \(y\) 为第二关键字排序，每次在数组上二分统计答案，遍历 \(set\) 暴力删除即可。

这种旋转坐标轴的方式貌似叫做曼哈顿距离转切比雪夫距离，这种做法的好处就是不论斜率为多少我们可以转化为斜率为 \(0\) 的情况考虑，能够简化我们的做法。

首先可以发现这样一条性质，被完全包含的线段直接去掉显然是对答案没有影响的，于是我们去掉这些线段后所有线段都将会是一个叠一个的形式。接下来我们可以发现这样一个性质，一个区间有多少种排列方式只与这个区间有多少个 \(1\) 有关，于是我们就有了下面这个 \(dp\)，令 \(dp_{i, j}\) 为到第 \(i\) 条线段，当前还剩余 \(j\) 个 \(1\) 的方案数，可以发现我们每次转移需要确定的是这条线段和上条线段左端点之间的部分，于是我们可以枚举给这部分放多少个 \(1\)，于是就有转移 \(dp_{i, j} = \sum\limits_{k = 0} ^ {\min(j, l_i - l_{i - 1})} dp_{i - 1, j - (sum_{r_i} - sum_{r_{i - 1}}) + k} \times \dbinom{l_i - l_{i - 1}}{k}\) 这个 \(dp\) 复杂度看起来是 \(O(n ^ 3)\) 的，但貌似 \(k\) 每次枚举的上界是 \(l_i - l_{i - 1}\)，因此这个 \(dp\) 的复杂度其实应该是 \(O(n ^ 2)\) 的。

题解的做法更为简单，考虑每次只确定一位选或不选，令 \(dp_{i, j}\) 为当前确定了前 \(i\) 个位置，还剩下 \(j\) 个 \(1\) 可选，转移就非常简单了，注意一下边界情况就可以了。其实这两种做法的本质是一样的，只是具体的实现方式有所不同。

巴特西

Atcoder ARC-065

ARC065(2020.8.3)

最新文章

热门文章