Codeforces Global Round 26

比赛链接

Problems	AC
A. Strange Splitting	○
B. Large Addition	○
C1. Magnitude (Easy Version)	○
C2. Magnitude (Hard Version)	○
D. ‘’a’’ String Problem	○
E. Shuffle
F. Reconstruction

A

将已经排序的数组元素红蓝染色，使得两种颜色均有，且红色数组的极差不等于蓝色数组的极差，或报告这不可能。保证数组元素数量至少有 $3$ 个。

将第二个染成红色，其余蓝色即可。

Code

B

问：正整数 $x$ 是否是两个满足以下条件的数的和：

• 两数位数相同
• 两数均仅由 $5,6,7,8,9$ 组成

最后一位不能是 $9$，第一位只能是 $1$，中间不能是 $0$

Code

C1

给定长度为 $n$ 的数组 $a$，进行以下流程，有整数 $c = 0$，枚举 $1, 2, \cdots, n$，每次可选择：

• $c \leftarrow c + a_i$
• $c \leftarrow \mid{c + a_i}\mid$
  求 $c$ 的最大值

只需要记录 $c$ 的最小值和最大值即可。只有可能从这两个中转移。

Code

C2

对于 C1 的问题，求取得最大值的方案数。

直接 dp 即可。

Code

D

给定一个由小写拉丁字符组成的字符串 $s$ 。计算非空字符串 $t \neq$ “ $\texttt{a}$ ” 的数量，以便可以将 $s$ 划分 $^{\dagger}$ 为满足以下条件的子字符串：

• 每个子字符串等于 $t$ 或 “ $\texttt{a}$ ”，并且
• 至少一个子字符串等于 $t$ 。

$^{\dagger}$ 字符串 $s$ 的划分是一些 $k$ 字符串 $t _ 1, t _ 2, \ldots, t _ k$ (称为子字符串)的有序序列，例如 $t _ 1 + t _ 2 + \ldots + t _ k = s$ ，其中 $+$ 表示连接操作。

对于 $s$ 中的非 $\texttt{a}$ 字符数量一定是 $t$ 中的非 $\texttt{a}$ 字符数量的整数倍。

质因数分解，然后从每一个非 $\texttt{a}$ 字符段的起点开始枚举。

考虑 $t$ 的最终形式左右都可以拼上一些数量的 $\texttt{a}$。假设左边有 $x$ 个，右边有 $y$ 个。

我们遍历 $s$，假设在 $s$ 中出现的每一段 $t$ 左边有 $A_i$ 个，右边有 $B_i$ 个 $\texttt{a}$ 字符。

我们应该需要满足：

• $$0 \leq x \leq \min{A_i}$$
• $$0 \leq y \leq \min{B_i}$$
• $$0 \leq x + y \leq \min\left{A_{i + 1} - B_{i}\right}$$

Code

E

两只饥饿的小熊猫，奥斯卡和露拉，有一棵有 $n$ 个节点的树 $T$。他们愿意对整个树 $T$ 执行以下 Shuffle Procedure 一次。通过这个 Shuffle Procedure，他们将用旧树的节点创建一棵新树。

1. 从原始树 $T$ 中选择任意节点 $V$。创建一棵以 $V$ 为根的新树 $T_2$。
2. 从 $T$ 中移除节点 $V$，使得原始树被分割成一个或多个子树（如果 $V$ 是 $T$ 中唯一的节点，则为零个子树）。
3. 对每个子树执行相同的 Shuffle Procedure（再次选择任意节点作为根），然后将所有 Shuffle 后的子树的根节点重新连接到 $V$，完成构建 $T_2$。

在此之后，奥斯卡和露拉得到一棵新树 $T_2$。它们只能吃树叶，并且非常饥饿，所以请找出通过一次 Shuffle 后可以创建的树中叶子的最大数量。

注意，叶子是所有度为 $1$ 的节点。因此，如果根节点只有一个子节点，它也可以被视为叶子。

观察一下。

想象一个“人”字形状的树，我们选择中间那个点可以让叶子变得最多。那么对于一个不相邻的点集，可以通过操作让他们全部变成叶子吗？我们只需要找到 不在点集里面 而且 和点集里的点相邻 的点 进行操作，就能让他们全部变成叶子。那么答案就是求一个树上的最大的点集，满足点集里面的点互不相邻。

但是结合样例 1，会发现答案并不是最大独立集。原因出在什么地方呢？因为在样例 1 中，我们将 3 作为根，但 3 本身是个叶子结点，所以答案会 +1。也就是说我们要做的就是每次枚举一个点删去，在剩下的点中跑最大独立集，然后如果删去的那个点是叶子的话答案就要 +1。

Code