2018 Multi-University, Nowcoder Day 8

Problem B

Solved by OEIS. 01:12 (+)

Brute force by ultmaster.

题意：染棋盘上不同行不同列的 $n$ 个格子，使得经过一系列两个相邻格子都染黑则染黑的操作之后，所有格子都能染黑。

题解：$a_n = \frac{1}{n} \sum_{k=0}^n 2^k \binom{n}{k} \binom{n}{k-1}$。

Problem E

Solved by ultmaster. 03:12 (+)

题意：一个棋盘，只能上下左右走，有一些航班。求最小遍历路径（起点和终点都是左上角）。

题解：显然如果棋盘的任何一边是偶数的话，答案就是 $nm$，如果两边都是奇数，容易构造出 $nm+1$ 的路径。下面考虑把这个 1 去掉。观察 / 打表所有的左上角起点的哈密尔顿通路可能的终点位置可以发现，这些终点位置在棋盘上是一个满足行加列模 2 为 0 的网格。努力感受一下大概能猜得到如果在两个这样的格子之间存在一个航班的话，可以从起点走出一条路径，终点走出一条路径，两条路径是不相干的。然后一下子就 AC 了。证明留给官方题解。

Problem G

Solved by kblack. 00:13 (+)

Problem H

Solved by zerol & ultmaster. 02:47 (+6)