Contest Info

date: 2018.11.30 18:31-23:31

practice link

Solutions

A. Trampler

签到题

C. Package

题目大意：有 \(n(n\leq 200)\) 个应用程序，每个应用程序有一些版本。给出 \(k(k\leq 500)\) 个限制条件，每个限制条件是一个 (应用程序，版本）的集合，表示这些选择互斥。保证特定应用程序的特定版本只在限制条件中最多出现一次，现在让你给每个应用程序指定一个版本，且不互斥。输出方案。

题解：对于存在版本不被限制的应用程序，我们选择它的一个没被限制的版本即可。然后建一个网络流，源点向限制条件连边，限制条件向它的应用程序连边，应用程序向汇点连边。跑最大流。

D. Vasya’s graph

题目大意：

给出\(n\le10^5\)顶点间的\(k\le10^5\)对关系，之后依次给出\(m\le10^5\)个加边的申请，如果加入这条边不会使得任意一对关系的两个点连通，则可以加，否则不加，输出成功的加边编号。

题解：

用并查集维护连通性，同时用一个std::unorderd_set存储不可以合并的集合关系。

当加边的时候，并查集find到两个顶点的根，如果在set中没有查到，就可以合并，否则不行。

合并的时候采用启发式合并，将小的集合中的禁止关系更新后插入set。

时空复杂度\(O(n\log{n})\).

E. Quadratic equation

签到题。

F. Alignment

简单贪心、\(dp\)，正确理解题意即可。

G. Rocket

题目大意：火箭有 \(n\) 个部分，每个部分有一些候选的金属材料，质量 \(m_i\)，花费 \(c_i\)。对于每个部分，你可以选择候选金属材料中的一个，或者两个来组成合金，同时你还要选一个参数 \(\alpha\)，合金的质量为 \(\alpha m_1+(1-\alpha) m_2\)，花费为 \(\alpha c_1+(1-\alpha)c_2\)。总质量不能超过 \(M\)，求最小的花费。输出方案。

题解：对于每个部分，我们对金属材料 \((m,c)\) 求凸包，那么可选的金属只会在左下凸壳上。合金显然就是凸壳顶点之间的边。我们初始选择每个凸壳的最左顶点，然后把每个凸壳的第一条边放入优先队列，贪心的选择斜率最小的一条边去增大质量。显然最后的方案只会有最多一个合金。

H. Cabbage

二分。

K. Ecliptic

简单空间解析几何。