2018 Multi-University, Nowcoder Day 6

Problem A

Solved by zerol. 00:34 (+)

题意：$2^n$ 个人按完全二叉树进行比赛，每轮用掉 n 个数中的一个，大的获胜，问胜者是谁。

题解：模拟。每次胜者用掉比对方最大的更大一些的数。

Problem B

Upsolved by ultmaster.

题意：树上有 $\binom{n+1}{2}$ 条路径，每次任意选一条路径染黑，问期望多少次把一棵白树染成全黑。

题解：官方题解答案是对的，但过程有问题。

记 $x_i$ 为随机变量：第 $i$ 个点染黑的时间。正确的容斥是这样的：

[math]\displaystyle{ \begin{align}ans &= E(\max_{1 \le i \le n} x_i) \\ &= \sum_{k=0}^{\infty} P(\max_{1 \le i \le n} x_i \ge k) \\ &= \sum_{k=0}^{\infty} \left( 1 - P(\max_{1 \le i \le n} x_i \lt k) \right) \\ &= \sum_{k=0}^{\infty} \left( 1 - P(x_1 \lt k \land x_2 \lt k \land \cdots \land x_n \lt k) \right) \\ &= \sum_{k=0}^{\infty} P(x_1 \ge k \lor x_2 \ge k \lor \cdots \lor x_n \ge k) \\ &= \sum_{k=0}^{\infty} \sum_{A \subseteq [n], A \neq \emptyset} (-1)^{|A|+1} P(\bigcap_{t \in A} x_t \ge k) \\ &= \sum_{A \subseteq [n], A \neq \emptyset} (-1)^{|A|+1} \sum_{k=0}^{\infty} P(\bigcap_{t \in A} x_t \ge k) \\ \end{align} }[/math]

由于 $\frac{P(\bigcap_{t \in A} x_t \ge k+1)}{P(\bigcap_{t \in A} x_t \ge k)}$ 是一个与 $k$ 无关的定值，所以后面那块就是一个等比数列求和，得到：

[math]\displaystyle{ ans = \sum_{A \subseteq [n], A \neq \emptyset} (-1)^{|A|+1} \left(1 - P(\bigcap_{t \in A} x_t \ge k) \right)^{-1} }[/math]

这个等比数列的公比其实就是，对于 $2^n - 1$ 个点集中的某一个点集，不经过这个点集的路径数量除以总路径数量（$\binom{n+1}{2}$）。也就是说这个点集把整棵树切成了若干个连通块，每个连通块（大小为 $s$）都会贡献 $\binom{s+1}{2}$ 条路径。同时我们注意到对于这个点集而言，我们只关心这个点集大小的奇偶性。所以可以用一个 S[i][j] 数组，表示有多少个点集，奇偶性为 $i$，且切剩下来的树上有 $j$ 条路径。利用 S 数组，不难算得答案。

那么怎么计算这个 S 数组呢？考虑树形 DP。f[i][j][k][p] 表示对于 $i$ 这棵子树，和根相连的没被点集切掉的连通块大小为 $j$，除了这个连通块里面的路径下面可能还有一些连通块里面的路径数量为 $k$，同时点集大小的奇偶性为 $p$。转移的时候考虑令 f[u][0][0][1] = 1（切掉根），f[u][1][0][0] = 1（不切掉根），然后逐一枚举子树进行类似背包的转移。注意从大到小枚举第二维和第三维向后转移的话，可以避免开两倍数组进行滚动；最后一维可能还是会存在冲突，特判一下就好。

非常容易写错且难以调试（果然还是不擅长树形 DP 呢）。复杂度据说是 $\mathcal{O} (n^5)$ 但是不会证，看起来真的像是 $\mathcal{O} (n^7)$ 除以很大的常数。

Problem C

Solved by ultmaster. 01:05 (+2)

题意：$S_n$ 是一个由 $1$ 到 $m$ 的数组成的集合，对于 $i<n$，$S_i \subseteq S_{i+1}$，求所有集合的方案数。

题解：(kblack 想出来的) 先枚举集合的大小，只要计算集合大小上升的位置的方案数。这是 $\binom{n-1}{x-1}$ 如果上升了 $x-1$ 次的话。如果上升了 $x-1$ 次，那么枚举的具体数字的数量是 $P(m,x)$。所以答案是 $\sum_{x=1}^{\min(n,m)} \binom{n-1}{x-1} P(m,x)$。处理边界的时候要小心一点。

ultmaster: Case 没写 WA1。

Problem D

Solved by zerol. 00:17 (+)

题意：给一个二分图，左边对右边是一对多，右边对左边是一对一，问最大权匹配。

题解：签到。对于右边每一个，选最大的左边进行匹配。

Problem E

Upsolved by ultmaster.

题意：初始给一个字符串，对于每一个可能的字符都定义一个字符串（长度大于 1），每一秒后，字符串中每一个字符都会替换成那个字符对应的字符串。问最少几秒后模式串会出现在该串内？

题解：首先可以观察到至多 10 秒后，一个字符就会变成一个长度超过模式串的字符串。所以讨论下面两种情况：

1. 模式串在 10 秒内就出现了。

2. 考虑 $ans-t$ ($t \le 10$) 的情况。我们从最后出现的时间往前看几秒，这个模式串那时候一定还是一个字符或者两个相邻字符。

所以我们需要 BFS 跑出所有一个字符和相邻的两个字符第一次出现的时间。然后需要快速地知道某个字符 $i$ 经过 $j$ 秒成长出来的字符串，在已经匹配了 $k$ 个字符的前提下，匹配该字符串后会匹配多少个字符。记为 $f(i,j,k)$。注意到该功能与 KMP 上的 DFA 非常接近，只是用这个 $f$ 优化转移。计算的话，对于 $i$ 的展开式 $s_1,s_2,\ldots,s_k$，$f(i,j,k) = f\cdots f(s_3,j-1,f(s_2,j-1,f(s_1,j-1,k)))\cdots )$。注意把终态记为 -1 即时跳出。（因为目标是匹配，不是计数）另外暴力计算 $f$ 是不可行的，因为 10 秒内有的字符可能会变得很长很长。

上面的两种情况，一种直接可以用 $f$ 快速地处理好，另外一种在 BFS 之后也可以处理。BFS 的时候要注意 $n=1$ 的情况，如果刚开始只有一个字符，要手动地展开一步，把相邻的字符添加到 "两个字符" 的队列里去。

Problem F

Solved by ultmaster. 03:27 (+2)

题意：给一棵有根树，叶子上每个节点都是随机的 0 和 1。每个非根节点上有 16 种真值表，要求选择适当的真值表使得所有节点的取值的组合得到的 1 节点的值的和最大。

题解：对于每个点，维护两种套餐，一种是 1 的个数最多，一种是 0 的个数最多。然后暴力转移一下就好了。需要高精，上了个 python。没加 Case 再次 WA1。还有递归爆炸（发现根本不用递归）。

Problem G

Solved by zerol. 03:49 (+2)

题意：给一棵树 T，并由此生成图 G，G 两点之间的容量定义为在 T 中的距离。问对于所有的点对在 G 中的最大流的和。

题解：发现 u，v 的最大流就是 min{与 u 相邻的边的容量和，与 v 相邻的边的容量和}。然后处理出每个点到所有点的距离和并排序即可。注意会爆 long long。

Problem H

Upsolved by kblack.

题意：给出 $c, z, m$，求满足 $a^x+b^y=c^z$ 且 $1 \leq a, b \leq m, 0 \leq x, y \leq m$ 的解数。

题解：当 $c^z = 1$ 时，解数为 $4m^2$，当 $a^x=1$ 或 $b^x=1$ 时，对于每个 $a^x=c^z$ 的合法解都有 $4m$ 个对应的解，至此退化的情况已经全部处理完毕。

$$ a = \prod{p_i^{d_i}} \\ b =\prod{p_i^{e_i}} \\ c =\prod{p_i^{f_i}} \\ d_ix+e_iy = f_i $$

$c$ 的素分解最多有 $6$ 个素数，也就是最多 $6$ 个方程，$m$ 内只包含 $c$ 的素因子的只有 $1848$ 个数，可以先枚举 $a$ 获得所有的 $d_i$，再枚举 $e_0$，然后分两种情况：若所有 $(d_i, e_i)$ 线性相关，可以用 $(d_i, f_i)$ 判断，用 extgcd 求一个解就能知道所有的解；否则枚举第一个不线性相关的方程的 $e_i$，可以得到唯一解，代入验证是否整数范围是否正确即可。

以上又是差不多把题解抄了一遍，细节挺多的，甚至卡常，差评。

Problem I

Solved by kblack. 03:18 (+5)

题意：给若干区间，查若干点，点碰到的区间全部删光，求删的情况，强制在线。

题解：借鉴 ST 表的思想，将一个区间分成两个长度为 2 的幂的区间按大小扔 set 顺便以左端点排序，查点的时候遍历长度，就知道哪些区间被碰到了，之后从 set 里面删掉这些区间。文件大小极大，需要输入输出优化。

Problem J

Solved by kblack. 00:29 (+2)

题意：生成 $10^7$ 的随机数，求 $ \max_{1 \leq i < j \leq n}{lcm(a_i, a_j)}$。

题解：由于是随机数，大概率互质，用 nth_element 找出最大的一些（比如100个），枚举一下就好了。

冰冷的签到。