2024.10.16 题目

题解：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(\mathrm{mod}3)$，则可以将 $n$ 改为 $\frac{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 _{j=S_i}\mathrm{dis}(i,j{)}^2$ 的值，其中 $S_i=\{j\in Z|\max (1,i-1)\le j<i\}\cup \{0\}$，$\mathrm{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$。求牛牛在工作完成的时刻，开心度可以达到的最大值。