T1 Amusement Park
题意:通信题。给定一张 \(n\) 个点 \(m\) 条边的无向连通图。Alice 会得到一个 \([0, 2^{60})\) 中的数 \(x\),并且她需要给这张图上每一个结点标一个数字 \(a_i = 0/1\)。
然后 Bob 也会拿到这张图(编号和 Alice 的一样),但是他不知道 \(x\),也不知道所有点上的数字。他当前在结点 \(p\),并且他知道这个结点上的数字为 \(a_p\)。
Bob 可以进行若干次移动,每次移动可以到达一个相邻的结点,并获取这个结点上的数字。Bob 需要用不超过 \(120\) 次移动知道 \(x\)。
\(60 \le n \le 10^4, m \le 2 \times 10^4\)。
首先注意到边越多越好做,并且输入可以决定你有多少条边,所以最难的情况显然是树。不妨强化一下,对于任意连通图,拉出一棵生成树,将其他边全部丢掉。于是我们只需考虑树的情况。
考虑 \(n = 60\) 怎么做,并且这种情况是可以存在的(原问题比这个强)。此时我们发现 Alice 能给 Bob 提供的信息只有 \(60\) 个 Bit,那么对于 Bob 来说什么都不能丢失,所以 Bob 必须走完这张图上的所有点。
可以给所有点规定一个顺序,表示它在最后的二进制数中位于哪一位。然后从一个结点出发时考虑树的欧拉序,可以用 \(2(n - 1)\) 次移动访问所有结点。
接下来考虑 \(n \neq 60\),首先可以拉出一个包含根的大小为 \(60\) 的连通块,在这个连通块内的所有结点做法和 \(n = 60\) 一样。
考虑连通块外的部分,我们可以对于每个结点,从他的父亲转移过来。可以考虑在父亲所属连通块内删除一个结点并加入自己,得到一个新连通块。删的这个点可以是父亲的连通块上的任意非父亲的叶子(考虑一棵大小为 \(60\) 的无根树至少有 \(2\) 个叶子)。对于该节点丢失的一个 Bit 的信息,可以在当前结点记录。得到这个连通块的过程还是欧拉序遍历即可。
时间复杂度 \(O(n\omega)\),其中 \(\omega = 60\)。移动次数 \(2(60 - 1) = 118\)。
T2 Bulldozer
二维平面上有 \(n\) 个点,每个点有一个坐标 \((x_i, y_i)\) 和一个权值 \(v_i\)。
选两条平行的直线,最大化夹在两条直线中间的点的权值和。输出这个权值和。
\(n \le 2 \times 10^3\)。
假设我们枚举斜率 \(k\)。那么考虑对于每个点,求出一条斜率为 \(k\),且经过该点的直线,对于所有点,我们按照对应直线的纵截距排序。考虑在排序后,任意一段区间可以取到,所以答案就是权值数组的最大子段和。
显然 \(k\) 一定为某两点连接得到直线的斜率,否则旋转一下一定不劣。那么一种做法就是每次 \(O(n^2)\) 枚举两个点求出 \(k\),然后排序一下求个最大子段和,时间复杂度 \(O(n^3)\) 或 \(O(n^3 \log n)\)。
注意到每个 \(k\) 的贡献是独立的,所以我们类似旋转扫描线的,将所有 \(k\) 从小到大排序后计算。
考虑对于两个点 \(u\) 和 \(v\),它们的相对位置一定是在 \(k \le k_0\) 时 \(u\) 靠前,\(k > k_0\) 时 \(v\) 靠前,并且一定存在某一时刻,使得 \(u\) 和 \(v\) 相邻。
所以对于所有可能对答案有贡献的 \(k\) 排序,对于两个点会产生相对位置变化的 \(k_0\) 排序,扫描线即可。每一相对位置变化可以看作交换两个树,我们可以用线段树维护,那么交换两个数在线段树上的体现其实就是单点修改,这个显然时可以做的。
时间复杂度 \(O(n^2 \log n)\)。
T3 Golf
二维平面上有一个高尔夫球,起始坐标为 \((X_s, Y_s)\),你要将它打到 \((X_t, Y_t)\)。
有 \(n\) 个障碍,每个障碍形如一个矩形,在任意时刻求不能穿过障碍,也不能在内部,但可以在边界上。
每次击球选择一个和坐标轴平行的方向,将球打出去任意距离,求最少需要多少次击球才能完成任务。
\(n \le 10^5\)。
将最优方案刻画为一条路径 \((X_s, Y_s), (X_1, Y_1), (X_2, Y_2), \ldots, (X_t, Y_t)\),最小化的就是路径的长度,容易发现每次球的横坐标一定是起点、终点、或某一个障碍的顶点的横坐标中的一个,否则平移一下一定不劣,所以可以先离散化一下。
一个较为暴力的做法是对 \(O(n)\) 条直线两两求交,对于交点 \(\text{bfs}\),时间复杂度 \(O(n^2)\) 或 \(O(n^3)\)。
注意到这样做状态数就是 \(O(n^2)\) 的,不好优化。考虑我们不将一个格点看作一个状态,而是将真正有用的线段看成一个状态。对于每个矩形的四条边延长,直到碰到边界或者另一个状态(要求极长),对于起点和终点分别向四个方向做射线,类似处理即可。这样可以得到有用的线段只有 \(O(n)\) 条,题意可以转化为每次切换一条线段的代价为 \(1\)。
考虑对于这些线段 \(\text{bfs}\),暴力做还是 \(O(n^2)\) 的,但此时状态只有 \(O(n)\) 个,这给我们提供了优化的空间。
具体的刻画出转移的形式:假设这条线段是竖向的(于 \(y\) 轴平行),显然它只能转移到横向线段。由于它的横坐标 \(x\) 是定值,能覆盖纵坐标的范围是 \([l, r]\),假设另一条横向线段的满足 \(y = y_0, x \in [l_0, r_0]\),前者能转移到后者当且仅当 \(y_0 \in [l, r], x \in [l_0, r_0]\)。
这个东西考虑用线段树套平衡树维护,对于上面的情况而言,在 \([l_0, r_0]\) 范围内插入 \(y\),在 \(x\) 的单点处查询纵坐标在 \([l, r]\) 内的所有状态。对于这些状态更新后就从线段树上删掉(因为是 \(\text{bfs}\),之后的转移肯定不优),那么每个状态至多被转移一次,被加入和删除一次。
时间复杂度 \(O(n \log^2 n)\),空间复杂度 \(O(n \log n)\)。
标签:结点,le,线段,连通,60,JOI,2017,Open,Bob From: https://www.cnblogs.com/hztmax0/p/18412907