Camp Day2 Div2

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寒假回去一定会恶补!

发表评论

电子邮件地址不会被公开。 必填项已用*标注