做题记录 26.1.27

· · 个人记录

\textcolor{black}\odot P2305 [NOI2014] 购票

转移方程是显然的，等价于根到当前点的直链的一段后缀上查询一次函数最值

预处理出栈序，则这段后缀等价于出栈序在直链两段的点之间且已经 \text{dfs} 过的全体点，问题转化为线段树每个结点保存一个一次函数，查询区间内一次函数在一点的最值，线段树套李超树即可

时间复杂度 O(n\log n\log V)，空间复杂度 O(n\log n)（注意插入李超树不要递归到叶子）

代码

参考

\textcolor{black}\odot AT_agc040_e [AGC040E] Prefix Suffix Addition

假定所有操作一之和为 b，操作二之和为 c，满足 \forall 0\le i\le n,b_i+c_i=a_i，则操作次数为 \sum_{i=0}^n([b_i>b_{i+1}]+[c_i<c_{i+1}])

令 dp_{i,j} 表示确定了 b_{0\sim i}，满足 b_i=j 时的最小总操作次数，则

dp_{0,0}=0 dp_{i,j}=\sum_{0\le k\le a_{i-1}} (dp_{i-1,k}+[k>j]+[a_{i-1}-k<a_i-j])

令 a_{n+1}=0，答案为 \min dp_{n+1,\ast}

显然 dp_{i,\ast} 单调（假定第二维在 [0,a_i] 中），且极差不超过 2

因此可以将 dp_{i,\ast} 划分为三段，容易做到 O(n)

代码

参考

\textcolor{black}\odot AT_agc049_e [AGC049E] Increment Decrement

对于固定的 a_{1\sim n}，考虑如何求出最小操作次数

令 dp_{i,j} 表示 a_{1\sim i} 中 a_i 被 j 次区间操作覆盖

显然初始 dp_{0,i}=c\times i，答案为 \min_j dp_{n,j}，转移为

dp_{i,j}=|a_i-j|+\sum_k (dp_{i-1,k}+c\times \max(j-k,0))

显然可以用 \text{slope trick}，dp_{i,\ast} 是凸的，斜率在 [-1,c+1] 范围内

初始转折点为 c 个 0，对 a_i 转移时，令斜率为 -1 的部分斜率变为 0，斜率 c+1 的部分斜率变为 c，然后向转折点集合中加入两个 a_i，设操作后转折点集合的最小值为 p（即斜率等于 0 的段的左端点），则这一次操作对最小值的增量为 a_i-p（显然 p\le a_i）

令 S 为转折点的可重集，初始 S 为 c 个 0，i=1 时加入 2 个 a_1 并令贡献加上 a_1-p，i\ge 2 时去掉 S 最小值最大值后加入两个 a_i 并令贡献加上 a_i-p

然后考虑题目的问题

先将 k^{n-1}\sum_i \sum_j b_{i,j} 计入答案，然后枚举 p\in \{b_{i,j}\}，考虑统计出 p 作为 \min S 的出现次数 c，然后答案减去 c\times p

差分为计算 \min S<p 的次数和 \min S<p+1 的出现次数，显然形式相同，只考虑前者

令 b_{i,j} 中 <p 的为 0，\ge p 的为 1，则任意时刻 S 的状态可以由 1 的数量描述，最终 \min S<p 当且仅当 0\in S'

令 ct_i 表示 b_{i,\ast} 中 1 的数量，令 dp_{i,j} 表示第 i 次操作后 S 中 1 的数量为 j 的方案数

初始 dp_{1,0}=k-ct_1,dp_{1,2}=ct_1

$$ dp_{i+1,j}\gets dp_{i,j}\times(k-ct_{i+1}) $$ $$ dp_{i+1,j+2}\gets dp_{i,j}\times ct_{i+1} $$ 方案数为 $\sum_{i=1}^n dp_{i,c+2}\times k^{n-i}

容易做到 O(n^2k^2)

代码

参考

\blue\odot P3188 [HNOI2007] 梦幻岛宝珠

每组 (a,b) 放到 b 位置上，令 dp_{i,j} 表示忽略 2^i 以下的重量，目前选择了 j\times 2^i 的最大价值，转移是容易的

时间复杂度 O(TV^2\log V)

代码

参考

\textcolor{black}\odot CF1290F Making Shapes

等价于求 c_{1\sim n} 的数量满足 c_i\in \N，\sum_i c_i x_i=0，\sum_i c_i y_i=0，\sum_i[x_i>0]c_ix_i\le m，\sum_i[y_i>0]c_iy_i\le m

令 dp_{d,x_1,x_2,y_1,y_2,f_1,f_2} 表示确定了 \sum_i[x_i>0]c_ix_i，-\sum_i[x_i<0]c_ix_i，\sum_i[y_i>0]c_iy_i，-\sum_i[y_i<0]c_iy_i 的低 d 位，它们 d 位到 d+1 位的进位分别为 x_1,x_2,y_1,y_2，其中前两项低 d 位相同，f_1 表示是否超过 m 的低 d 位，后两项低 d 位相同，f_2 表示是否超过 m 的低 d 位

转移时 O(2^n) 枚举 d+1 位上 c_i 的状态，容易 O(1) 转移

总时间复杂度 O((nV)^42^n\log m)，其中 V=|x_i|

代码

参考

\purple\odot P12479 [集训队互测 2024] 长野原龙势流星群 \quad QOJ #9532. 长野原龙势流星群

初始每个点为一个连通块，每次选择平均值最大的一个连通块与其父亲合并，过程中维护每个结点作为根时连通块平均值的最大值

时间复杂度 O(n\log n)

luogu

QOJ

\textcolor{black}\odot AT_agc072_c [AGC072C] Human Exercise

考虑求出前 k-1 次行走后每个格子经过次数，则最后一次的结果容易模拟得到

显然由副对角线互为镜像的两个格子（(x,y) 和 (n-y+1,n-x+1)）经过次数相同，因此只考虑左上部分

显然 (1,1) 经过次数为 k-1，可证经过 (i,j) 的每条路径，下一步以 i+j 为周期，每个周期前 i 步走到 (i+1,j)，后 j 步走到 (i,j+1)

容易做到 O(n^2)

代码

参考