2018 Multi-University, Nowcoder Day 5

Problem A

Solved by ultmaster. 00:25 (+)

题意：要求删掉 $k$ 门课程的成绩使得加权平均分最大。

题解：二分答案，移项后判断式子是否大于 0 即可。

Problem B

Upsolved by ultmaster.

题意：$n$ 是好数，当存在 $x \in [n^2+1,n^2+2n]$ 满足 $x | n^4$。求比输入大的最小的好数。

题解：$n^4 = (n^2-x)(n^2+y)$ 展开得到 $(y-x)n^2 = xy$。由于 $y \le 2n$，$y-x$ 只能是 1 或 2 或 3。下面分别讨论。

$y-x=1$ 时，方程无解。（没有严格证明过）

$y-x=2$ 时，$2n^2 = x(x+2)$，即 $(x+1)^2-2n^2=1$。解该佩尔方程得到 $n$ 的递推式是 $a_n = 6 a_{n-1} - a_{n-2}$。

$y-x=3$ 时，$(2x+3)^2 - 12n^2 = 9$。得到 $n$ 的递推式是 $a_n = 14 a_{n-1} - a_{n-2}$。

暴力算一算就好了。

佩尔方程小课堂：佩尔方程千万不要去推（虽然推起来很有趣，但结果不一定好看，会是两个式子）。记住佩尔方程结果的形式通常是 $a_n = k a_{n-1} - a_{n-2}$（$a_{n-2}$ 前的系数通常是 $-1$）。暴力 / 凑出两个基础解之后加上一个 0，容易解出 $k$ 并验证。一般的话还可以找规律得到，但本题由于是两个序列并在一起，规律并不容易发现。

特别鸣谢：本题题解和佩尔方程小课堂由 oxx 友情提供。

Problem C

题意：给定一张 n 个点 m 条边的无向图，对于每个边集的子集 S，假设这个子集作为边的话，这张图的连通块个数为 k[S]，求 $\sum_S k[S]^{k[S]-1}$。

题解：

虽然出题人的本意是要把 $x^{x-1}$ 看做 $x$ 个点的有根树个数，但是姑且不考虑这个，而是求出满足对于所以 $x$， $k(S)=x$ 的 $S$ 的个数。

$g(S)=2^{e(S)}$，其中 $e(S)$ 表示顶点集 $S$ 的导出子图中边的条数。

先求出 $f(S) = \sum_{T\subseteq S} g(S)$，用高维前缀和或者 FWT 都可以。定义乘法为子集卷积，$f^n(S)$ 的含义是 $S$ 导出子图的边集中至少有 $n$ 个联通块的方案数。

设 $h(n)=f^n(U)$，$h'(n)$ 为恰好 $n$ 个联通块的方案数。那么 $h'(x)=h(x)-\sum_{i>x} h'(i) S(i,x)$，其中 $S$ 是第二类斯特灵数。

实现过程中由于要子集卷积，所以还要按二进制中 1 的个数分离，计算 $h(n)$ 时还需要一次容斥。

Problem D

Upsolved by kblack. (-1)

题意：往一个指定偶数排列里面插入保持顺序的奇数，求产生的最少逆序对数。

题解：往哪里插入可以随便维护，题解说最优插入位置一定递增，证不来，我们就假装的确是这样吧 QAQ。

Problem E

Solved by zerol. 00:49 (+)

题意：给一些无序的无序四元组，要求变成目标，求最少的需要改变位置的元素。

题解：KM。定义两个之间的匹配值是四元组的交的个数，然后跑二分图最大匹配。

Problem F

Solved by ultmaster. 02:14 (+)

题意：每一个数 $d_i$ 有 $p_i$ 的概率出现，求贪心的上升序列的长度的期望。

题解：从 $1$ 到 $n$ 用 $p$ 和 $d$ 反复更新两个数组。$a_k$ 表示序列以 $k$ 结尾的概率；$b_k$ 表示序列以 $k$ 结尾的情形下答案的期望（不是条件期望，就是直接贡献答案的）。

FOR (j, 0, d) {
    b[d] += (b[j] + a[j]) * p;
    b[j] = b[j] * prev;
}
FOR (j, 0, d) {
    a[d] += a[j] * p;
    a[j] = a[j] * prev;
}

答案是 $b$ 数组的和。

下面优化这个过程：发现大概涉及到下面的操作：区间乘，单点加，区间查询。用线段树就可以。单点加的时候直接暴力 pushdown 下去。没有优化，卡着时限过了。

ultmaster: 绝对是做烦了，因为题解只要一个树状数组就好了。

Problem G

Solved by kblack. 00:14 (+1)

温暖的签到。

Problem H

Solved by zerol. 02:52 (+1)

题意：求一个数列的下标字典序第 k 小的上升子序列。

题解：预处理出每个下标开始的上升子序列个数，然后一位一位确定即可。

Problem I

Solved by kblack. 01:17 (+1)

题意：求一个点集有多少非空子集 $S$ 使得 $S$ 的每个子集都能被一个长条 $\{(x,y)|x \geq a, l \leq y \leq r\}$ 切出来。

题解：3 个点必须是 < 形状，所有大于 3 个点都布星。一个点直接算，其他情况枚举第二个点，搞个树状数组维护一下就好了。

Problem J

Solved by kblack. 00:08 (+)

温暖的签到。