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 了）。

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

Problem I

Upsolved by zerol.

题意：给一个数列，求一个排列，使得相邻两数之间的异或值的最大值最小，要求下标字典序尽可能小。

题解：首先求出相邻两数异或值的最大值的最小值。把所有数按照二进制中最高的不是所有数都一样的位的 0/1 分成两组，最优解的这一位的排列肯定有形如 000..01...11 的。其中一组往 trie 里插，另一组往 trie 里查，就能求出这个最小值了。然后问题转化成了一个求字典序最小的哈密顿路径，两组内部是完全图，两组之间有边当且仅当异或值恰好为之前求出来的最小值。每次贪心选取，但是要保证剩下的有解。一开始只考虑 1,2,3,4（下标），设上一个选的是 x，那么接下来考虑的是 x 所在这一组的剩下的最小值和次小值，以及另一组中与 x 相连的最小值。对于所有纳入考虑的，按从小到大依次检验合法性，合法只要满足一下任一条件：1.只有这一组了。 2.这一组只有一个了，而且自己和对面有边。 3.即便是去掉自己，两组之间仍然有边。至于这样为什么是对的/条件能否简化，就留给读者思考了。