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 C

Upsolved by zerol.

题意：有点复杂。给定一棵树，求对于所有联通块的 f 之和。定义 f 是路径的集合数量，使得每条路径与联通块没有交点，而且联通块周围一圈都至少被覆盖了一次。

题解：枚举联通块的 LCA （也就是联通块深度最小的那个点）。假设联通块已经确定，那么 f 就是被联通块截下来的所有子树 u 的 $2^{\binom{sz(u)}{2}}- 2^{\sum_{fa(v)=u} \binom{sz(v)}{2}}$ LCA 上面的也应该看成一棵子树，只是这部分可以另外算。$dp[u]=\prod dp[v] + 2^{\binom{sz(u)}{2}}-\sum_{fa(v)=u} 2^{\binom{sz(v)}{2}}$，如果不考虑 LCA 之上的，那么 $ans[u]=\prod dp[v]$。dp[u] 的含义是，u 的父亲必须选，u 的子树中合法的路径集合数。最后考虑 LCA(u) 上面的，预处理出 $sum[u]=\sum \binom{sz(u)}{2}$，那么 fa(u) 的贡献是 $2^{\binom{n-sz(u)}{2}}- 2^{\sum_{fa(v)=fa(u)} \binom{sz(v)}{2} - \binom{sz(u)}{2} + \binom{n - sz[fa(u)]}{2}}$。

Problem E

Solved by ultmaster. 03:12 (+)

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

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

Problem G

Solved by OEIS. 00:13 (+)

Guessed by kblack.

温暖的签到。

Problem H

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

题意：求一个多重集的最大子集使其异或和为 0。

题解：反过来考虑求一个最小子集使其异或和为 $S$。转换成一个最短路问题。点是所有 $2^n$ 个数，每个点都能伸出 $n$ 条边。跑 BFS。一度怀疑均摊复杂度是对的（直到 TLE 了）。

需要一点小优化：比方说最后一步预先开个数组直接查，所有数随机化防卡。事实上跑得还很快（怀疑是不是真的能卡得掉）。