2018 Multi-University, Nowcoder Day 5

Problem A

Solved by ultmaster. 00:25 (+)

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

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

Problem D

Unsolved. (-1)

Problem E

Solved by zerol. 00:49 (+)

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)

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 (+)

温暖的签到。