题解：[[2024.10.16 模拟赛]] ## 最终测试 #树状数组 #概率与期望 $n$ 名选手正在参加比赛，第 $i$ 名选手作答了两道题，分值为 $a_{i,1}$ 与 $a_{i,2}$，每道题有 $50\%$ 的正确概率，求每个选手最终排名的期望，误差不超过 $10^{-6}$。选手的排名定义为比他分数高的人数 $+1$ 的值。 ## 空间跳跃 #冰雹猜想 #模拟 给定正整数 $d,l$，初始有整数 $n=1$，可以做以下三种操作： - 将 $n$ 改变为 $2\times n$； - 若 $\min(|n|,|n-d|)\le l$，可以将 $n$ 改为 $n-d$； - 若 $n\equiv 1\pmod 3$，则可以将 $n$ 改为 $\cfrac{n-1}{3}$。 $q$ 次询问，每次询问给出目的地 $x$，求变换方案使得 $n=1$ 最终能够变换为 $x$。输出方案，变换次数不能超过 $1500$ 次。 ## 快速访问 #树链剖分 #线段树 有 $n+1$ 个结点的树，结点编号为 $0,1,\cdots,n$，第 $i$ 条边连接 $u_i$ 与 $v_i$。求对于 $i$ ${} (1\le i\le n) {}$，$A_i=\sum\limits_{j=S_i}\operatorname{dis}(i,j)^2$ 的值，其中 $S_i=\{j\in ℤ|\max(1,i-1)\le j<i\}∪\{0\}$，$\operatorname{dis}(i,j)$ 为 $i$ 到 $j$ 的简单路径经过的边的数量。 ## 门童 #序列dp 牛牛去当志愿者。大厅沙发和大门距离为 $L$ 个单位，牛牛在每秒可以做以下事： - 站在门口不动，开心度每秒减少 $x_1$； - 从门口走向沙发一个单位，开心度每秒减少 $x_2$； - 从沙发走向门口一个单位，开心度每秒减少 $x_3$； - 在沙发上摸鱼，开心度每秒增加 $x_4$。 有 $n$ 名选手需要牛牛接待，第 $i$ 名选手会在第 $t_i$ 秒到达大门，它的耐心值为 $p_i$，友善值为 $f_i$，牛牛必须要在任意时刻 $T$ $(t_i\le T\le t_i+p_i)$ 接待，接待瞬间完成，开心值会在接待的瞬间上升 $f_i\times(t_i+p_i+T)$。 牛牛在第 $0$ 秒站在门口，开心度为 $0$。求牛牛在工作完成的时刻，开心度可以达到的最大值。