2018 Multi-University, Nowcoder Day 6

Problem A

Solved by zerol. 00:34 (+)

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

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

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.

待补。

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 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个），枚举一下就好了。

冰冷的签到。