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)}{\rm d}x$。
题解:可以把分式的连乘转换成分式的和,再分别积分。
我们发现,$\prod_{i=1}^n(a_i^2+x^2)=\sum_{i=1}^{n}\frac{1}{(x^2+a_i^2)\prod_{j=1}^n(a_j^2-a_i^2)(j!=i)}$。
利用此性质,将乘积的积分转换成积分的和,易解。
Problem C
Solved by Kilo_5723. 04:12:29 (+1)
题意:给定一个 $n$ 维空间中的点 $(a_1,a_2,\dots,a_n)$,求一个点 $(p_1,p_2,\dots,p_n)(\sum_{i=1}^n p_i=1,a_i>=0)$,使得两点距离最短。
题解:显然,若没有 $p_i>=0$ 的限制,使得每一个 $a_i=p_i$ 相等即可。但加上限制之后,为了最小化影响,应该对 $>0$ 的 $p_i$ 均等的减少一定量的值补给 $<0$ 的缺口。
一种实现方法是:对 $p_i$ 进行排序,统计 $<0$ 的 $p_i$ 的和。从小到大遍历 $>0$ 的 $p_i$:
如果 $p_i$ 小于将当前的缺口平均分摊给每一个正数的均摊值,说明 $p_i$ 要被减到 $0$,将缺口减去 $p_i$。
否则,对于当前的 $p_i$ 以及之后的每一个 $p_i$,均摊缺口。
由于要求输出分数,运算过程中分子分母的大小可能超过 long long 能存储的范围,但答案没有超出范围,用 __int128 存储即可。
Problem D
Unsolved.
Problem E
Solved by Kilo_5723. 02:25:19 (+)
题意:求长度为 $2(n+m)$ 的 $01$ 序列,使得其中恰好能取出不一定连续的 $n$ 个 $01$ 和 $m$ 个 $10$。
题解:先考虑给定一个序列,如何判断其是否能取出 $n$ 个 $01$ 和 $m$ 个 $10$。我们发现,可以贪心的将新读到的数作为端口 $0-$ 或 $1-$,直到对应的端口数量已经满足要求,需要和对应的另一种端口 $1-$ 和 $0-$ 匹配成 $10$ 和 $01$。如果过程中另一种端口的数量不足,则给定序列不满足性质。
根据这种方法,我们可以将加入字符看作是在平面上移动的过程。初始位置为 $(0,0)$,我们要向右或向上走,到达 $(n+m,n+m)$。根据贪心的准则,需要满足的限制条件就为 $-n \le x-y \le m$。将问题转换为在只能向右或向上走,且横纵坐标 $x,y$ 始终满足 $-n \le x-y \le m$ 的情况下,$(0,0)$ 到 $(n+m,n+m)$ 的路径条数。 $O(n^2)$ dp 求解。
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 就好了。