H
哥德巴赫
J
诈骗
A
签到
D
要么全 \(0\)， 要么全 \(1\)
B
不得不说我真的纯纯 SB 真的。
考场做法是先转成概率， 然后就是计算长度大于等于 \(i\) 概率之和。
\(f(i, j, 0/1)\) 前 \(i + j\) 个位置填 \(i\) 个小于等于 \(n\) 的数， \(j\) 个大于 \(n\) 的数， 最后一段是上升/下降的概率， 每次交替加入一段小于 \(n\) 的上升的数， 一段大于 \(n\) 的下降的数即可， 最后的结果是概率之和乘上阶乘吗也就是期望乘阶乘。因为不能做除法， 把阶乘提前乘一下就行了， 考试忘记提前乘重构代码去算半天， 我是傻逼。
E
支配树， 6
考试没看， 看了也不记得支配树咋玩了得拉板子
一眼最短路树建出来， 然后考虑每条边 \(u \to v\) 。
如果 \(dep[u] < dep[v]\) 啥事没有。
如果 \(dep[u] = dep[v]\) 那 \(v\) 就可以通过 \(u\) 到达， 距离错误。
如果 \(dep[u] > dep[v]\) 那如果 DFS 可先到 \(u\) 再去 \(v\) 则可能错误， 判 \(v\) 是否是支配点即可。
I
被这个 60 骗了。
其实拆成路径长度和颜色切换次数， 前者直接算就行， 后者倍增树上维护一下完事。 懒得写了。
这个 \(60\) 我还以为是什么高妙的矩乘优化。
F
超， 怎么刚准备翻题解就会了。
好像对值域分治， 每次暴力处理中间 \(9\) 个点的答案， 然后左右分别分治下去就完事了。
超， 我是伞兵没看这个题。码速还是拉了。
G
不会， 看眼题解。
题解啥玩意， 咕一下
C
voronoi图算法 c++
好像是有点用的板子， 但是找不到资料学啊。
标签：概率,dep,题解,多校,Day3,牛客,阶乘 From： https://www.cnblogs.com/clover4/p/17578574.html