Camp Day2 Div2

Jan 21, 2019 由 小羊

Problem J - Cosmis Cleaner

这题是个三维的计算几何，需要比较强的微积分知识。不过现场还是推了球缺公式的：

$V(h,r) = \int_h^r \pi(r^2-x^2)dx = \frac{2\pi}3r^3-\pi r^2h+\frac\pi3h^3$

其中 $h$ 为球心到切割屏幕的距离。另外很容易得到两球交平面解析式与点到平面距离公式：

$d_0=\frac{|Ax_0+By_0+Cz_0+D|}{\sqrt{A^2+B^2+C^2}}$

然后根据球在空间中的不同位置进行分类讨论即可。

$ans_n = \begin{cases}0, & 球在区域外 \\ V(-r_n, r_n), & 球在区域内 \\ V(h_0,r_0)+V(d,r_n), & 球一大半在外 \\ V(h_0,r_0)+V(-d,r_n), & 球一大半在内 \end{cases}$

其中 $h_0$ 为清除区域球心到交面距离，$d$ 为被切割的球到交面的距离。

Problem A - Erase Numbers II

即选择两个数字，使得两者以字符串连接的形式得到的数字最大。

为了使数字最大，那么选取的数字必然是长度最长的两个。而且，最大的数字一定会被选到，因为：如果最大的数字在拼接数字的前部，那么没有比前部更大的；如果最大的数字在拼接数字的后部，那么当前部取最大时没有比后部更大的。

那么，我可以忽略另外一个数字的长度第二长条件，假装不知道的给最大的数和另外所有的数来一次拼接，用sprintf和sscanf再带上unsinged long long就可以完成一个 $O(n)$ 的贪心。

比赛时的锅：

• 队友给出了一个分类讨论的思想，然后写的比较混乱。
• 后期有了这种贪心的思想的时候却不知20位数字如何比较大小，没有意识到ull和int128的可行性，然后就用strcmp演自己了。

Problem B - Erase Numbers I

利用后缀数组转化为一个字符串匹配问题，将整个大的连接串分割为三个部分。

但是目前还不太会字符串的有关内容QAQ寒假回去一定会恶补！