tdog暑期集训

这是2024暑期集训的题目. $Day1(2024/7/14):$搜索专题(加上一点数位DP). $Day2(2024/7/15):$数据结构专题. $Day3(2024/7/16):$树上问题,如LCA,树的直径. $Day4(2024/7/17):$图论,关于点双,边双,强连通分量,割点和桥(割边). $Day5(2024/7/18):$杂题选讲. $Day6(2024/7/19):$cdq点分治,分块,莫队. $Day6$题解: # 题解 - 07.19 ## T1 count 直接跑欧拉筛就可以了。时间复杂度 $\mathcal{O}(nk)$，其中 $n$ 是值域。 ## T2 trim 删边操作不好处理，我们考虑反过来进行加边。 假设当前加的边连接了连通块 $u$ 和 $v$，通过反证法，不难发现加完边后，直径有三种情况： 1. 等于 $u$ 中的直径 2. 等于 $v$ 中的直径 3. 新的直径一个端点是 $u$ 的直径的端点，另一个端点是 $v$ 的直径的端点 于是我们枚举端点的组合，在树上求两点简单路径取最大值即可。求两点简单路径需要求 $LCA$，可以使用倍增或者树链剖分等。时间复杂度 $\mathcal{O}(nlogn)$。 ## T3 magic 首先我们发现，第一次使用魔法后，可以任意排序，一定是要把相同的数字放在一起最优。之后需要使用的魔法次数是不同的数字的个数。 因此，总共需要至少的魔法次数等于： - 不同的数字的个数减一，当第一次使用魔法可以完全消除某种数字时。 - 不同的数字个数，当没有任何数字可以在第一次使用魔法时消除时。 首先，不同的数字个数很好维护，我们离线之后用莫队即可。 至于怎么判断有没有数字满足可以被消除的条件，对于数字 $x$ 我们可以在 `std::deque[x]` 上维护二元组 $(dist, count)$，其中 $dist$ 表示两个相同数字之间的距离，$count$ 表示有几对连续的这个距离。如果 `std::deque[x]` 内只有一个元素，那么代表它们的位置成等差分布，可以一次魔法消除。 总时间复杂度 $\mathcal{O}(n\sqrt{n})$。 ## T4 teleport 考虑扫描线，使得已经加入的点一定满足 $y_m \leq y$，其中 $y_m$ 是加入的点的 $y$ 坐标（楼层 $B$ 的点），$y$ 是当前要查询的点的 $y$ 坐标（楼层 $A$ 的点）。 对 $x$ 坐标值域建立线段树。值域较大，可以使用离散化或者动态开点线段树。 考虑查询时候，线段树上区间 $[l, r]$ - 如果 $x \leq l$，那么两点距离为 $x_m - x + y - y_m$，其中 $- x + y$ 为定值，线段树上维护 $x_m - y_m$ 的最小值即可 - 如果 $x \geq r$，那么两点距离为 $x - x_m + y - y_m$，其中 $x + y$ 为定值，线段树上维护 $- x_m - y_m$ 的最小值即可 - 如果 $l < x < r$，那么再进入两个子结点查询 由于线段树上包含 $x$ 的区间 $[l, r]$ 一共 $\mathcal{O}(\log{n})$ 个，所以时间复杂度可以保证。 记得在 $y_m + d + 1$ 处删点。对于 $y_m > y$ 的点，我们反转 $y$ 轴即对所有 $y$ 坐标取相反数再跑一遍即可。 总时间复杂度 $\mathcal{O}(n\log{n})$。