2024.10.20 题目

题解：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\leftarrow j$）。牛牛每天至少睡觉 $k$ 分钟，这 $k$ 分钟不能有人吵闹。请问想让牛牛满足要求需要花费的最小代价是多少？

路径难题

最短路 图

一座城市有 $n$ 个点，编号为 $1\sim n$，由 $m$ 条无向边连通，第 $i$ 条边连通 $u_i$ 和 $v_i$，距离为 $d_i$。有出租车可以从任意结点坐到任意结点，行走 $p$ 距离收费 $\lfloor \frac{p}{r}\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$ 取模。