XVII Open Cup named after E.V. Pankratiev. XXI Ural Championship

From EOJ Wiki
Jump to: navigation, search

Problem A

Solved by Xiejiaodng. 0:23 (+)

题意:判断给出的图是不是一个环 + 一条链。

题解:找到环和链的转折点,一定是一个度数为 $3$ 的点。

找到度数为 $1$ 的点一定是链的一段,从这个点出发到度数为 $3$ 的点然后在把环标记一遍。

去掉不联通的情况,去掉各种细节即可。

Problem B

Solved by Xiejiadong. 2:46 (+1)

题意:给出两个对于坐标轴散点的柱形统计图,判断能够通过同一个散点分布得到。

题解:因为没有散点在坐标轴的定义域外面,所以前缀和处理以后,开始端点 $b$ 处一定是 $0$ ,通过这个可以推断出所有前缀和位置的和。

判断是否有冲突,是否有靠后的位置小于前面(要保证非负)的即可。

Problem C

Upsolved by Xiejiadong. (-6)

题意:配置一个 mass 在 $[min,max]$ 范围内的东西,使得能够得到这类东西的数量最大。

题解:dp 显然 $f[i]=max(min(f[i-mx],c/x))$ 。

考虑把所有质量相同的东西压在一起处理,时间复杂度 $O(n^2logn)$ 。

被题意杀了。

Problem D

Unsolved. (-5)

Problem E

Unsolved.

Problem F

Unsolved.

Problem G

Solved by Weaver_zhu. 0:51 (+1)

Problem H

Solved by Kilo_5723. 4:13 (+)

Problem I

Unsolved.

Problem J

Unsolved.

Problem K

Solved by Kilo_5723. 0:51 (+)

Problem L

Unsolved.

Problem M

Unsolved.