Contest Info

practice link

Solutions

A. Subscribers

签到题。

B. Touitsu

签到题。

C. Different Strokes

签到题。

D. Restore the Tree

签到题。

E. Weights on Vertices and Edges

题目大意：给你一个连通的无向图，每条边和每个点都有权。定义一个连通块是好的，当且仅当它的每条边的权都不大于它的所有点的权值和。求最少删掉多少条边使得这个图的每个连通块都是好的。

题解：将边按照权从小到大排序，依次加边。若加入一条边后使得两个连通块连通，且新的连通块是好的，那么显然这个新连通块中的每一条边都不用删去。用并查集维护。

F. Jewels

题目大意：有 \(n\) 件珠宝，每件珠宝都有一个价值和一个颜色。现在要展示这些珠宝，要求每种颜色要么没有，要么至少有两件珠宝。对每个 \(1\sim n\) 求最大价值，或判断不可能。

题解：我们首先将每种颜色的珠宝从大到小排序。显然价值最大的两个是优先一起取的，我们把它们“绑定”起来，将它们的价值看做它们价值的平均值。

之后我们对所有的珠宝从大到小排序。对每个 \(x\) 首先尝试贪心地选取前 \(x\) 件，只有一种情况会出现问题，就是第 \(x\) 件和第 \(x+1\) 件珠宝绑定。这时我们不妨先取前 \(x-1\) 件珠宝，然后考虑从中删去 \(t\) 件，再加入外面的 \(t+1\) 件。因为我们是从大到小排序，因此显然 \(t\ge3\) 时不会最优（因为这 \(t\) 件和 \(t+1\) 件中必然会出现同类型、前者大于后者的情况）。所以我们要用 multiset 动态地维护 \(1,2,3\) 件珠宝的情况，对 \(t=0,1,2\) 取一个最大值即可。