【题解】Wannafly挑战赛3

（题解由比赛出题人提供，点击右侧“本文相关内容”的题目即可开始做题）

T1 珂学送分

用f[i]表示[i…n]这段子序列可以切成的期望段数，对于每个i，我们可以找到一个最大的j，使得[i…j]这段的和不超过x，那么有 $\sum_{k=i+1}^{j+1}{f[k]/(j-i+1)}$ +1。随着i的减小，其对应的j也会减小，所以可以用一根单调的指针维护j。f[i]的计算有一个后缀和解决。

T2 遇见

找到A的车的挡位的最快速度和最慢速度，那么他和B之间的相对速度就是（B的速度+A的速度），用总距离除以最快和最慢的速度，分别计算即可。注意单位之间的转换，1m/s=3.6km/h。

T3 位数差

设bit(x)为x在十进制下的位数，那么 $\sum_{1\leq i<j\leq n}^{n}{bit(ai+aj)-\sum_{i=1}^{n}{(n-i)bit(ai)}}$

$\sum_{i=1}^{n}{(n-i)bit(ai)}$ 可以在读入的时候算好，而计算 $\sum_{1\leq i<j<n}^{}{bit(ai+aj)}$ ，其实和a数组里元素的顺序没什么关系，所以可以把数组a排序后从大到小枚举每个a，考虑比a小的数a加上去的情况，位数要不不变，要不就加1，二分不变和加一的临界点即可。