跳至主要內容

CCPC 2023 Final 部分题解

Wallbreaker5th大约 7 分钟OI×ICPCOI×ICPCOI×ICPC - 题解OI×ICPC - 贪心OI×ICPC - 单调栈OI×ICPC - 图论OI×ICPC - 堆OI×ICPC - 可撤销贪心OI×ICPC - 博弈论OI×ICPC - DFS 序OI×ICPC - DP

注意

题解写得可能非常抽象。

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

比赛链接:UCupopen in new window

A. Add One 2

题意

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

题解

(如果我没理解错队友的叙述的话)

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

C. Colorful Graph 2

题意

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

题解

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

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

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

D. Min or Max

题意

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

题解

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

G. China Convex Polygon Contest

题意

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

题解

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

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

H. The Game

题意

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

题解

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

J. DFS Order 5

题意

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

题解

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

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

我们按如下方式判断:

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

K. Sticks

题意

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

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

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

题解

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

(代码不是我写的,细节不清楚)