CCPC 2023 Final 部分题解

注意

题解写得可能非常抽象。

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

A. Add One 2

题意

你有一个序列 $a$ ，初始为 $0$ 。你一次操作可以前缀加一或者后缀加一。你要让这个序列的每一项都不小于给定的序列 $b$ 。求 $a$ 的元素和的最小值。 $n\leq 10^6,a_i\leq 10^9$

一个不太优的解是取序列 $b$ 的 $\max$ ，把整个 $a$ 都变成这个值。但是我们可以找到 $a$ 的一个子段，把它挖掉 $1$ ，，对应到操作上就是把一个贯穿的操作变成一个前缀和一个后缀操作、中间空出来一段。我们要做 $\max b$ 次这样的操作，并希望挖掉尽可能长的总长度。~~这就很像前一天才打的 USTCPC 的题。~~用一个单调栈栈扫一遍整个序列，就可以求出哪些段可以挖掉、可以挖多深。这些段从长到短排序，然后贪心地挖即可。

C. Colorful Graph 2

题意

给定一个正 $n$ 边形，以及额外 $m$ 条连接两个顶点的边，边只在顶点处相交。给顶点黑、红染色，使得图中的所有环都包含至少两种颜色。 $n\leq 2 \times 10^5$ 。

题解

首先注意到，对于本题，我们只需要每个极小的环（即每个“面”）满足条件即可。

一个不知道好不好写的写法是，直接从某个环开始 DFS 所有的环，通过额外边来从一个环跳到另一个环；枚举到一个环时，其一定包含至少一个新的顶点，我们对这个新的顶点染色使得这个环满足条件。在一个环上枚举的时候，只需要找当前边的反边的下一条边；而新的环则是当前边（额外边）的反边所在的环。（懒得配图了）

队友的做法是，直接对于所有点按编号从小到大考虑。考虑当前点的连向更大点的出边，这些边中至多有一条（连向最大的点的）的终点已经被染色；我们让这些边的终点轮流红黑染色即可。

D. Min or Max

题意

给定一个序列 $a$ ，一次操作可以把相邻两数变为它们的最大值或最小值。问其能否变为序列 $b$ 。 $n\leq 10^5$ 。

题解

签到题。能选最大或最小其实就是二者任选其一。因此只要 $b$ 是 $a$ 的子序列即可。

G. China Convex Polygon Contest

题意

一场比赛有 $n$ 道题。Kevin 会在时刻 $a_1,\cdots, a_n$ 过题。小青鱼每道题分别要花 $b_i$ 的时间做出来，他可以决定每道题的做题顺序，并且做出来的题可以囤到更晚提交。比赛会有一个“Last Success”榜，显示当前最近一次过题的选手。小青鱼想要在这个榜上尽可能长时间地出现。求最长的时间。 $n\leq 10^5$ 。

题解

小青鱼的策略一定是先做用时短的题目，然后通过囤题来调整自己的过题时间。假如小青鱼每次做完题的时刻都是 Kevin 过题的时刻，那么我们可以从后往前贪心，每次选择在之后的、没被占过的时间段，让这道题囤到这个时间段。

然而小青鱼做完题的时刻可能不与 Kevin 过题的时刻对齐，这时小青鱼可能会选择囤题到之后的时段提交，但也可能选择立即提交。如果立即提交的话，我们可能反悔这个操作：枚举到一个更早完成的题目时，可能会让这道更早完成的题目囤到这个不完整的时间段，相应的题目囤到再往后的某个时间段提交。因此，如果我们某个题目选择了立即提交，我们同时要把堆里最大的一个元素提出来，加上当前时段在当前题目之前的时间长度，放回堆里，作为反悔的选项。

H. The Game

题意

一个长为 $2n$ 的序列，甲乙轮流删除其中一个数，直到序列长度为 $2$ ，甲先手。若任意时刻序列回文，乙胜，否则甲胜。问最终胜者。 $n\leq 10^6$ 。

题解

首先，若乙能胜利，那他也能继续游戏直到序列里只剩两个相同的数（若长为偶数则对称操作，若长为奇数则去掉正中的元素转化为偶数情况）。因此可以把乙的获胜条件改为最后剩下的两个数相同。结论是，乙能获胜当且仅当序列中不同的数的数量小于等于 $n$ ，该结论可以归纳证明。

J. DFS Order 5

题意

给定一棵树。多次询问：给出一个序列，判断其是否是树的以 $1$ 为根的某个 DFS 序的子段。 $n,q\leq 10^5$ 。

题解

~~VP 的时候直接做了不一定以 $1$ 为根的加强版。~~

DFS 的过程一定形如：从起点 $s$ 开始，把起点的子树搜索完，然后沿着起点到根的路径往上跳一段，再往下一步（也有可能不往上，进入到同层的某个点），搜索完另一个子树……当然 $1$ 在序列开头的情况容易处理。

我们按如下方式判断：

（假设 $1$ 不在序列开头）提出起点父亲到根的路径，之后枚举每个序列中的点，如果这个点在这条路径上，无解；如果这个点离这条路径长度为 $1$ ，我们需要遍历这个点的子树；
要是 $1$ 在序列开头，则我们需要遍历 $1$ 的子树。
将要遍历子树的点，以深度从大到小为第一关键字（我们必须先遍历深的子树）、在序列中的位置为第二关键字（相同深度的点为兄弟，它们之间的顺序任意，我们尽力让其符合给定序列）排序。
从每个要遍历的点开始，检查给定序列的这一段能否由从这个点开始 DFS 得到。

K. Sticks

题意

有一个 $n\times n$ 的网格，每个格子为黑色或者白色。我们认为一种染色方案是好的，当且仅当其可以通过以下方式得到：

初始为全白；
对于每一行，染黑一个前缀；
对于每一列，染黑一个前缀；
行和列的前缀之间不相交。

给定一个网格，其中一些格子的颜色确定，其余待定。求好染色方案的数量。 $n\leq 3\times 10^3$ 。

题解

设 $f[i,j]$ 表示：考虑了前 $i$ 行、前 $j$ 列，在前 $i$ 行中存在一行的前缀染色延伸到了第 $j$ 列（即：前 $j$ 的列染色已经被阻挡了）的方案数。为了不算重，我们强制要求每个行的前缀染色染得尽量短；从而如果当前行的染色长度突破的 $j$ （假设到了 $j'$ ），那么第 $j'$ 列的前缀染色不能延伸到当前行。

（代码不是我写的，细节不清楚）