成外 & 梦熊 CSP-S 模拟赛 3。
除了 T1 是签到题以外,T2、T3、T4 都使我大脑燃烧。
做一个倍增数组,f i , j f_{i,j} f i , j 表示 i i i 走了 2 j 2^{j} 2 j 步后到达的位置,然后对于每一个位置的球,二进制拆分求出最终到达的位置,在最终到达的位置累加即可。
枚举 k k k 切割次数,x x x 切割成的棍木长度。注意到对于所有长度 ≤ 2 k × x \le2^{k}\times x ≤ 2 k × x 的棍木,对答案的贡献都是 ⌊ p i x ⌋ \lfloor\frac{p_{i}}{x}\rfloor ⌊ x p i ⌋ 。再长一点的棍木,对答案的贡献都是 2 k − 1 2^{k}-1 2 k − 1 。k k k 枚举到 log m \log m log m 即可,x x x 枚举到 m 2 k \frac{m}{2^k} 2 k m 即可,这两层时间复杂度 O ( m ) O(m) O ( m ) 。但是后面枚举每根棍木计算 ⌊ p i x ⌋ \lfloor\frac{p_{i}}{x}\rfloor ⌊ x p i ⌋ 是不可能的,所以我们枚举 j = ⌊ p i x ⌋ × x j=\lfloor\frac{p_{i}}{x}\rfloor\times x j = ⌊ x p i ⌋ × x ,把所有 ≥ j \ge j ≥ j 的数字贡献 + 1 +1 + 1 。要统计 ≥ j \ge j ≥ j 的数字,用桶做个后缀和即可。总体时间复杂度 O ( m log m ) O(m \log m) O ( m log m ) 。
设 f i f_i f i 表示前 i i i 个位置的最大得分,显然 f i = max j = 1 i − 1 f j + i − j f_{i}=\max_{j=1}^{i-1} f_{j}+i-j f i = max j = 1 i − 1 f j + i − j ,其中 [ j + 1 , i ] [j+1,i] [ j + 1 , i ] 是红色区间。记 x i x_{i} x i 为 i i i 位置红色数量减去绿色数量,y i y_{i} y i 为 i i i 位置红色数量减去蓝色数量,X i X_{i} X i 和 Y i Y_{i} Y i 分别为它们的前缀和。那么一段区间 [ j + 1 , i ] [j+1,i] [ j + 1 , i ] 是红色区间当且仅当 X i ≥ X j X_{i}\ge X_{j} X i ≥ X j 且 Y i ≥ Y j Y_{i}\ge Y_{j} Y i ≥ Y j 。而对于 X i > X j X_{i}> X_{j} X i > X j 且 Y i > Y j Y_{i}> Y_{j} Y i > Y j 的区间,实际上不是最优解,因为这种区间扩展一格后可以得到更长的长度并且仍然是红色区间。因此只需考虑 X i > X j X_{i}> X_{j} X i > X j 且 Y i = Y j Y_{i}= Y_{j} Y i = Y j ,或者 X i = X j X_{i}= X_{j} X i = X j 且 Y i > Y j Y_{i}> Y_{j} Y i > Y j 的区间。这样题面就变成了二维偏序的形式。对于每一个 X j X_{j} X j ,有对应的 Y j Y_{j} Y j 集合,在集合中找到 Y j < Y i Y_{j}<Y_{i} Y j < Y i 的数中,f j − j f_{j}-j f j − j 最大的那个。这个二维偏序用树状数组即可解决,给每个 X i X_i X i 单独开一个树状数组,Y i Y_i Y i 同理。时间复杂度 O ( n log n ) O(n\log n) O ( n log n ) 。
这题应该是一道矩阵优化递推模板题,但是我完全不会什么矩阵优化递推。
首先要想到本题的 DP 式子。定义 f i f_i f i 为考虑前 i i i 个位置,并且 i i i 位置为一个棍木的结尾时的答案。如果当前位置没有标记,那么 f i = ∑ j = 1 i − 1 f j ( i − j ) 2 f_i=\displaystyle\sum_{j=1}^{i-1}f_j(i-j)^2 f i = j = 1 ∑ i − 1 f j ( i − j ) 2 。否则 f i = 0 f_i=0 f i = 0 。
接下来把这个式子进行矩阵优化(先说结论)。
初始答案矩阵是这样的:
A n s = [ 1 0 0 ] Ans=\begin{bmatrix}
1\\
0\\
0
\end{bmatrix} A n s = 1 0 0 定义以下矩阵:
A = [ 1 0 1 1 1 1 1 2 2 ] A=\begin{bmatrix}
1 & 0 & 1\\
1 & 1 & 1\\
1 & 2 & 2
\end{bmatrix} A = 1 1 1 0 1 2 1 1 2 B = [ 1 0 0 1 1 0 1 2 1 ] B=\begin{bmatrix}
1 & 0 & 0\\
1 & 1 & 0\\
1 & 2 & 1
\end{bmatrix} B = 1 1 1 0 1 2 0 0 1 一次递推,如果一个点没有被标记,就把答案更新为:A × A n s A\times Ans A × A n s ;否则更新为 B × A n s B\times Ans B × A n s 。
注意到最多有 10 5 10^5 1 0 5 个标记点,因此对于连续的一段无标记点,可以用矩阵快速幂加速。时间复杂度 O ( m log n ) O(m\log n) O ( m log n ) 。答案即为 A n s Ans A n s 矩阵的第 3 3 3 行。
你问我这 3 3 3 个矩阵怎么来的,非常抱歉,本人数学不好,不知道怎么来的,我也不会推式子,也看不懂这些矩阵为什么是这样构造的。
设
d p i dp_i d p i 表示前
i i i 个位置被完全覆盖,且在位置
i i i 处放置分割点的方案价值之和。对于位置
i i i ,定义三个辅助前缀和:
a i = ∑ j = 0 i − 1 d p j a_i = \sum_{j=0}^{i-1} dp_j a i = j = 0 ∑ i − 1 d p j b i = ∑ j = 0 i − 1 d p j ⋅ ( i − j ) b_i = \sum_{j=0}^{i-1} dp_j \cdot (i-j) b i = j = 0 ∑ i − 1 d p j ⋅ ( i − j ) c i = ∑ j = 0 i − 1 d p j ⋅ ( i − j ) 2 c_i = \sum_{j=0}^{i-1} dp_j \cdot (i-j)^2 c i = j = 0 ∑ i − 1 d p j ⋅ ( i − j ) 2 显然,当
i i i 不是标记点时,
d p i = c i dp_i = c_i d p i = c i (因为
d p i = ∑ j = 0 i − 1 d p j ( i − j ) 2 = c i dp_i = \sum_{j=0}^{i-1} dp_j (i-j)^2 = c_i d p i = ∑ j = 0 i − 1 d p j ( i − j ) 2 = c i )。
题面并没有直接给出
d p 0 = 1 dp_0=1 d p 0 = 1 。
d p 0 dp_0 d p 0 是我们为了启动递推而人为定义的初始条件。
d p 0 dp_0 d p 0 的含义是:把前
0 0 0 个位置(即空线段
[ 0 , 0 ] [0,0] [ 0 , 0 ] )完全覆盖,并且在位置
0 0 0 处放一个分割点的方案价值之和。
空线段只有一种覆盖方案:什么都不放。
该方案的价值是所有木棒长度的平方的乘积。空线段没有木棒,所以是空乘积。
数学中约定空乘积为
1 1 1 ,因此我们定义:
d p 0 = 1 dp_0 = 1 d p 0 = 1 这个初始条件不是题面直接给出的,而是由“空线段价值 = 空乘积 = 1”的约定推导出来的。
此时
d p i = c i dp_i = c_i d p i = c i 会加入前缀和。考虑从
i i i 到
i + 1 i+1 i + 1 的转移:
a i + 1 = ∑ j = 0 i d p j = a i + d p i = a i + c i a_{i+1} = \sum_{j=0}^{i} dp_j = a_i + dp_i = a_i + c_i a i + 1 = j = 0 ∑ i d p j = a i + d p i = a i + c i b i + 1 = ∑ j = 0 i d p j ( i + 1 − j ) = ∑ j = 0 i − 1 d p j ( i + 1 − j ) + d p i ⋅ 1 = ∑ j = 0 i − 1 d p j ( i − j ) + ∑ j = 0 i − 1 d p j + d p i = b i + a i + c i \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} b i + 1 = j = 0 ∑ i d p j ( i + 1 − j ) = j = 0 ∑ i − 1 d p j ( i + 1 − j ) + d p i ⋅ 1 = j = 0 ∑ i − 1 d p j ( i − j ) + j = 0 ∑ i − 1 d p j + d p i = b i + a i + c i c i + 1 = ∑ j = 0 i d p j ( i + 1 − j ) 2 = ∑ j = 0 i − 1 d p j [ ( i − j ) 2 + 2 ( i − j ) + 1 ] + d p i ⋅ 1 = c i + 2 b i + a i + c i = a i + 2 b i + 2 c i \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} c i + 1 = j = 0 ∑ i d p j ( i + 1 − j ) 2 = j = 0 ∑ i − 1 d p j [ ( i − j ) 2 + 2 ( i − j ) + 1 ] + d p i ⋅ 1 = c i + 2 b i + a i + c i = a i + 2 b i + 2 c i 因此非特殊点的状态转移为:
( a i + 1 b i + 1 c i + 1 ) = ( 1 0 1 1 1 1 1 2 2 ) ( a i b i c i ) \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} a i + 1 b i + 1 c i + 1 = 1 1 1 0 1 2 1 1 2 a i b i c i 记此矩阵为
M non M_{\text{non}} M non 。
此时
d p i = 0 dp_i = 0 d p i = 0 ,不会加入前缀和。从
i i i 到
i + 1 i+1 i + 1 :
a i + 1 = ∑ j = 0 i − 1 d p j = a i a_{i+1} = \sum_{j=0}^{i-1} dp_j = a_i a i + 1 = j = 0 ∑ i − 1 d p j = a i b i + 1 = ∑ j = 0 i − 1 d p j ( i + 1 − j ) = ∑ j = 0 i − 1 d p j ( i − j ) + ∑ j = 0 i − 1 d p j = b i + a i \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} b i + 1 = j = 0 ∑ i − 1 d p j ( i + 1 − j ) = j = 0 ∑ i − 1 d p j ( i − j ) + j = 0 ∑ i − 1 d p j = b i + a i c i + 1 = ∑ j = 0 i − 1 d p j ( i + 1 − j ) 2 = ∑ j = 0 i − 1 d p j [ ( i − j ) 2 + 2 ( i − j ) + 1 ] = c i + 2 b i + a i \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} c i + 1 = j = 0 ∑ i − 1 d p j ( i + 1 − j ) 2 = j = 0 ∑ i − 1 d p j [ ( i − j ) 2 + 2 ( i − j ) + 1 ] = c i + 2 b i + a i 因此特殊点的状态转移为:
( a i + 1 b i + 1 c i + 1 ) = ( 1 0 0 1 1 0 1 2 1 ) ( a i b i c i ) \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} a i + 1 b i + 1 c i + 1 = 1 1 1 0 1 2 0 0 1 a i b i c i 记此矩阵为
M spec M_{\text{spec}} M spec 。
初始时
i = 0 i=0 i = 0 ,所有求和为空,按定义
a 0 = b 0 = c 0 = 0 a_0=b_0=c_0=0 a 0 = b 0 = c 0 = 0 。
但我们需要注入
d p 0 = 1 dp_0=1 d p 0 = 1 。观察
M non M_{\text{non}} M non 的第一行:
a i + 1 = a i + c i a_{i+1}=a_i+c_i a i + 1 = a i + c i 。
若令初始向量为
v 0 = ( 1 0 0 ) v_0 = \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix} v 0 = 1 0 0 即
a 0 = 1 , b 0 = 0 , c 0 = 0 a_0=1, b_0=0, c_0=0 a 0 = 1 , b 0 = 0 , c 0 = 0 ,则经过一次非特殊点转移后:
v 1 = M non v 0 = ( 1 0 1 1 1 1 1 2 2 ) ( 1 0 0 ) = ( 1 1 1 ) 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} v 1 = M non v 0 = 1 1 1 0 1 2 1 1 2 1 0 0 = 1 1 1 而根据定义直接计算
i = 1 i=1 i = 1 时:
a 1 = d p 0 = 1 , b 1 = d p 0 ⋅ 1 = 1 , c 1 = d p 0 ⋅ 1 2 = 1 a_1 = dp_0 = 1,\quad b_1 = dp_0 \cdot 1 = 1,\quad c_1 = dp_0 \cdot 1^2 = 1 a 1 = d p 0 = 1 , b 1 = d p 0 ⋅ 1 = 1 , c 1 = d p 0 ⋅ 1 2 = 1 完全吻合。因此初始向量取
v 0 = ( 1 , 0 , 0 ) T v_0=(1,0,0)^T v 0 = ( 1 , 0 , 0 ) T 是编码
d p 0 = 1 dp_0=1 d p 0 = 1 的正确方式。最终答案为
d p n = c n dp_n = c_n d p n = c n ,即最终状态向量的第三个分量。