本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 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$ 的面积和。 那么现在当务之急是计算 $\ngle BAD$ 和 $\ngle BCD$，后面以计算 $\ngle BAD$ 为例。 注意到在 $\Delta ABC$ 中，三边已知，拿出我们的余弦定理： $$BC^2=AB^2+AC^2-2AB\cdot AC\cos\ngle BAC$$ 变形可得： $$\ngle BAC=\rccos(\frac{AB^2+AC^2-BC^2}{2AB\cdot AC})$$ 那么 $\ngle BAD=2\ngle BAC$。 求出该角后扇形和三角形的面积（分别设为 $S_1,S_2$）就很好求了： $$S_i=\frac{\ngle BAC\cdot r_1^2}{2},S_2=\frac{\sin\ngle 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))$。