2018 Multi-University, Nowcoder Day 5

From EOJ Wiki
Jump to navigation Jump to search

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 D

Unsolved. (-1)

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)

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

温暖的签到。