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 (+)
温暖的签到。