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.

题意：给出一个结构体，里面有一些成员占用 $1,2,4,8$ 个字节，要求每个成员的起始地址能被成员长度整除，而且最后一个成员会占用所有成员中最大的那个的字节，求结构体占用内存的极大极小和平均值。

题解：三个问题都能用五维 dp 解决，五维分别是占用 $1,2,4,8$ 剩下的成员个数以及当前末尾地址模 $8$ 的余数。

主要问题是卡内存，五维的 vector 刚好被卡掉，如果在函数内部开五维数组 dp[a][b][c][d][8] 就能过了。

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 (+)

题意：文明游戏，求一个点走到另一个点的最短怎么走。

题解：记录一个二元组表示回合数和当前回合已花费行动力，就可以用dij跑了

Problem K

Solved by Kilo_5723. 2:45 (+)

题意：给出地球自转轴和黄道面法向量的夹角 $\alpha$ 以及地球上一个点的 $A$ 的纬度 $\theta$。现在告诉你地球上另一个点 $B$ 与 $A$ 同经度且在赤道上，$B$ 在某一时刻穿过了黄道面并与 $A$ 在黄道面的两侧，求最快再过多久 $A$ 会达到自转周期中与黄道面距离的最小值。

题解：答案一定在自转四分之一周之内。在地球自转轴与黄道面经过地球中心的法向量形成的平面上建坐标系，这样就把三维的问题规约到了二维上。

设原点为地球中心，地球半径为 $1$，$y$ 轴为地球自转轴。在地球转过角度 $\beta$ 后，$A$ 在坐标系上的映射就是 $(\cos \theta \cdot \sin \beta,\sin \theta)$。只要判断其与黄道面法向量 $(-\sin \alpha,\cos \alpha)$ 的点积的正负就能判断 $A$ 此时是否经过黄道面。