2019 Multi-University,Nowcoder Day 2

Problem A

Solved by Weaver_zhu && Kilo_5723. 01:36:01 (+2)

题意：给出一个环的大小，从0开始，每次随机向两个方向之一走一步，求走到m的期望

题解：起手蒙特卡洛就找到答案了，但是没看到前缀积（英语白学了，也没看到有人过，于是就扔了。还好有Kilo和机房后面队伍的欢呼声救场（逃

Problem B

Upsolved by Kilo_5723.

Problem C

Unsolved.

Problem D

Unsolved.

Problem E

Unsolved.

Problem F

Upsolved by Weaver_zhu. (-1)

Problem G

Unsolved.

Problem H

Solved by Xiejiadong. 03:43:42 (+2)

题意：求全 $1$ 的次大矩阵面积。

题解：考虑最大矩阵如何做，对于每一行考虑这一行作为底的最大矩形面积。

这个就变成了经典的最大广告牌问题，用单调栈维护每个位置向左向右最多能拓展的长度，即可算出最的矩形。

对于次大的矩形，考虑裁掉最大矩形的四个角，在分别算最大的矩形面积，取这四个中的较大值即可。

脑子不动，暗示 Weaver_zhu 写了不知道多少个小时的三分，于是这题爆炸了。

Problem I

Unsolved.

Problem J

Solved by Kilo_5723. 04:37:15 (+6)