【题解】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_{k=i+1}^{j+1} f[k] /(j-i+1)+1$

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

T4 蝴蝶

枚举中间点，暴力枚举四个方向扩展的长度再用前缀和的手段判断左右两条直线是否全由 $X$ 或 $O$ 填充，复杂度 $O(n^2)$

T5 迷宫

首先证明从树上的点 $x$ 走到点 $y$ 的期望为

$\mathrm{E}(\mathrm{x} \rightarrow \mathrm{y})=1+\sum_{z,(\mathrm{x}, \mathrm{z}) \in \mathrm{E}, \mathrm{z} \geq \mathrm{y}}(E(z \rightarrow x)+1)$ ，其中下标的 $E$ 表示边集；

令 $D=x$ 的度，

$\mathrm{E}(\mathrm{x} \rightarrow \mathrm{y})=\frac{1}{D}+\frac{\sum_{z,(\mathrm{x}, \mathrm{z}) \in \mathrm{B}, \mathrm{z} \mid=\mathrm{y}}(E(\mathrm{z} \rightarrow x)+1+E(x \rightarrow y))}{\mathrm{D}}$

$\frac{\mathrm{E}(\mathrm{x} \rightarrow \mathrm{y})}{\mathrm{D}}=\frac{1}{D}+\frac{\Sigma_{z,(\mathrm{x}, \mathrm{z}) \in \mathrm{E}, \mathrm{z} \mid=\mathrm{y}}(E(\mathrm{z} \rightarrow x)+1)}{\mathrm{D}}$

对于一颗子树来说， $E（x \rightarrow y）=2size(x)-1$ 其次不难发现路标一定全放在 $S$ 到 $T$ 的路径上。

用 $f[i][j]$ 表示前 $i$ 个点用了 $j$ 个路标的情况下达到i最少的期望步数。考虑到 $j+1$ 个点放在 $k$ 的情况，对于 $[i+1…k]$ 中的点 $x$ ，有 $E(1→x+1)=E(1→x)+E(x→x+1)$

然而因为在 $i$ 点有个路标， $E(x→x+1)=2∗(size(x)−size(i))+1$ ，总体考虑。

$\begin{aligned} \mathrm{f}[\mathrm{k}][\mathrm{j}+1]=& \min \left(f[i][j]+\sum_{x=i}^{k-1} E(x \rightarrow x+1)\right) \\ &=\min \left(f[i][j]+\sum_{x=i}^{k-1}(2 *(\operatorname{size}(\mathrm{x})-\operatorname{size}(\mathrm{i}))+1)\right.\\ &=\min \left(f[i][j]+2 \sum_{x=i}^{k-1} \operatorname{size}(x)-2(k-i) \operatorname{size}(i)+k-i\right) \end{aligned}$