2019 Multi-University,Nowcoder Day 1
Problem A
Solved by Kilo_5723. 00:20:52 (+)
题意:给定两个 $1$ ~ $n$ 的排列 $\{a_i\},\{b_i\}$,求最大的 $m$,使得 $RMQ(a,l,r)=RMQ(b,l,r)$ 对所有 $1 \le l \le r \le m$ 成立,其中 $RMQ(c,l,r)$ 是 $c_l,c_{l+1},\dots,c_r$ 中最小元素的下标。
题解:考虑对任意 $m$ 判断是否满足条件。我们发现,若 $RMQ(a,1,m) \neq RMQ(b,1,m)$ 则肯定不满足条件,否则对所有 $l \le m \le r$,$RMQ(a,l,r)=RMQ(b,l,r)$。此时对 $(l,m-1)$ 和 $(m+1,r)$ 递归求解就可以判断 $1~m$ 是否满足条件。
因此,对 $m$ 二分求解,就可以找到最大的 $m$。
Problem B
Upsolved by Kilo_5723. (-1)
题意:求 $\frac{1}{\pi}\int_0^{\infty}\frac{1}{\prod_{i=1}^n(a_i^2+x^2)}\d x$。
Problem C
Solved by Kilo_5723. 04:12:29 (+1)
Problem D
Unsolved.
Problem E
Solved by Kilo_5723. 02:25:19 (+)
Problem F
Solved by Kilo_5723. 00:50:00 (+)
题意:在一个三角形内随便散点,一次散点的价值是被分出来的最大三角形的面积,求随机散点的期望价值。
题解:小范围随机散点,蒙特卡洛找规律。
可以发现答案是 $22$ 倍的三角形面积。
Problem G
Unsolved.
Problem H
Unsolved.
Problem I
Unsolved.
Problem J
Solved by Xiejiadong. 00:07:33 (+)
题意:比较两个分数的大小。
题解:直接比较会爆 long long ,开 __int128 就好了。