CF600(EDU2) 题解

zrl123456 · 2025-07-16 21:48:18 · 题解

我 6 个题 WA 了 12 遍！

A Extract Numbers:

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

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

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

• 1\le |s|\le 10^5

  为方便处理边界，可在字符串前后都加上一个 ,。
  首先对于每个不在字符串开头的 , 或 ;，记录它与字符串中上一个 , 之间的单词，根据题意判断它是否为数字单词，最后加到答案中即可。
  时间复杂度为 \Theta(n)。

  B Queries about less or equal elements:

  考察：二分。
  题目简述：
  给你两个序列 \{a_n\} 和 \{b_m\}，\forall i\in[1,m]，求：

  \sum_{j=1}^n[a_j\le b_i]

  数据范围：

• 1\le n,m\le 2\times 10^5
• \forall i\in[1,n],j\in[1,m],-10^9\le a_i,b_j\le 10^9

  首先给 \{a_n\} 排序，然后，\forall i\in[1,m]，注意到 \{a_n\} 中第一个大于 b_i 的数的下标即为 \{a_n\} 中小于等于 b_i 的数的个数加上 1，故使用 upper_bound 即可实现。

  C Make Palindrome:

  考察：字符串，贪心。
  题目简述：
  给你一个字符串 s，首先将它中的字母进行修改，然后将它重排，使它成为一个回文串，求当修改字母个数最少时，字典序最少的字符串。
  数据范围：

• 1\le |s|\le 2\times 10^5

  由于字符串可以任意重排，故在一开始就将字符串中的字符按 ASCII 码序升序排序。
  我们要让修改字母数最少，那么我们先将相同的几对字符取一个放进新字符串中。
  然后再将漏单的字符一个个地放进新字符串中，直到字符串的长度达到 \displaystyle\lceil\frac{|s|}{2}\rceil 就终止，剩下的字符就是被修改的字符。
  最后先正序再倒序输出这个新字符串，注意根据 |s| 的奇偶性判断最后一个字符是输出一遍还是两遍。

  D Area of Two Circles' Intersection:

  考察：数学，计算几何。
  题目简述：
  给你两个圆，它们分别以点 (x_1,y_1) 和 (x_2,y_2) 为圆心，以 r_1 和 r_2 为半径，求这两个圆的面积交。
  数据范围：

• -10^9\le x_1,y_1,x_2,y_2\le 10^9
• 1\le r_1,r_2\le 10^9

  两圆之间位置关系有 3 种情况：

  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 的出现次数非严格最多，则称其在该子树中占主导地位。
     对于每个点，求以该点为根的子树的所有占主导地位的颜色种类的总和。
     数据范围：

• 1\le n\le 10^5
• \forall i\in[1,n],1\le c_i\le n

  暴力求每个点的答案，开桶存储每种颜色的出现次数，但是注意在非叶子节点上直接由重儿子转移过来，保留原有数据，这样只有位于重链的点数据才会被清空，由于只有 \Theta(\log n) 条重链，故总时间复杂度为 \Theta(n\log n)。

  F Edge coloring of bipartite graph:

  考察：二分图。
  题目简述：
  在一个左右各有 a 个和 b 个点的有 m 条边的无重边的无向二分图上，对它的每条边染色，要求有公共顶点的两条边不能染成同一颜色，求最少染成几种不同的颜色，并给出一种方案。
  数据范围：

• 1\le a,b\le 10^5
• 0\le m\le 10^5

  观察样例得到一个可能的结论：答案就为每个点的最大度。
  容易发现答案至少为每个点的最大度。
  下面构造出答案为每个点的最大度的一种方案：
  对于每条边，若两点上连的边所染颜色的 \text{mex} 相同，则这条边就染这个颜色。
  否则，我们还是染上两个 \text{mex} 中的较小值，然后找出那条与其矛盾的边并给它染上较大值，若仍有矛盾则递归下去修改。
  由于二分图没有奇环，同时偶环最后所得结论与一开始的 \text{mex} 的前提条件，故不会产生环。
  所以总时间复杂度为 \Theta(m(a+b))。