XIX Open Cup named after E.V. Pankratiev. Grand Prix of Eurasia, Division 1.

Problem A

Solved by Xiejiadong. 0:07 (+)

温暖的签到。

Problem B

Unsolved.

Problem C

Solved by Xiejiadong. 2:23 (+2)

题意：每个软件有不同的版本。一些软件的版本之间会有冲突，要求在没有冲突的情况下，每个软件装少至少一种版本。

题解：显然，对于某一个软件，如果他的某一个版本与其他任何软件的版本都没有冲突，直接装他就好了。

那么对于剩下的软件，可以用网络流来做：

• 源点连向所有的软件，流量 $1$ ；
• 软件连向每一个版本，流量 $1$ ；
• 为每一个冲突建立一个点，所有冲突的版本连向这个点，流量 $1$ ；
• 冲突的点连向汇点，流量 $1$ 。

跑最大流即可，然后在参与网络里面找可行解。

Problem D

Solved by Xiejiadong. 1:25 (+3)

题意：按照顺序依次加边，加的边需要满足给出的 $k$ 对点中，没有任何一对点在当前图中是联通的。

分析：考虑用并查集来维护联通性。

如果我们对于每一个当前联通块都维护不能与其相连的点集合。考虑对于当前要联通的点 $x$ 和 $y$ ，无非就是 $x$ 所在块的点不能有任何一个在 $y$ 的集合中且 $y$ 所在块的点不能有任何一个在 $x$ 的集合，于是只需要维护每一个联通块内的点和不能与当前联通块相连的点集合。

合并的时候，用启发式合并即可。

Problem E

Solved by Kilo_5723. 0:15 (+)

题意：给出一元二次方程的一个绝对值不超过 $10^6$ 的根 $k$，求一个所有系数不超过 $10^6$ 的一元二次方程。

题解：如果 $k=\pm 1$ 输出 $x^2 \pm 2x +1$，否则如果 $k>0$，输出 $(x+1)(x-k)$，反之输出 $(x-1)(x-k)$。

Problem F

Upsolved by Kilo_5723.

Problem G

Unsolved.

Problem H

Solved by Kilo_5723. 1:09 (+2)

Problem I

Solved by Xiejiadong. 4:07 (+5)

题意：每次加入一条线段或者询问一个点被多少线段覆盖，强制在线。

题解：坐标是小数，最多 $6$ 位，考虑 $\times 10^6$ 之后变成整数线段树。

考虑用动态开点的线段树来维护，延迟标记不需要下传，每次都是单点询问，沿路的标记都手动带上即可。

• 坑点是 $\times 10^6$ 一定要四舍五入。不然会因为精度炸掉。

Problem J

Solved by Weaver_zhu. 1:22 (+)

Problem K

Solved by Kilo_5723. 2:45 (+)