标签：10 4.12 一个点 复杂度 times leq mathcal 2024.4

Sat

JOI 2023 Final

宣传 2

\(n\) 个人，每个人有住所位置 \(X_i\) 与影响力 \(E_i\)，一个人 \(i\) 拿到书后会号召另一个人 \(j\) 买书仅当 \(|X-i-X_j|\leq E_i - E_j\)，你最少送多少个人书才能使得所有人都会有书（送的或者被号召买书）。

\(n\leq 5\times 10^5\)。

---

拆一下绝对值，得：

\[\begin{cases} X_i - X_j \leq E_i - E_j \implies E_j - X_j\leq E_i - X_i \\ X_j - X_i \leq E_i - E_j \implies E_j + X_j\leq E_i + X_i \\ \end{cases} \]

设每个人为点 \(P_i(E_i - X_i, E_i + X_i)\)，如果有一个点在另一个点左下角那么就会被号召。

按照 \(x\) 排序，单调栈算有几个点不被号召即可。

迷宫

给定一个 \(R\times C\) 的迷宫，每次操作可以选择一个 \(N\times N\) 的子矩阵并抹除该部分的所有障碍，求最少操作次数使得可以从起点到终点。

\(R\times C\leq 6\times 10^6\)。

---

首先显然要 01bfs，如果可以从路走就从路走。

考虑暴力更新，时间复杂度为 \(\mathcal{O}(RCN^2)\)。

可以发现，每一个格子通过一次操作所得到的行动范围是一个 \((2N+1)\times (2N+1)\) 的矩形，挖掉四个角。如果终点不在内部，则需要跨出边界。

维护边界即可，暴力扫的时间复杂度为 \(\mathcal{O}(RCN)\)，此处 \(N\) 同阶与 \(\mathcal{O}(\sqrt{RC})\)。

拿一个并查集维护，时间复杂度为 \(\mathcal{O}(RC\alpha(R))\)。

训猫

\(n\) 个点的树，每个节点有一个高度 \(P_i\)，构成全排列。

每一次你可以标记一个点，如果标记到猫所在的点，猫会到达【最高的】【可以不通过被标记的点到达的】点。

猫初始在高度为 \(n\) 的点，请问合理的标记顺序可以让猫最多走多远？

\(n\leq 2\times 10^5\)。

---

考虑 DP，发现每次删掉一个点后会到达一棵子树并且无法返回，记 \(f_u\) 表示猫在 \(u\) 点，最多可以走的距离，则显然从每个子树中编号最大的点 \(v\) 转移 \(f_v + dis(u,v)\)。

考虑按照高度从小到大枚举转移，直接用高度建边，并用并查集维护连通性即可。

标签：10,4.12,一个点,复杂度,times,leq,mathcal,2024.4
From： https://www.cnblogs.com/ydzr00000/p/18117488