【题解】Wannafly挑战赛3
（题解由比赛出题人提供，点击右侧“本文相关内容”的题目即可开始做题）
T1 珂学送分
用f[i]表示[i…n]这段子序列可以切成的期望段数，对于每个i，我们可以找到一个最大的j，使得[i…j]这段的和不超过x，那么有+1。随着i的减小，其对应的j也会减小，所以可以用一根单调的指针维护j。f[i]的计算有一个后缀和解决。
找到A的车的挡位的最快速度和最慢速度，那么他和B之间的相对速度就是（B的速度+A的速度），用总距离除以最快和最慢的速度，分别计算即可。注意单位之间的转换，1m/s=3.6km/h。
设bit(x)为x在十进制下的位数，那么
T4 蝴蝶
T5 迷宫
首先证明从树上的点x走到点y的期望为
对于一颗子树来说，$ E（x y）=2size(x)-1其次不难发现路标一定全放在S到T的路径上。
用f[i][j]表示前i个点用了j个路标的情况下达到i最少的期望步数。考虑到j+1个点放在k的情况，对于[i+1…k]中的点x，有
然而因为在i点有个路标，，总体考虑。
其他疑问可加以下交流群（加入一个即可啦~）
牛客多校算法训练营1：453799454
牛客全国算法训练营2：330766563
牛客多校算法训练营3：934889305
牛客多校算法训练营1：453799454
牛客全国算法训练营2：330766563
牛客多校算法训练营3：934889305
腾讯开奖334人在聊