【题解】牛客练习赛46
A:华华教奕奕写几何
设大半圆半径为r,两个小半圆的半径为r1,r2。
则有：2*s=π*(r*r-r1*r1-r2*r2) ①
r=r1+r2 ②
两式联立得r=r1+s/(π*r1)
可以把r1看作自变量，r看作因变量，对r1求导，即可得r的最小值。
B:华华送奕奕小礼物
设sum_a为a的前缀和，sum_b为b的前缀和。则以(x1,y1)为左上角，以(x2,y2)为右下角的矩阵的权值为(sum_a[x2]-sum_a[x1-1])*(sum_b[y2]-sum_b[y1-1])，其中要满足x1<=x2,y1<=y2。x1,x2的选择与y1,y2的选择相互独立。可以预处理所有y1,y2的组合，然后排序。接下来枚举x1,x2，对y二分即可。复杂度n^2*log(m^2)
C:华华跟奕奕玩游戏
设a[i]为进行了i轮游戏黑球个数的期望，则a[0]=n。
a[i+1]=
化简后得a[i+1]=，到这里可以直接矩阵快速幂求解。也可以继续推到。令s=
,则
a[0]=n
a[1]=s*n+p*s=n*s+p*s
a[2]=s*a[1]+p*s=n*s^2+p*s^2+p*s
a[3]=s*a[2]+p*s=n*s^3+p*s^3+p*s^2+p*s
不难得出a[k]=n*s^k+p*(s^1+s^2+...+s^k)
D:华华陪奕奕打怪兽
二分时间。后面贪心的选择攻击策略。对于二分出来的时间t,因为a是循环数组，对于每个i,1<=i<=n,可以算出最大的整数d,使得i+d*n<=t,实际上可以看作a[i]*b[j]可以使用d次。可以把所有的a[i]*b[1]存在一个优先队列，每次取最小，次数用光后在放入a[i]*b[2],知道C或W小于等于0。
E:华华和奕奕学物理
若某一时刻a球比b球速度快，则a球始终比b球速度快。取T=300000。对于1操作 v1,t1,m1。可以算出V1=v1+g*(T-t1)。对于2操作，可以算出V2=v2+g*(T-t2)。则需要查询的小球即是满足V1<=V2的小球。然后根据公式m1*(v1+g*(t2-t1))^2,拆开，维护6个树状数组即可。
F:华华和奕奕的旅行
考虑若没有1操作，对于2操作，若当前节点的水量不足，可以找父亲节点借水，若父亲节点处的水不够用，则找父亲的父亲，以此类推，直到水借够为止。经过这次操作后，这条路径上的水已经被借完了，所以这个点的子节点借水到这个点时，可以直接跳过这段路径。可以用并查集维护一下。对于每次1操作，可以重构一次树。
最后膜一发Tweetuzki，标程被打爆了。
查看6道真题和解析