26.9.21 比赛记录

更新于 2026年9月26日约 9 分钟阅读

成外 & 梦熊 CSP-S 模拟赛 3。

除了 T1 是签到题以外,T2、T3、T4 都使我大脑燃烧。

T1 ball

做一个倍增数组,fi,jf_{i,j} 表示 ii 走了 2j2^{j} 步后到达的位置,然后对于每一个位置的球,二进制拆分求出最终到达的位置,在最终到达的位置累加即可。

T2 cut

枚举 kk 切割次数,xx 切割成的棍木长度。注意到对于所有长度 ≤2k×x\le2^{k}\times x 的棍木,对答案的贡献都是 ⌊pix⌋\lfloor\frac{p_{i}}{x}\rfloor。再长一点的棍木,对答案的贡献都是 2k−12^{k}-1。kk 枚举到 log⁡m\log m 即可,xx 枚举到 m2k\frac{m}{2^k} 即可,这两层时间复杂度 O(m)O(m)。但是后面枚举每根棍木计算 ⌊pix⌋\lfloor\frac{p_{i}}{x}\rfloor 是不可能的,所以我们枚举 j=⌊pix⌋×xj=\lfloor\frac{p_{i}}{x}\rfloor\times x,把所有 ≥j\ge j 的数字贡献 +1+1。要统计 ≥j\ge j 的数字,用桶做个后缀和即可。总体时间复杂度 O(mlog⁡m)O(m \log m)。

T3 red

设 fif_i 表示前 ii 个位置的最大得分,显然 fi=max⁡j=1i−1fj+i−jf_{i}=\max_{j=1}^{i-1} f_{j}+i-j,其中 [j+1,i][j+1,i] 是红色区间。记 xix_{i} 为 ii 位置红色数量减去绿色数量,yiy_{i} 为 ii 位置红色数量减去蓝色数量,XiX_{i} 和 YiY_{i} 分别为它们的前缀和。那么一段区间 [j+1,i][j+1,i] 是红色区间当且仅当 Xi≥XjX_{i}\ge X_{j} 且 Yi≥YjY_{i}\ge Y_{j}。而对于 Xi>XjX_{i}> X_{j} 且 Yi>YjY_{i}> Y_{j} 的区间,实际上不是最优解,因为这种区间扩展一格后可以得到更长的长度并且仍然是红色区间。因此只需考虑 Xi>XjX_{i}> X_{j} 且 Yi=YjY_{i}= Y_{j},或者 Xi=XjX_{i}= X_{j} 且 Yi>YjY_{i}> Y_{j} 的区间。这样题面就变成了二维偏序的形式。对于每一个 XjX_{j},有对应的 YjY_{j} 集合,在集合中找到 Yj<YiY_{j}<Y_{i} 的数中,fj−jf_{j}-j 最大的那个。这个二维偏序用树状数组即可解决,给每个 XiX_i 单独开一个树状数组,YiY_i 同理。时间复杂度 O(nlog⁡n)O(n\log n)。

T4 cover

这题应该是一道矩阵优化递推模板题,但是我完全不会什么矩阵优化递推。

首先要想到本题的 DP 式子。定义 fif_i 为考虑前 ii 个位置,并且 ii 位置为一个棍木的结尾时的答案。如果当前位置没有标记,那么 fi=∑j=1i−1fj(i−j)2f_i=\displaystyle\sum_{j=1}^{i-1}f_j(i-j)^2。否则 fi=0f_i=0。

接下来把这个式子进行矩阵优化(先说结论)。

初始答案矩阵是这样的:

Ans=[100]Ans=\begin{bmatrix} 1\\ 0\\ 0 \end{bmatrix}

定义以下矩阵:

A=[101111122]A=\begin{bmatrix} 1 & 0 & 1\\ 1 & 1 & 1\\ 1 & 2 & 2 \end{bmatrix}B=[100110121]B=\begin{bmatrix} 1 & 0 & 0\\ 1 & 1 & 0\\ 1 & 2 & 1 \end{bmatrix}

一次递推,如果一个点没有被标记,就把答案更新为:A×AnsA\times Ans;否则更新为 B×AnsB\times Ans。

注意到最多有 10510^5 个标记点,因此对于连续的一段无标记点,可以用矩阵快速幂加速。时间复杂度 O(mlog⁡n)O(m\log n)。答案即为 AnsAns 矩阵的第 33 行。

你问我这 33 个矩阵怎么来的,非常抱歉,本人数学不好,不知道怎么来的,我也不会推式子,也看不懂这些矩阵为什么是这样构造的。

Deepseek 的解释

1. 定义状态与辅助量

设 dpidp_i 表示前 ii 个位置被完全覆盖,且在位置 ii 处放置分割点的方案价值之和。对于位置 ii,定义三个辅助前缀和:ai=∑j=0i−1dpja_i = \sum_{j=0}^{i-1} dp_jbi=∑j=0i−1dpj⋅(i−j)b_i = \sum_{j=0}^{i-1} dp_j \cdot (i-j)ci=∑j=0i−1dpj⋅(i−j)2c_i = \sum_{j=0}^{i-1} dp_j \cdot (i-j)^2显然,当 ii 不是标记点时,dpi=cidp_i = c_i(因为 dpi=∑j=0i−1dpj(i−j)2=cidp_i = \sum_{j=0}^{i-1} dp_j (i-j)^2 = c_i)。

2. 初始条件 dp0=1dp_0=1 的来源

题面并没有直接给出 dp0=1dp_0=1。
dp0dp_0 是我们为了启动递推而人为定义的初始条件。dp0dp_0 的含义是:把前 00 个位置(即空线段 [0,0][0,0])完全覆盖,并且在位置 00 处放一个分割点的方案价值之和。
空线段只有一种覆盖方案:什么都不放。
该方案的价值是所有木棒长度的平方的乘积。空线段没有木棒,所以是空乘积。
数学中约定空乘积为 11,因此我们定义:dp0=1dp_0 = 1这个初始条件不是题面直接给出的,而是由“空线段价值 = 空乘积 = 1”的约定推导出来的。

3. 非特殊点的转移(ii 不是标记点)

此时 dpi=cidp_i = c_i 会加入前缀和。考虑从 ii 到 i+1i+1 的转移:ai+1=∑j=0idpj=ai+dpi=ai+cia_{i+1} = \sum_{j=0}^{i} dp_j = a_i + dp_i = a_i + c_ibi+1=∑j=0idpj(i+1−j)=∑j=0i−1dpj(i+1−j)+dpi⋅1=∑j=0i−1dpj(i−j)+∑j=0i−1dpj+dpi=bi+ai+ci\begin{aligned} b_{i+1} &= \sum_{j=0}^{i} dp_j (i+1-j) \\ &= \sum_{j=0}^{i-1} dp_j (i+1-j) + dp_i \cdot 1 \\ &= \sum_{j=0}^{i-1} dp_j (i-j) + \sum_{j=0}^{i-1} dp_j + dp_i \\ &= b_i + a_i + c_i \end{aligned}ci+1=∑j=0idpj(i+1−j)2=∑j=0i−1dpj[(i−j)2+2(i−j)+1]+dpi⋅1=ci+2bi+ai+ci=ai+2bi+2ci\begin{aligned} c_{i+1} &= \sum_{j=0}^{i} dp_j (i+1-j)^2 \\ &= \sum_{j=0}^{i-1} dp_j \big[(i-j)^2 + 2(i-j) + 1\big] + dp_i \cdot 1 \\ &= c_i + 2b_i + a_i + c_i \\ &= a_i + 2b_i + 2c_i \end{aligned}因此非特殊点的状态转移为:(ai+1bi+1ci+1)=(101111122)(aibici)\begin{pmatrix} a_{i+1} \\ b_{i+1} \\ c_{i+1} \end{pmatrix} = \begin{pmatrix} 1 & 0 & 1 \\ 1 & 1 & 1 \\ 1 & 2 & 2 \end{pmatrix} \begin{pmatrix} a_i \\ b_i \\ c_i \end{pmatrix}记此矩阵为 MnonM_{\text{non}}。

4. 特殊点的转移(ii 是标记点)

此时 dpi=0dp_i = 0,不会加入前缀和。从 ii 到 i+1i+1:ai+1=∑j=0i−1dpj=aia_{i+1} = \sum_{j=0}^{i-1} dp_j = a_ibi+1=∑j=0i−1dpj(i+1−j)=∑j=0i−1dpj(i−j)+∑j=0i−1dpj=bi+ai\begin{aligned} b_{i+1} &= \sum_{j=0}^{i-1} dp_j (i+1-j) \\ &= \sum_{j=0}^{i-1} dp_j (i-j) + \sum_{j=0}^{i-1} dp_j \\ &= b_i + a_i \end{aligned}ci+1=∑j=0i−1dpj(i+1−j)2=∑j=0i−1dpj[(i−j)2+2(i−j)+1]=ci+2bi+ai\begin{aligned} c_{i+1} &= \sum_{j=0}^{i-1} dp_j (i+1-j)^2 \\ &= \sum_{j=0}^{i-1} dp_j \big[(i-j)^2 + 2(i-j) + 1\big] \\ &= c_i + 2b_i + a_i \end{aligned}因此特殊点的状态转移为:(ai+1bi+1ci+1)=(100110121)(aibici)\begin{pmatrix} a_{i+1} \\ b_{i+1} \\ c_{i+1} \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 2 & 1 \end{pmatrix} \begin{pmatrix} a_i \\ b_i \\ c_i \end{pmatrix}记此矩阵为 MspecM_{\text{spec}}。

5. 初始状态与答案

初始时 i=0i=0,所有求和为空,按定义 a0=b0=c0=0a_0=b_0=c_0=0。
但我们需要注入 dp0=1dp_0=1。观察 MnonM_{\text{non}} 的第一行:ai+1=ai+cia_{i+1}=a_i+c_i。
若令初始向量为v0=(100)v_0 = \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix}即 a0=1,b0=0,c0=0a_0=1, b_0=0, c_0=0,则经过一次非特殊点转移后:v1=Mnonv0=(101111122)(100)=(111)v_1 = M_{\text{non}} v_0 = \begin{pmatrix} 1 & 0 & 1 \\ 1 & 1 & 1 \\ 1 & 2 & 2 \end{pmatrix} \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix} = \begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix}而根据定义直接计算 i=1i=1 时:a1=dp0=1,b1=dp0⋅1=1,c1=dp0⋅12=1a_1 = dp_0 = 1,\quad b_1 = dp_0 \cdot 1 = 1,\quad c_1 = dp_0 \cdot 1^2 = 1完全吻合。因此初始向量取 v0=(1,0,0)Tv_0=(1,0,0)^T 是编码 dp0=1dp_0=1 的正确方式。最终答案为 dpn=cndp_n = c_n,即最终状态向量的第三个分量。

Vector Log · 算法竞赛学习笔记

Built with Nuxt UI & Nuxt MDC