CTU Open Contest 2019

From EOJ Wiki
Jump to navigation Jump to search

Problem A

Solved by Kilo_5723. 00:36 (+5)

题意:求在所有由 $A$ 和 $B$ 组成的 $K$ 位数中,$C$ 出现的次数。

题解:如果 $C\neq A$ 且 $C \neq B$,则不会出现。

否则如果 $A=B$,则出现 $K$ 次。

否则,出现 $K \times 2^{K-1}$ 次。

Problem B

Solved by Xiejiadong. 02:34(+)

按照题目意思计算即可。

题目却是比较难理解,看着样例大概猜了猜。

Problem C

Solved by Kilo_5723. 03:04 (+3)

Problem D

Solved by Xiejiadong. 04:08 (+)

题意:删掉尽可能多的边,使得每个点都从源点能到,能到汇点。

题解:考虑最坏情况下,每个点都需要一条出边和入边(除了源点和汇点),也就是需要 $2n-2$ 条边。

但是图中存在的某些边可以减少这样的边,即本来需要 $a-$ 汇点 以及 $b-$ 汇点,但现在可以通过 $a-b-$ 汇点来减少所需要的边。

显然这样的一组关系可以减少一条边。

考虑把所有的点拆成入点和出点,于是在上述要找尽可能多的关系,其实就是二分图匹配。

Problem E

Solved by Weaver_zhu. 03:37 (+1)

Problem F

Solved by Kilo_5723. 02:05 (+1)

Problem G

Solved by Kilo_5723. 01:33 (+2)

Problem H

Solved by Xiejiadong. 02:53 (+2)

相对比较大的模拟题。时间顺序比较难处理(主要是题目没讲清楚)。

Problem I

Solved by Weaver_zhu. 4:07 (+3)

Problem J

Solved by Weaver_zhu. 02:20 (+)