T1 珂学送分
用表示这段子序列可以切成的期望段数,对于每个,我们可以找到一个最大的,使得这段的和不超过,那么有。随着的减小,其对应的也会减小,所以可以用一根单调的指针维护。的计算有一个后缀和解决。
T2 遇见
找到A的车的挡位的最快速度和最慢速度,那么他和B之间的相对速度就是(B的速度+A的速度),用总距离除以最快和最慢的速度,分别计算即可。注意单位之间的转换,1m/s=3.6km/h。
T3 位数差
设为在十进制下的位数,那么
可以在读入的时候算好,而计算 ,其实和a数组里元素的顺序没什么关系,所以可以把数组排序后从大到小枚举每个,考虑比小的数加上去的情况,位数要不不变,要不就加,二分不变和加一的临界点即可。
T4 蝴蝶
枚举中间点,暴力枚举四个方向扩展的长度再用前缀和的手段判断左右两条直线是否全由或填充,复杂度
T5 迷宫
首先证明从树上的点走到点的期望为
,其中下标的表示边集;
令的度,
对于一颗子树来说,其次不难发现路标一定全放在到的路径上。
用表示前个点用了个路标的情况下达到i最少的期望步数。考虑到个点放在的情况,对于中的点,有
然而因为在点有个路标,,总体考虑。
用这个斜率优化一下就可以了。
全部评论
(0) 回帖