2026.7.11 贪心

2026/7/13 8:15:06

[JOIST 2022] 团队竞技 / Team Contest

考虑先分别找出 \(X_i,Y_i,Z_i\) 最大的三个人。若此时存在一个人满足其至少有两个是非严格最大值，那么这个人在团队中一定是不合法的，可以删去，然后递归到规模为 \(n-1\) 的子问题；若不存在，则这就是答案。

使用三个 set 维护即可，时间复杂度 \(O(n \log n)\)。

熟练

记 \(c_i\) 为点 \(i\) 被所有链覆盖的次数。发现答案有一个显然的下界 \(\max c_i\)。那么能不能取到呢？

答案是可以。考虑构造方案：称取到 \(\max c_i\) 的 \(i\) 为关键点，我们选取深度最小的关键点，其祖先中没有任何关键点。选取一条路径 \((a_k,b_k)\) 满足 \(\text{lca}(a_k,b_k)=i\) 即可满足条件。

符合条件的路径是否一定存在？考虑若不存在，则所有经过 \(i\) 的路径都经过 \(i\) 的父亲，说明 \(i\) 的祖先中存在关键点，矛盾。故一定存在合法的路径。

模拟上述构造过程即可做到 \(O((n+m)\log^2 n)\)。

[JOISC 2019] 馕 / Naan

我们先来考虑 \(N=2\) 应该怎么做。

我们既然想让每个人的幸福感均至少为其独吞的 \(\dfrac{1}{2}\)，那么我们对于这两个人分别找出在其独吞时能够将馕分为幸福感相等的两部分的那个点。然后，我们只需要取分割点靠前的那个人。将这段前缀分给这个人，剩余部分分给第二个人即可。由于分割点相较于第二个人来说是靠前了的，因此第二个人的幸福感也至少是其独吞的 \(\dfrac{1}{2}\)。

扩展到 \(N \ge 2\)，尝试对每个人找出 \(N-1\) 个点，这些点将馕分为幸福感相等的 \(N\) 部分。每次选取一个还能选的最靠前的部分，将其分给这个人即可。正确性证明可以类比两个人的情况。

时间复杂度 \(O(NL)\)，需要推一些数学公式。

[集训队互测 2024] 长野原龙势流星群

考虑点权最大的点，其答案显然为其点权。

考虑这个点的父亲。若一个连通块包含了这个点的父亲，那么包含这个点显然是优的，因此可以看做一个点处理。

于是可以提出如下做法：

将所有点按照点权扔到一个优先队列中，每次取出点权最大的点，将这个点的答案设为其点权，合并其与其父亲并将合并后该连通块中的点权平均值作为点权扔到队列中。

时间复杂度 \(O(n \log n)\)。

[JOISC 2021] イベント巡り 2 (Event Hopping 2) (Day4)

待补。

Digital Village

考虑 E2 怎么做。建立 Kruskal 重构树，从小到大加入边。定义 \(f_{u,i}\) 代表以 \(u\) 为根的子树中有 \(i\) 个信号发射器的最小延迟，则有转移：

\[f_{u,x+y} \leftarrow \begin{cases} f_{\text{ls}_u,x}+f_{\text{rs}_u,y} & x>0,y>0 \\\ f_{\text{ls}_u,x}+\text{sz}_{\text{rs}_u} \times w_u & x>0,y=0 \\\ \text{sz}_{\text{ls}_u} \times w_u + f_{\text{rs}_u,x} & x=0,y>0 \\\ 0 & x=0,y=0 \end{cases} \]

暴力转移，时间复杂度为树上背包的 \(O(n^2)\)，能够通过 E2。

怎么优化呢？令 \(f_{u,0}=\text{sz}_u \times w_{\text{fa}_u}\)，那么上述合并过程可以看做对 \(f_{\text{ls}_u}\) 与 \(f_{\text{rs}_u}\) 先做闵和然后在 \(0\) 处单点加得到，因此 \(f\) 是凸的，Slope Trick 维护即可。

使用 multiset 启发式合并，时间复杂度是 \(O(n \log^2 n)\)。