CF600(EDU2) 题解

· · 题解

我 6 个题 WA 了 12 遍！

A Extract Numbers:

考察：字符串，模拟。
题目简述：
有一个字符串 s，里面有一些单词，它们两两之间用 , 或 ; 分隔开，定义：

数字单词为只由阿拉伯数字组成的且不含前导 0 的单词。 含前导 0 指单词不为 0 且以 0 开头。

现在将所有数字单词放在一起，两两之间用 , 隔开，外面加上 " 并输出在第一行，将其它单词按同样方式处理输出在第二行。
对于任意一行，若没有单词满足条件，则在该行输出 -。
数据范围：

  1. 一圆完全包含另一圆，即 \text{distance}((x_1,y_1),(x_2,y_2))\le|r_1-r_2|，此时两圆面积交就为小圆面积，为 \pi\min(r_1,r_2)^2。
  2. 两圆没有交集，即 \text{distance}((x_1,y_1),(x_2,y_2))\ge r_1+r_2，此时两圆面积交为 0。
  3. 如图： 两圆面积交可表示为扇形 ABD 和 CBD 的面积和减去 \Delta ABD 和 \Delta CBD 的面积和。 那么现在当务之急是计算 \angle BAD 和 \angle BCD，后面以计算 \angle BAD 为例。 注意到在 \Delta ABC 中，三边已知，拿出我们的余弦定理：BC^2=AB^2+AC^2-2AB\cdot AC\cos\angle BAC

    变形可得：

    \angle BAC=\arccos(\frac{AB^2+AC^2-BC^2}{2AB\cdot AC})

    那么 \angle BAD=2\angle BAC。 求出该角后扇形和三角形的面积（分别设为 S_1,S_2）就很好求了：

    S_i=\frac{\angle BAC\cdot r_1^2}{2},S_2=\frac{\sin\angle BAC\cdot r_1^2}{2}

    E Lomsat gelral:

    考察：树上启发式合并。
    题目简述：
    给你一棵有 n 个点的树，第 i 个点上染了种类为 c_i 的颜色。
    若一个子树中颜色 x 的出现次数非严格最多，则称其在该子树中占主导地位。
    对于每个点，求以该点为根的子树的所有占主导地位的颜色种类的总和。
    数据范围：