Moscow Pre-Finals Workshop 2016. Kent Nikaido Contest 1.

From EOJ Wiki
Jump to navigation Jump to search

Problem A

Solvde by Xiejiadong. 0:14:51 (+)

题意:可以放入三种形态的四格子方块,判断其中两种放入次数的奇偶性。

题解:可以发现,如果从副对角线的位置看的话。第一种形态是 $(2,2)$ 的形式,其余两种形态都是 $(1,1,1,1)$ 的形式。

于是我们可以分别求出每一条对角线的奇偶性,因为 $(2,2)$ 显然不会影响奇偶性,于是可以得到其余两种状态所需要的次数。

Problem B

Solved by Weaver_zhu. 3:15:25 (+2)

Problem C

Solved by Kilo_5723. 2:54:10 (+1)

Problem D

Solved by Xiejiadong. 1:01:51 (+)

题意:要求从 $1$ 出发回到 $1$ ,且遍历每一条边至少一次的最小代价。

题解:因为这道题目的边权比较特殊,都是 $2^i$ 。

而显然,对于每一条边可以做到最多只走两次,于是就可以发现,重复走的边一定是在 MST 上的。

跑出 MST ,判断每一条边是否需要走两次,对于需要走两次的边,一定满足被这条边分成两半的树上节点中,至少有一部分有奇数个度数为奇数的点。

Problem E

Unsolved.

Problem F

Unsolved.

Problem G

Unsolved.

Problem H

Solved by Kilo_5723. 1:09:28 (+1)

Problem I

Unsolved.

Problem J

Solved by Kilo_5723. 0:52:40 (+)

Problem K

Solved by Kilo_5723. 0:28:47 (+)