CACPC 决赛题解

· · 个人记录

环海岸线联盟联合校赛决赛题解

橘雪莉&&归雨

2026年3月

难度预测

Very Easy:B,H,N

Easy:E,F,G,I

Medium:C,D,J

Hard:K,L,M

Impossible:A

H. 周天它真的不一样

签到题，打表模拟即可。

N. Min and Mex

签到题。

分类讨论：

y=0$：$x=0$ 无解，否则输出两个 $x $y=2$：$x=0$ 输出$0$ $1$，否则无解 其余情况无解。 验题人的做法是 $a=min$，枚举 $b$ 判断是否满足条件，$b-a ≤2$。 ## $B$. 死亡回溯 签到题。 把操作按时间从大到小排序，然后一个一个加入，加入到满足条件的时候输出当前时间即为答案。 时间复杂度 $O(n log n)$。 ## $I$. 归雨的奖励生活 定义三种状态： $a_{i}$：第 $i$ 天为奖励的方案数； $b_{i}$：第 $i$ 天为第一天加训的方案数； $c_{i}$：第 $i$ 天为第二天加训的方案数。 根据规则“不能连续两天奖励”和“不能连续三天加训”，得到转移方程: $$a_{i}=b_{i-1}+c_{i-1},$$ $$b_{i}=a_{i-1},$$ $$c_{i}=b_{i-1}.$$ 初始值：$a_{1}=1$，$b_{1}=1$，$c_{1}=0$。 第 $n$ 天的总方案数为 $f_{n}=a_{n}+b_{n}+c_{n}$。 将后两式代入第一式可得： $$a_{i}=a_{i-2}+a_{i-3} \quad(i \geq 4).$$ 从而推出 $f_{i}$ 满足相同递推： $$f_{i}=f_{i-2}+f_{i-3} \quad(i \geq 4),$$ 初始值 $f_{1}=2$，$f_{2}=3$，$f_{3}=4$。 ## $F$. 愛の残滓 比较难满足的条件是和为合数，那么不妨取出所有模 $5$ 等于 $1$ 的素数，这样任意五个数的和都是$5$的倍数，显然是合数。 Bonus:如何实现这道题的checker? ## $G$. 雪莉的苹果 以下是一种可能的构造： 首先考虑 $n=1$ 的情形，我们可以暴力枚举出一组解$6$，$10$，$15$ 然后如果不考虑元素互不相同的限制，直接全部放这些数字即可。 但是有元素互不相同的限制，我们给每个数乘上一个素数，这样不会改变两两之间的最大公约数。 数据范围比较小，暴力筛素数也可以通过。 ## $E$. Yuanzhe 后援会 $n=2$ 直接输出$1$ $2 $n ≥4$ 的时候，可以手玩出一个构造： $1$−$2$，$2$−$3$，$3$−$4$，$2$−$5$，$5$−$6$，$2$−$7$，$7$−$8$，$\dots

不难证明除了 2 之外所有的点都满足条件。

如果 2 不满足条件，把 3 和 4 换个位置就行。

C. 死亡回溯2

难点在怎么处理时间操作。

只需要在操作的时候顺带维护一个时间戳，然后把操作丢进一个栈里面，时间回溯操作的时候从栈里面暴力弹出，然后把加操作变为减操作即可。

栈内的时间戳显然是单调的，每个元素最多进出栈一次，所以复杂度可以保证。

用任何可以维护单点加，区间查询和的数据结构实现即可。

Fun Fact:Easy version 只需要支持查询单点和，被毙了。

D. 福外集训队

求第 k 大的最大值，直接贪心不好做，考虑二分答案。设二分值为 mid，问题变为：是否存在一种操作，使操作后至少有 k 个数≥mid

如何判断 mid 是否可行？

首先，统计原序列中本来就 ≥mid 的数的个数，记为base。

接下来，考虑操作区间。区间内的数加x 后可能变成≥mid，条件是原数在[mid −x, mid −1] 之间（因为加上x 刚好够到mid）。

记这样的数为“可升级数”。

我们用滑动窗口(双指针)遍历所有长度为 m 的区间，统计窗口内可升级数的个数，取最大值记为 maxGain。 那么，操作后 ≥mid 的总数就是 base + maxGain。若该值 ≥k，则 mid 可行，否则不可行。

二分边界

下界可取原序列最小值，上界可取原序列最大值 +x（因为一次操作最多加 x）。二分即可。

复杂度：每次判断 O(n)，总复杂度为 O(n log (max a+x))，可以通过。

J.!?强强?!(easy version)

枚举第三个字符串的分割点，然后只需要写一个 O(n) 判断一个串是否是另一个串的子串的算法即可，可以KMP 或者字符串哈希实现。

时间复杂度 O(n^{2})。

K.!?强强?!(hard version)

我们可以贪心从第一个串里取尽量大的子串，这样肯定不劣。反过来，如果大的串是某个字符串的子串，更小的串显然也是子串。这样满足了单调性。

于是借鉴B 的思路，只需要二分分割点即可。

时间复杂度 O(n log n)。当然也可以用KMP 做到线性。

M. 图灵完备

非与没有结合律，如果直接拉线段树板子就错了。但是仍然可以通过线段树实现，这里不展开。

注意到答案只和区间内最后一个 0 出现的位置有关，可以用 set 维护所有 0 的出现位置。

然而这还不够简洁，由于数据随机生成，可以直接从右端点暴力往前跳找 0 ，这样并不会跳很多步数（事实上期望是 1 步）。

然后，什么叫做分块能过???

Bonus:将一操作改为区间修改。

【模板】并查集

用 bitset 查并集可以直接通过。

然而如果数据范围加强到 5 ×10^{5}，bitset 将难以通过。

首先需要一个容斥原理，并集等于两个集合的大小之和减去交集，然后转化为求交集。

以下设 n , q 同阶。

我们记忆化答案，然后如果x 集合的大小大于 y 集合的大小，交换两个集合，最后枚举x 集合里的元素，在 y 集合里查询是否存在即可。

证明:我们把集合分为大集合和小集合，分界点为 B 如果其中一个集合是小集合，那么枚举的时间复杂度不会超过 O(n B)

如果两个集合都是大集合，那么大集合之间的询问数有 (\frac{n}{B})^{2} 个. 单次询问复杂度为 B ,总时间复杂度是两者乘积为 \frac{n^{2}}{B}。

为了平衡复杂度，不妨取 B 为根号即可。

A. 箱庭迷宫

Fun Fact: 原本第一版题目中，代价参数固定为 A=30 , B=1 ,且询问次数 q ≤10 ,并要求输出操作序列。此时可以通过枚举所有可能的相遇深度来解决问题，复杂度为 O(n log n+q \cdot n log n) , 虽然涉及 LCA ,但是不至于到防 AK。

然而，出题人感觉存在单次查询 O(\log n) 的做法，于是咨询了润哥(出题人的朋友)。在hack 掉贪心后，提出了一个数位 DP 的解法。经过多轮打磨，最终演变为本题的防 AK 版本。

注:出题人也是在润哥和DeepSeek 的帮助下才理解数位DP 的实现,出题人是躺赢狗。

游戏允许两种操作:

  1. 选择一人沿路径移动 2^{x} 个箱庭，代价为 A 。
  2. 若两人处于同一箱庭，可同时移动 2^{x} 个箱庭，代价为 B 迷宫构成一棵以出口为根的有根树。设归雨、爱丽丝的深度分别为 X Y ,它们最近公共祖先的深度为 M 。若两人在深度为 P 的节点相遇( 0 ≤P ≤M) ),则:归雨单独移动的距离为 X-P ,爱丽丝单独移动的距离为 Y-P ,两人一起移动的距离为 P 。总代价为: cost=A \cdot(popcount(X-P)+popcount(Y-P))+B \cdot popcount(P)

其中popcount(x) 表示 X 的二进制中1 的个数。

一种贪心思路是:当 B<A 时，应尽可能让两人一起走，并且尽可能少点用操作1 , 于是认为 P 必须取自X\&Y 的子集。这里给出一个反例:取 A=30 , B=1 ,并令: X=17 (二进制10001), Y=15 (二进制01111), M=13 (二进制01101). 此时 X \& Y=1 。若取 P=1 ,代价为:

30\cdot (popcount(16)+popcount(14))+1\cdot popcount(1)=30\cdot (1+3)+1=121

但若取 P=13 (即 M 本身),代价为:

30\cdot (popcount(4)+popcount(2))+1\cdot popcount(13)=30\cdot (1+1)+3=63.

显然 P=13 更优，而它并不是X\&Y 的子集。此外，由于代价 A , B 是输入的，任何依赖具体数值的贪心策略都无法保证正确, 这迫使选手采用动态规划。

第一步:求LCA 使用倍增法或树链剖分预处理每个节点的深度和祖先信息，对于每组询问 O(log n) 求出LCA，进而得到X,Y M 第二步:数位DP 求最小代价 我们需要求解:

min _{0<P<M}\{A(popcount(X-P)+popcount(Y-P))+Bpopcount(P)\}

减法可能产生借位，因此不能直接按位独立计算。采用数位DP 从低位向高位逐位处理，同时记录借位信息。

状态定义

设 d p[i][c_{x}][c_{y}][ tight ] 表示处理完第0 到第 i 位(从低位到高位)后，当前位向更高位产生的借位为 c_{x} , c_{y} (分别对应 X-P 和 Y-P ),且当前构造的 P 是否与上限 M 的前缀相等(tight 标志)时的最小代价。最终答案取dp[16][0][0][1](因为 M ≤5 ×10^{4}<2^{16} ,处理到第16 位足够)。

复杂度

预处理 LCA 为 O(n log n) ,每次查询中，求 LCA 需 O(log n) ,数位 DP 也需 O(log n) ,因此总时间复杂度为 O(n log n+q log n) , 足以通过。