CYCPC Round 2 题解

题解作者：Zheng_iii, MaxBlazeIceInk

预测难度：

Very Easy ：L

Easy ： B，K

Medium：D，F，G，H，M

Medium Hard：J，C，E

Hard ：A，I

A

二分最大目标 DPS $K$ 。由 $\frac{\text{Total Dmg}}{\text{Total Time}} \le K$ 变形可得，释放单次增幅技能的独立等效收益为：

$Weight = Extra\ Damage - K \times Extra\ Time$

原问题转化为：求满足排轴限制下，最多释放 $m$ 次技能的最大总 $Weight$ 。若最大总权重 $\ge K \times Basic \ Time - Basic\ Damage$ ，则当前 $K$ 合法。

有次数限制，猜凸性，引入 WQS 二分。每次转移扣除斜率附加费 $C$ ，求无限制的最大收益 $g(C) = \max_x \{ f(x) - C \cdot x \}$ 。

拉格朗日弱对偶定理，最优解直接由对偶函数极小值求得： $\text{Ans} = \min_{C \ge 0} \{ g(C) + C \cdot m \}$

技能后摇 $T$ 会引发后续时间推迟，为避免时间维度爆炸，将所有排轴操作全部映射到没有技能的绝对基准时间轴上。

在基准时刻 $X_{base}$ 释放技能，影响是：

有效增伤终点： $MappedEnd = \min(X_{base} + L, T_{start}[i+1] + L - T)$
延时惩罚： $\Delta t = \max(0, X_{base} + T - T_{start}[i+1])$

需要特别注意的是，如果增伤时间 $L \le$ 技能后摇 $T$ ，意味着 Buff 在僵直期内就会消失，无法提供任何增伤，反而会拖慢排轴。此时最优策略为不释放任何技能，直接特判输出纯基础 DPS 即可。

只需保证下一次技能起手 $X_{next} \ge MappedEnd$ ，即可解耦后效性。DP 状态缩减为 (基准结束时间, 当前累积收益, 耗费技能数)。

为避免同冷却期内大量合法 $X_{base}$ 造成的 $O(N^2)$ 转移，对于两个不同的状态 A 和 B ，如果状态 A 结束更早、收益更高、耗费配额更少，B 就可以被移除了。

将所有新状态按 MappedEnd 升序、Obj 降序、count 升序排序。线性扫描该数组，维护历史最大收益 max_obj，仅当遇到 Obj > max_obj 的状态才入栈。

当增伤时间 $L$ 极大时，技能影响跨越多人格，状态数仍会因无法合并而膨胀。结合数据随机性，对存活的候选状态集合进行均匀采样，强制保留时间最优（首）与伤害最优（尾），并在中间均匀抽样保留常数个点（如 24 个）（类似拟合这个图像），这样复杂度就是对的。

B

诈骗题（可能是）。

因为枚举到了每一个数对和他们的 $gcd$ ，所以：

\sum_{j=1}^{\lfloor i/2 \rfloor - 1} f(i, j) = \binom{i}{2} - f(i, \lfloor i/2 \rfloor) \\ = \binom{i}{2} - 1

可得：

ans = \sum_{i=1}^n \left( \binom{i}{2} - 1 \right)

展开后有很多推法，可以选择直接上指标求和。

ans = \binom{n+1}{3} - n - 1 \\ ans = \frac{(n+1)\times n\times (n-1)}{6}-n-1

有趣的是，在 AI 验题的过程中，gemini 3.1 pro 用力大砖飞的做法推出了同样的式子，以下是它的做法：

首先，理解 $f(i, j)$ 的含义：

$f(i, j)$ 表示在 $1 \le x < y \le i$ 中，满足 $\gcd(x, y) = j$ 的数对 $(x, y)$ 的数量。

这等价于在 $1 \le x' < y' \le \lfloor i/j \rfloor$ 中，满足 $\gcd(x', y') = 1$ 的数对 $(x', y')$ 的数量。

我们知道， $[1, m]$ 中互质的数对数量为 $\sum_{d=2}^m \varphi(d)$ 。

令 $\Phi(m) = \sum_{d=2}^m \varphi(d)$ ，且 $\Phi(1) = 0$ 。因此有 $f(i, j) = \Phi(\lfloor i/j \rfloor)$ 。

回到原式：

ans = \sum_{i=1}^n \sum_{j=1}^{\lfloor i/2 \rfloor - 1} f(i, j)

注意到当 $j \ge \lfloor i/2 \rfloor$ 时， $\lfloor i/j \rfloor \le 2$ 。

特别地，当 $j = \lfloor i/2 \rfloor$ 时（ $i \ge 4$ ）， $\lfloor i/j \rfloor = 2$ ，而 $\Phi(2) = \varphi(2) = 1$ 。

更进一步地，如果我们将 $j$ 的求和范围扩展到 $i$ ，可以通过扣除多余的项来化简：

\sum_{j=1}^{\lfloor i/2 \rfloor - 1} \Phi(\lfloor i/j \rfloor) = \sum_{j=1}^i \Phi(\lfloor i/j \rfloor) - 1 \quad (\text{对于 } i \ge 4)

为了方便，我们计算扩展后的总和 $S(n) = \sum_{i=1}^n \sum_{j=1}^i \Phi(\lfloor i/j \rfloor)$ 。

代入 $\Phi$ 的定义，改变求和顺序：

S(n) = \sum_{i=1}^n \sum_{j=1}^i \sum_{d=2}^{\lfloor i/j \rfloor} \varphi(d)

条件 $d \le \lfloor i/j \rfloor$ 等价于 $j \cdot d \le i$ 。因此我们可以将其看作是枚举 $j$ 和 $d$ ，统计满足 $j \cdot d \le n$ 的情况：

S(n) = \sum_{k=2}^n \sum_{j \cdot d = k, d \ge 2} \varphi(d) \times (n - k + 1)

根据欧拉函数的性质， $\sum_{d|k, d \ge 2} \varphi(d) = k - 1$ 。

因此，

S(n) = \sum_{k=2}^n (n - k + 1)(k - 1)

这是一个经典的求和式，展开后可以用等差数列和平方和公式化简，得到：

S(n) = \frac{(n-1)n(n+1)}{6} = \binom{n+1}{3}

最后，我们需要扣除前面推导中多加的部分（每个 $i \ge 4$ 都多加了 $1$ ，且要处理前 3 项的边界）：

经过边界补偿可以得出，真正的答案恰好是：

ans = S(n) - n - 1 = \binom{n+1}{3} - n - 1

将上述结论在对 $998244353$ 取模的条件下用 $O(1)$ 的时间复杂度实现，即可完美解决此题。

C

前置部分构造 DAG，连边 $i \to i+1, i+2, i+3$ ，我们给跨步捷径附加按二进制位递减的正数惩罚值 $\Delta$ 。

这种势能设计能强制优先队列按路径总权值从大到小的顺序，逆向遍历超过 $10^7$ 种路径组合。

为了突破 $10^8$ ，我们在最后两个节点间构造重边，连入近 20 条权值严格递减的重边。

由于主体部分放大了最短路的更新间距，节点 29 的每一次出队，都能触发这 20 条重边的连续松弛。

这样就能做到 $10^8 +$ 次操作了。

D

建出线段树，给每个区间内的每个坐标开一个点，算上外部点，一共 $O(n\log n)$ 个点。

考察区间 $[l,r]$ ，内部做好相邻之间的连边，边权为 $1$ 。对于 $x\rightarrow [l,r]$ ，不难发现，如果 $r\leq x$ ，那么可以 $x$ 向 $r$ 连接边权为 $d+x-r$ 的边来完成建图； $l>x$ 同理。显然如果 $x\in[l,r]$ ，可以拆成两部分。

对于 $[l,r]\rightarrow x$ ，不难发现，照着上面的图再建一份就是对的。

树上点向外部点连单向边。总边数 $O((n+m)\log n)$ ，跑 dijkstra，复杂度 $O(n\log^2n)$ 。

考虑一些更优的做法。建两类线段树，一棵表示向右，一棵表示向左。左树中父节点向左子节点连边 $r-mid$ ，向右子节点连边 $0$ 来充分利用递归结构。这样的点数为 $O(n)$ ，不会被卡。

E

概率/期望 + 生成函数 + 卷积。

在出这道题的时候觉得 NTT 会污染这道题其余的部分，所以就放 $O(n^2)$ 过了。

这题推法比较多，笔者讲一个没啥门槛的有点复杂的推法。

先考虑任意两行在列意义下的代价。

两个元素 $a_i > b_i$ ，当且仅当存在一个特定的阈值 $v$ ，使得 $a_i > v$ 且 $b_i \le v$ 。

也就是说，转换成 01 序列， $a_i$ 对应的是 $1$ ， $b_i$ 对应的是 $0$ 。

设 $x$ 为 $a$ 中 $1$ 的数量， $y$ 为 $b$ 中 $1$ 的数量，那其实代价就是 $max(0,x-y)$ 。

考虑枚举 $v,x,y$ ，忽略外层和式，里层是：

\binom{n}{x}(m-v)^xv^{n-x}\times\binom{n}{y}(m-v)^yv^{n-y}

令 $k = x + y, m = \lfloor \frac{k}{2} \rfloor$ 。

把枚举 $x$ 的求和挪进来，把除二项式外的部分挪出去：

v^{2n-k}(m-v)^k\sum_{x=0}^n \binom{n}{x}\binom{n}{k-x}max(0,2x-k)

现在我们有两个部分需要处理，一个是和式里面的部分，一个是和式外面的部分，我们先考虑和式里面。

也就是：

\sum_{x=0}^n \binom{n}{x}\binom{n}{k-x}max(0,2x-k)

$max(0,2x-k)$ 其实是好处理的，上式显然等于：

\sum_{x=m+1}^k (2x-k) \binom{n}{x}\binom{n}{k-x}

内层的这一些二项式看起来有点难受，拆一下：

x \binom{n}{x}\binom{n}{k-x} - (k-x) \binom{n}{x}\binom{n}{k-x}

根据吸收恒等式，可得上式等于：

n \left[\binom{n-1}{x-1}\binom{n}{k-x} - \binom{n}{x}\binom{n-1}{k-x-1} \right]

这个 $n$ 不好看，考虑把他拆成 $n-1$ (下面的推导先把外面那个 $n$ 省略了)：

\binom{n-1}{x-1} \left[ \binom{n-1}{k-x} + \binom{n-1}{k-x-1}\right] - \left[ \binom{n-1}{x} + \binom{n-1}{x-1}\right] \binom{n-1}{k-x-1}

惊喜的发现居然有两项是一样的，把他们消掉，剩下的是：

\binom{n-1}{x-1}\binom{n-1}{k-x} - \binom{n-1}{x}\binom{n-1}{k-x-1}

这个东西看上去非常整齐，那我们设 $f(x) = \binom{n-1}{x-1}\binom{n-1}{k-x}$ 。

会发现这个东西其实就是 $f(x) - f(x+1)$ 。

我们把刚刚省略的 $n$ 乘回去， $n(f(x) - f(x+1))$ 。

外层的和式也加上：

n\sum_{x=m+1}^{k}f(x) - f(x+1)

相邻两项可以消掉中间的部分，所以上式等于：

n(f(m+1)-f(k+1))

由于 $f(k+1)$ 带回定义计算后是 $0$ ，所以上式其实是：

n\times f(m+1)

这样再带回定义式就完成内层和式的推导了，得：

n\binom{n-1}{\lfloor \frac{k}{2} \rfloor}\binom{n-1}{\lfloor \frac{k-1}{2} \rfloor}

接下来考虑外层的 $v^{2n-k}(m-v)^k$ 。

把枚举 $v$ 的和式加上：

c_k = \sum_{v=1}^{m-1} v^{2n-k}(m-v)^k

这个东西看起来就很可做，先二项式展开一下后面的部分：

\sum_{j=0}^k \binom{k}{j} m^{k-j} (-1)^j(\sum_{v=1}^{m-1}v^{2n-k+j})

\sum_{j=0}^k \binom{k}{j} m^{k-j} (-1)^jS(2n-k+j)

后面是自然数幂和，考虑用拆第二类斯特林数拆下降幂：

v^p = \sum_{i=0}^p \begin{Bmatrix} p \\ i \end{Bmatrix} i! \binom{v}{i}

S(p) = \sum_{i=0}^p \begin{Bmatrix} p \\ i \end{Bmatrix} i! \sum_{v=1}^{m-1} \binom{v}{i}

后面是上指标求和，所以：

\sum_{i=0}^p \begin{Bmatrix} p \\ i \end{Bmatrix} i! \binom{m}{i+1}

$\binom{m}{i+1}$ 看上去不好算，因为 $m$ 很大，但是带上前面的 $i!$ 就很好算，展开一下 $\binom{m}{i+1}$ 发现乘上 $i!$ 可以变成一个下降幂的形式，这样就可以递推 $O(n)$ 算了。

至此我们会发现复杂度里的 $m$ 消失了，带回去就可以 $O(n^2)$ 直接算。

F

换根题先定根。不难发现可以树形 dp， $f_x$ 表示子树内叶子全变成最大值的最小代价，记为 $(m_x,f_x)$ 。当合并 $(m_x,f_x)$ 与 $(m_y,f_y)$ 时，不妨设后者大，合并出 $(m_y,f_x+f_y+m_y-m_x)$ 。

注意到有多个子树的时候需要同时合并，因此实际上是三元组。

合并具有结合律。换根的时候维护子树前后缀三元组即可。

$O(n)$ 。

G

不难注意到，对于一个子串，将其左向循环位移 $q$ 次后如果形成回文串，那么一定有开始的子串前 $2q$ 个字符为一个回文串，且右端剩余的字符串也为回文串。

不难想到枚举分界点。对于每个 $i$ ，统计有多少 $j\leq i,k>i$ ，满足 $[j,i],(i,k]$ 均为回文串，且 $[j,i]$ 为偶回文串。

发现会漏。再仔细看，发现后缀上也要计算，这考虑了重叠的贡献。反过来再算一次即可。

于是答案是：左右匹配（要求非空）各一次，然后单独回文串算 $1$ 次，单独偶回文串算 $2$ 次。

H

映射思想，看到 $2m$ 思考它不是白给的。

记第 $i$ 个质因子的次数为 $a_i$ ，每个数都是一个 $b_i$ 的向量序列。

不难发现，一个长度为 $2m$ 的序列，进行变换 $b_i\leftarrow a_i-b_i$ 可以建立近乎完全的映射。

也即，一个乘积 $k<n^m$ 的序列和一个乘积为 $\displaystyle\frac{n^{2m}}{k}>n^m$ 的序列一一对应，然而乘积恰为 $n^m$ 的序列被多算了。

因此我们只需要计算乘积恰为 $n^m$ 的序列个数。这在每个质因子上是独立的，对每个质因子做容斥即可。

$O(\sqrt n+\omega(n)m)$ 。

I

djq 学生物的 S4 版本。

桌面上卡片的状态可以看作是群 $G = (S_4)^n$ 上的一个元素。每一次“洗牌操作”相当于在群 $G$ 上乘上一个元素。这就形成了一个带有停止概率的随机游走模型。

设转移概率分布为 $P(g) = \frac{c_g}{m}$ ，停止概率为 $\frac{1}{m}$ 。最终状态的概率分布 $F$ 满足：

$F = \sum_{k=0}^{\infty} P^{*k} \cdot \frac{1}{m}$

这里 $*$ 表示群卷积。在群代数 $\mathbb{F}_q[G]$ 中，上述无穷级数可以求和为：

$F = \frac{1}{m} (I - P)^{-1} = (mI - mP)^{-1}$

其中 $I$ 是群的单位元。由于 $m = 1 + \sum c_g$ ，元素 $mI - mP$ 在单位元处的系数为 $m - c_e$ ，在其他元素 $g$ 处的系数为 $-c_g$ 。

为了求群代数中元素的逆，我们需要将它映射到频域。因为 $G = (S_4)^n$ ，它的不可约表示是 $S_4$ 不可约表示的张量积。我们可以利用 $S_4$ 的 5 个不可约表示（维数分别为 1, 1, 3, 3, 2），做 $n$ 维的快速傅里叶变换（FFT）。

在频域中，只需对每个张量积空间所对应的矩阵求逆，最后再做一次逆 FFT 即可。

J

朴素做一下发现做不出来，必然要利用直径。

考虑固定一个 $x$ 怎么做。此时 $y$ 的答案是 $\displaystyle\max_{i=1}^n\{d_i+dis(y,i)\}$ 。

trick：新定义直径。我们令 $w(u,v)=dis(u,v)+d_u+d_v$ ，那么答案是 $w$ 意义下的直径。现在我们来证明 $w$ 具有一般直径的所有性质。

证明：在每个点 $u$ 上挂一个叶子 $u'$ ，使得 $u,u'$ 间的边权为 $d_u$ ；那么 $w$ 显然是与新树的路径和定义一致，所有直径的性质均成立，得证。

因此我们只需要维护点集直径。对于 $x$ 不固定的情况，显然我们在第一棵树的 dfs 序上建立线段树，维护 $[l,r]$ 的点集直径。换根过程中对 $d$ 的修改是区间加减。这对点集直径的变化是可控的。

$O(n\log n+q)$ 。

K

有科普性质的题目。

设 $dp[i][0/1]$ 表示考虑了前 $i$ 个节点，且节点 $i$ 属于集合 $S/T$ 时的最小割代价。

当节点 $i$ 属于集合 $S$ 时（即求 $dp[i][0]$ ）：

此时必须割断 $i \to T$ （代价 $a_{2i}$ ）。

节点 $i-1$ 可以属于集合 $S$ 或 $T$ 。无论 $i-1$ 在哪个集合，边 $i-1 \to i$ 都不可能发生从 $S$ 指向 $T$ 的情况（要么都在 $S$ ，要么是从 $T$ 指向 $S$ ）。

dp[i][0] = \min(dp[i-1][0], dp[i-1][1]) + a_{2i}

当节点 $i$ 属于集合 $T$ 时（即求 $dp[i][1]$ ）：

此时必须割断 $S \to i$ （代价 $a_{2i-1}$ ）。

节点 $i-1$ 如果属于集合 $S$ ，则边 $i-1 \to i$ 是从 $S$ 指向 $T$ ，必须割断（代价 $a_{2n+i-1}$ ）。

节点 $i-1$ 如果属于集合 $T$ ，则边 $i-1 \to i$ 不产生代价。

dp[i][1] = \min(dp[i-1][0] + a_{2n+i-1}, dp[i-1][1]) + a_{2i-1}

所有节点考虑完毕后，最小割即为 $\min(dp[n][0], dp[n][1])$ 。

L

签到题。

注意到如果 n 是偶数，先手必胜，否则后手必胜。

证明：

1. 终局状态（必败态）：

当 n = 1 时，游戏结束，面对 1 的玩家因为找不到满足条件的严格约数（1 <= d < 1 不成立）而立刻输掉游戏。
注意到，1 是一个奇数。

2. 面对奇数时的处境（必败态）：

如果当前玩家面对的是一个奇数 n，那么 n 的所有约数 d 一定也都是奇数。
根据游戏规则，该玩家操作后的数字将变成 n - d。
因为奇数 - 奇数 = 偶数，所以面对奇数的玩家，无论怎么选择约数，操作后必定会把一个偶数交给对手。

3. 面对偶数时的处境（必胜态）：

如果当前玩家面对的是一个偶数 n（且 n >= 2），他需要选择一个严格约数 d。
任何大于等于 2 的整数，都必然包含 1 这个约数。该玩家可以直接选择 d = 1（1 是奇数）。
根据游戏规则，操作后的数字将变成 n - 1。
因为偶数 - 奇数 = 奇数，所以面对偶数的玩家，总是可以通过减去 1，强行把一个奇数交给对手。

4. 总结必胜策略：

两个绝顶聪明的人博弈，谁能把对手逼到奇数，谁就能赢（因为 1 是奇数，最终输的人一定会面对 1）。
如果 n 初始是偶数：先手只需每次都选择减去 1，后手就会永远只面对奇数。后手无论怎么操作，都会把偶数还给先手。数字不断减小，最终后手一定会面对 n = 1 而落败。Cirno 胜。
如果 n 初始是奇数：先手无论怎么操作，都只能把偶数交给后手。此时后手掌握了主动权，可以采用上述的“每次减 1”策略，反过来把先手逼入绝境。Daiyousei 胜。

M

因为每个眼睛只会朝一个特定的方向看，所以可以将所有点的 $x,y,x+y,x-y$ 坐标进行离散化处理。

然后在 $8$ 个方向均摊枚举所有的直线。对于每一条直线，按照一个方向的顺序扫描所有点。记录路线上最近遇到的眼睛；遇到任何点的时候，将身体对应的点向眼睛对应的点连边（表示操作的先后关系）；遇到眼睛的时候额外更新最近的眼睛。这样连出的边数也是 $O(\sum k)$ 的。

最后进行拓扑排序，用优先队列贪心取最小的可行点即可。 $O((\sum k)\log(\sum k))$ 。

CYCPC R2 题解

CYCPC Round 2 题解

A

B

C

D

E

F

G

H

I

J

K

L

M