挖土机杯 CSP-J 组模拟赛 R2 全盘题解

Hisaishi_Kanade · 2022-10-16 12:22:14 · 个人记录

前言

AK了，但是时间很拉

【A】探索未知

题意：给出一大坨分数让你加减。

根据数学知识，\dfrac a b \pm\dfrac c d=\dfrac {ad \pm bc} {bd}。

设 ad\pm bc=x,bd=y，

由于原题要求约分，所以需要将上下除以他们的公约数 g=\gcd(x,y)。

我封装了一个很傻逼的 frac 类，支持 +=/-= 运算符。初始值是 \dfrac 0 1=0。

但是要求形如 -\dfrac {1145141} {1919810} 的需要输出 -1145141/1919810，也就是负号加在分子上，所以 -= 的时候判一下。

代码

【B】球状精灵的传说

首先 n^2 做法显然。

如何优化呢？我们想到一点，\rho 只和 \min(r_1,r_2,r_3) 有关。如果拥抱以后 \rho 更大了，显然改掉的是 r_1。

由此对于任意一个精灵 \{r_1,r_2,r_3\}，排序得到 \{q_1,q_2,q_3\}。

我们只要让他和另外一个精灵 \{p_1,p_2,p_3\}（也有序）拥抱时，使得 p_2=q_2,p_3=q_3，且 q_1 最大。

显然答案更优（因为 \min(r_1,r_2,r_3) 更大了）。

但是怎么找呢？

注意到 r_1,r_2,r_3 很小，可以开 10^3\times 10^3 的桶记录。