2024.10.6 题目

题解：2024.10.6 模拟赛

喷泉

数学 几何

给定点 $A,B,C$ 的坐标，有动点 $P$ 在 $AB$ 上运动，求 $PC+r$ 的最大值与 $PC-r$ 的最小值。

红绿灯

模拟 最大公因数

有 $m$ 个红绿灯需要经过，第 $i$ 个红绿灯周期为 $a_i$ 秒，这代表着该红绿灯只会在秒数为 $a_i$ 的倍数时亮绿灯。给定 $n$，求时刻 $j\in [1,n]$ 开始，通过红绿灯后的时刻为多少。

子集

背包dp 集合 快速幂 乘法逆元

对于集合 $S$，定义 $F_0(S)=\left[\sum _{s\in S}s=M\right],F_k(S)=\sum _{s\in S}{F}_{k-1}(T)(k>0)$。给定集合 $S=a_1,a_2,\cdots ,a_n$ 和 $M,k$，求 $F_k(S)$ 对 $10^9+7$ 取模的值。

佛怒火莲

二分 随机化

有 $N$ 堆火焰，第 $i$ 堆火焰的属性为 $a_i$，不稳定度为 $b_i$。需要选择 $k$ 种属性不同的火焰，假设排序后的数组为 $b$，那么其威力为 $\underset{i=2}{\overset{k}{\min }}|b_i-b_{i-1}|$。求最大威力。