NIKKEI Programming Contest 2019 题解
ABCD 就不写了。
E - Weights on Vertices and Edges
题意
给定一个 \(N\) 个点 \(M\) 条边的点带权、边带权无向连通图 \(G\)，你需要删除一些边，使得对于留下的每条边边权小于等于该边所在连通块的点权之和。
\(N,M\le 10^5\)
题解
考虑一个 \(O(NM)\) 的做法，每次将边权大于当前连通块的边全部删除，然后分治处理每个连通块。
显然这个做法与从大到小判断每条边是否满足条件，不满足则删去的做法是一样的。
注意到一条边若满足条件，那么该条边当前所在的连通块中的任意一条边都不会被删除。
于是用带撤销并查集维护即可。
时间复杂度 \(O(M\log M)\)。
F - Jewels
题意
有 \(N\) 个珠宝，\(K\) 种颜色，第 \(i\) 个珠宝颜色为 \(C_i\)，价值为 \(V_i\)，保证每种颜色至少出现了两次。
你需要对于每个 \(1\le x\le N\)，求出满足以下条件时，选择恰好 \(x\) 个珠宝的最大价值和：
- 对于选择的任意一个珠宝，存在另一个与它颜色相同的珠宝也被选择。
\(N\le 2\times 10^5\)
题解
对于同种颜色价值最大的两个珠宝，一定会被同时选择。考虑将这样的两个珠宝捆在一起。
我们将所有珠宝按价值从大到小排序，特别地，对于两个捆在一起的珠宝，价值看成平均值，并且价值相等时强制排在其它珠宝前面。
对于一个 \(x\)，若前 \(x\) 个珠宝恰好可以被选择，那么答案一定为前 \(x\) 个珠宝的价值和。
否则，我们可以先选择前 \(x-1\) 个，然后考虑如何使数量增加 \(1\)。我们在选择前 \(x-1\) 个的基础上，定义以下集合（一种颜色使用过当且仅当选择的珠宝中存在该颜色的珠宝）：
- \(P\) 为被选择的珠宝中不是捆在一起的珠宝。
- \(Q\) 为颜色使用过的珠宝中没有被选择的珠宝。
- \(R\) 为颜色使用过的、捆在一起且其他该颜色的珠宝没有被选择的珠宝对。
- \(S\) 为颜色没使用过的、捆在一起的珠宝对。
- \(T\) 为颜色没使用过的、捆在一起的珠宝和其他该颜色的珠宝中价值最大的组成的三元组。
那么有三种情况：
- 添加一个 \(Q\) 中的珠宝。
- 删去一个 \(P\) 中的珠宝，添加一个 \(S\) 中的珠宝对。
- 删去一个 \(R\) 中的珠宝对，添加一个 \(T\) 中的珠宝三元组。
可以证明不可能存在这三种情况以外的调整方法。
于是我们使用 std::multiset 维护即可。
时间复杂度 \(O(N\log N)\)。
