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

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