2024.10.6 模拟赛

题目：2024.10.6 题目

喷泉

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

---

首先，$P$ 到 $C$ 的最大距离非常好求，因为 $P$ 越靠向两边 $PC$ 就越大，因此 $P$ 只有在 $A$ 或 $B$ 上时最优，答案为 $\max (D(A,C),D(B,C))+r$，令 $D(x,y)$ 为 $x$ 到 $y$ 的欧几里得距离。

现在考虑的就是 $P$ 到 $C$ 的最小距离了。我们有垂直公理：在同一平面内，一点到一直线的最短距离等于过该点垂直于该直线的线段的长度，也就是 $PC$ 垂直于 $AB$ 的时候 $PC$ 最短。

这里有两种方法。

第一种，我们可以通过勾股定理求出 $AC$ 与 $BC$ 还有 $AB$ 的长度，然后使用海伦公式求出 $S_{\Delta ABC}$，由于 $S_{\Delta ABC}=\frac{1}{2}AB\times PC$，所以 $PC=\frac{2\times S_{\Delta ABC}}{AB}$。

第二种，我们设 $AP$ 为 $f$，令 $a=AC,b=BC,l=AB$，通过勾股定理我们求出 $PC=\sqrt{a^2-f^2}=\sqrt{b^2-(l-f{)}^2}$，因此有 $a^2-f^2=b^2-l^2-r^2+2lf$， 解得 $f=\frac{a^2-b^2+l^2}{2L}$。再通过勾股定理求出 $PC=a^2-f^2$ 或 $PC=b^2-(l-r{)}^2$。

红绿灯

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

---

虽然最开始时间都为 $1\sim n$，但是观察样例后能够发现过了足够多的红绿灯后，剩下的相邻初始时间基本上都会因为后面的红绿灯导致它们结束时间相同。因此，我们将不同的时间看成一个块，对于时间为 $i$ 的块记录它的左右下标 $[l_i,r_i]$。

接下来考虑新红绿灯。假设当前时间戳为 $x$，红绿灯的周期为 $y$，那么此时有两种情况：若 $x\equiv 0(\mathrm{mod}y)$，那么不需要等红绿灯，过去还是 $x$；否则需要等到下一个周期，即 $(\lfloor x/y\rfloor +1)\times x$。

在改变值域后，我们需要将值相同的多个块合并成一个。该算法在特殊数据下可以被卡到 $\mathcal{O}(nm)$，但是由于在本题中数据为随机生成，因此时间复杂度可以看做 $\mathcal{O}(m\sqrt{n})$。

子集

对于集合 $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$ 取模的值。

---

通过找规律，我们可以发现 $F_k(S)=\sum _{s\in S}{F}_0(s)\times k^{n-|s|}$，需要快速求出 $F_0(s)$，因此考虑 01 背包。由于使用 01 背包后会丢失 $|s|$，我们需要在 01 背包时就记录 $|s|$。可以让 $d{p}_0=k^n$，在每次转移时除以 $k$（使用快速幂取逆元）。时间复杂度 $\mathcal{O}(nm)$。

佛怒火莲

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

---

暴力都不会写，输出 $0$，$0$ 分。

总结

• 排名：$2$；
• 比赛分数：$300/400$；
• 情况：相比 2024.10.3 模拟赛，非常好；
• 问题：不会随机化。