CCPC 2024 Final 部分题解

注意

题解写得可能非常抽象。

「如果一个题解你看不懂，那是题解垃圾而不是你垃圾。」

B. Add One 3 / 加一 3

题意

有一个长为 $n$ 的整数序列 $a_1,a_2,\ldots,a_n$ ，一次操作可以将 $a_i$ 加 $1$ ；多次（独立的）询问，每次给出 $l,r$ ，问至少进行多少次操作可以使得 $a[l..r]$ 是 $a$ 的唯一的和最大的子段（考虑空子段）。 $n,q\leq 5 \times 10^5$ 。

题解

先判断掉一些边界情况，比如当前最大子段和为负之类的。

如果这个 $[l,r]$ 往两边延伸，存在一个非负的后缀或者前缀，那么其一定不合法；否则只需要把每个数加到充分大一定有解。

（无论初始的还是最终的）最大字段不可能与 $[l,r]$ 相交或者包含 $[l,r]$ （因为 $[l,r]$ 往外延伸都是负的），只可能在 $[l,r]$ 内部或外部。实际上所有最大子段之间也只能包含或相离。

先不考虑“唯一”的要求。设当前最大子段和为 $M$ 、 $[l,r]$ 区间和为 $S$ 。 $[l,r]$ 以外的最大子段不会被在 $[l,r]$ 内的增加所影响。我们考察 $[l,r]$ 内的数。要让 $[l,r]$ 本身是最大子段， $[l,r]$ 的前缀和和后缀和都要大于等于 $0$ ，即所有的前缀和要在 $[0,M]$ 范围内。我们只需要从前往后，每一处前缀和为负了就在这里加一、在 $r$ 处把前缀和加到 $M$ 即可，这中途不会出现超过 $M$ 的情况，因为 $M$ 是最大子段和；每次操作都让 $r$ 处的前缀和加一、其从 $S$ 变到了 $M$ 。因此需要的操作数是 $M - S$ 。

现在要求唯一：

如果 $[l,r]$ 已经是唯一的最大子段了， $M-S$ 即可，否则至少要再额外（在 $l$ 或者 $r$ ） $+1$ 来超越其他最大子段。
如果 $[l+1, r-1]$ 内有最大子段，则要在 $l$ 、 $r$ 处各多加 $1$ 。

我们需要求 $[1,n]$ 、 $[1,l-1]$ 、 $[r+1,n]$ 、 $[l+1,r]$ 、 $[l,r-1]$ 、 $[l+1,r-1]$ 的最大子段和，后三个需要用线段树。

C. Iridescent Universe / 彩虹色的宇宙

题意

给一个图，初始每条边有一种颜色。你可以做不超过 $n$ 次操作，每次选择一个点 $x$ ，把它的所有相邻边变成 $y$ 。问是否可行，并构造方案。 $n\leq 2 \times 10^5$ 。

题解

类似拓扑排序。考虑倒着操作，如果一个点的邻居的所有边都是同色的，那么之前可以是任意颜色的。把这些边的颜色变成空，继续对所有邻居边都是同色的或者空的点做这个操作。如果无法继续进行操作，对比一下剩下的边和初始边的颜色即可。

E. Omniscient Artist / 全知艺术家

题意

给定平面上 $n$ 个与坐标轴平行的矩形，求覆盖次数是 $m, 2m, \ldots$ 的面积。 $n \leq 3 \times 10^5$ ， $m \geq \sqrt{n}$ 。

题解

扫描线，需要维护 $a_i$ ：区间加减 $1$ 、查询所有 $m$ 的倍数出现次数。

对序列分块，每块维护 $\max$ 和 $\min$ 之间的每个数的出现次数。查询暴力查询即可，因为 $\sum |a_i - a_{i-1}| \leq 2n$ ，所以 $\sum \max - \min$ 是 $O(n)$ 级别。重构需要做到 $O(\text{块大小})$ （而不是 $O(\max-\min)$ ）。

F. Witnessing the Miracle / 见证奇迹

题意

数轴上 $1$ 到 $n$ 的某些整点位置有磁铁。每次可以选择一个磁铁操作，这个磁铁会消失，两边的磁铁会往外移动一格。你想进行恰好 $k$ 次操作，并且使得最终磁铁仍然在 $[1,n]$ 之间。给两个带 ? 的 01 串 $S$ 和 $T$ ，求有多少种替换 ? 的方式可以使得 $S$ 和 $T$ 可能是合法的初始状态和最终状态。 $n\leq 5000$ 。

题解

考虑确定被拿走的磁铁的集合，此时没有被拿走的磁铁移动的方向和距离可以由它左侧被拿走的磁铁的数量确定。因此拿走磁铁的顺序没有影响。

DP， $f[i,j]$ 表示，确定了 $S$ 的前 $i-1$ 位和 $T$ 的前 $j-1$ 位，且若 $S_i$ 是一个被保留的磁铁，则它最终的位置为 $j$ 。转移时考虑当前位是 0、保留的 1 还是不保留的 1。

G. + and × with a sugar / +, × 与糖

题意

给定一个正整数序列，插入 +、* 使得运算结果最大。 $n \leq 2 \times 10^5$ 。

题解

如果总乘积超过 $2n$ ，把所有数（除了开头结尾的 $1$ ）乘起来一定最大。

对于剩下的数字，至多只有 $\log_2 n + O(1)$ 个数不等于 $1$ ，可以直接枚举或者 DP 这些数的划分方式。

H. Qingyu's Little Training Center / 小青鱼的训练中心

题意

在所有长度为 $n$ 有 $m$ 个 1 的 01 串中，选 $k$ 个，使得每一位 1 个数的最大值尽量小。构造方案。 $n\leq 20$

题解

答案的下界显然是 $\left\ceil \frac{km}{n} \right\ceil$ 。其可以递归构造达到：

先找 $\left\ceil \frac{km}{n} \right\ceil$ 个第一位是 1 的串，为此，我们递归 $n-1, m-1, \left\ceil \frac{km}{n} \right\ceil$ ，并在得到的串前面加上 1。
然后递归 $n-1, m, k - \left\ceil \frac{km}{n} \right\ceil$ ，并在得到的串前面加上 0。
在把两个集合合并起来的时候，需要把后面 $n-2$ 位各自做置换，以把 1 个数多 1 的位尽量错开。

K. Grotesque Team Reconstruction / 怪诞组队法

题意

给一个图，划分成两部分，使得两部分都连通并且点数模 $3$ 都余 $2$ ，问是否可行。 $n,m\leq 5 \times 10^5$ 。

题解

首先判断原图不连通的情况。如果连通，划分成两个连通块意味着在某个点双内部划分开。

建立圆方树，求出点双连通分量中，每个点在去掉这个点双之后的连通块大小（即圆方树上这个点对应的子树大小）模 $3$ 的余数。

如果一个点双中有一个 $2$ ，那么把这个点单独切出来即可，剩下的仍然连通。

否则这个点双中只有 $0,1$ ，如果只有一个 $1$ ，那么这个点双不可行。否则至少有 $4$ 个 $1$ 。因为是点双，所以可以双极定向，一定能划分成两个连通的部分，并且其中一个部分只有两个 $1$ 。