A
你在平面上有 \(n\) 个点,你每次可以从一个点跳到其右下或左上任意的点,|
对每个点 \(i\),求所有点到 \(i\) 至少跳多少次的和。
点的坐标值域为 \(M=2500\)。\(n\le 2.5e5\).
我们先考虑某个点,到所有点跳多少次。首先右下,左上都是跳一次即可。
我们先考虑右上的点怎么办。我们一定是从已跳的点跳过去。
设已到达的点最小的 \(x\) 为 \(minx\),最大的 \(y\) 为 \(maxy\),
那么我们可以使 \(x>minx\) 或 \(y<maxy\) 点可以再跳一次到达,
当前还不能到达的是就是右上角 \([1,minx]\times[maxy,M]\),可以划分为子问题求解。
B
平面上有 \(n\) 个点可以放置红色雷达,\(m\) 个点可以放置蓝色雷达,你需要求最大的 \(r\le R\),
使得每个雷达以 \(r\) 的半径画圆,不同颜色的雷达不相交。
求最大的覆盖面积,同颜色雷达重复覆盖的面积重复计算,\(n,m\le 50\).
明显是二分图最大独立集,我们先枚举独立集大小,然后二分半径。
C
两棵树 \(A,B\),\(q\) 次询问,给出 \(A\) 的一条路径,你要求有多少个子路径满足其点集在 \(B\) 树上形成连通块。
\(n,q\le 1e5\).
维护在 \(B\) 树上 \(V-E\) 的最小值,若 \(V-E=1\),那么形成树。
我们现在要求一个历史最小值出现次数的东西。