题解：[[2024.10.20 模拟赛]] ## 袜子分配 #数学 #找规律 #概率与期望 有 $n$ 双袜子，随机取 $n$ 次，每次抽出随机两只袜子，如果两双袜子正好是一双就开心一次，求随机 $n$ 次的开心次数期望，与答案误差小于 $10^{-8}$。 ## 艰难睡眠 #单调队列 #序列最大值查询 每天有 $m$ 个时间单位，有 $n$ 个人，第 $i$ 个人默认在 $[a_i,a_i+b_i-1]$ 这段时间吵闹。可以花费 $c_{i,j}$ 的代价让第 $i$ 个人到 $j$ 的时间吵（即让 $a_i\gets j$）。牛牛每天至少睡觉 $k$ 分钟，这 $k$ 分钟不能有人吵闹。请问想让牛牛满足要求需要花费的最小代价是多少？ ## 路径难题 #最短路 #图 一座城市有 $n$ 个点，编号为 $1\sim n$，由 $m$ 条无向边连通，第 $i$ 条边连通 $u_i$ 和 $v_i$，距离为 $d_i$。有出租车可以从任意结点坐到任意结点，行走 $p$ 距离收费 $\left\lfloor\cfrac{p}{r}\right\rfloor$ 元，多次乘坐多次收费。还有 $k$ 路公交车，第 $i$ 路公交车有 $t_i$ 个站台，在任意两个站台之间乘坐公交车花费 $c_i$。给定 $q$ 次询问，每次询问为 $(s,t)$ 的格式，求 $s$ 到 $t$ 最少需要花费的钱数。 ## 牛半仙的妹子序列 #序列dp #线段树 有 $n$ 个妹子，魅力值为 $1\sim n$。牛半仙会选择若干个妹子组成序列 $\{p_1,p_2,\cdots,p_m\}$，当且仅当他是一个上升序列，不存在 $j$ 使得 $j>p_m$ 且 $v_j>v_{p_m}$，不存在 $j$ 使得 $j<p_1$ 且 $v_j<v_{p_1}$，且不存在 $j$ 使得 $p_i<j<p_{i+1},v_{p_i}<v_j<v_{p_{i+1}}$。求选择序列的方式，答案对 $998244353$ 取模。