做题记录 25.9.8

· · 个人记录

\purple\odot P4229 某位歌姬的故事

先将位置离散化，原本的 [1,n] 划分为 O(q) 个子区间，每个限制都包含若干完整子区间

将限制按其值排序，从小到大枚举值 v，枚举当前值的限制，取出这些限制覆盖到的所有子区间依次排列，则转化为：k 个元素可取 0/1，取 0 和取 1 时各自有权值，给定若干区间，要求每个区间内至少有一个 1，求所有方案的权值和，其中一种方案的权值为所有位置的权值积，所有的 v 对应的权值和之积即为最终答案（注意特殊处理没有限制的位置）

其中取 1 表示对应子区间中存在 a，取 0 表示对应子区间内值都 <a

长度为 l 的子区间取 0 权值为 (v-1)^l，取 1 权值为 v^l-(v-1)^l

设限制的集合为 S，令 f_i 表示 i 位置取 1，1\sim i 的方案数，则转移为

f_i=\sum_{j=\max_{[l,r)\in S,r\le i}l}^{i-1}f_j v_{i,1}\prod_{k=j}^{i-1}v_{k,0}

其中 v_{i,0/1} 表示 i 取 0/1 的权值

答案统计类似

总时间复杂度 O(\sum q^2)，容易优化到 O(\sum q\log q)

代码

参考

\purple\odot P6622 [省选联考 2020 A/B 卷] 信号传递

令 cnt_{i,j} 表示 a_x=i,a_{x+1}=j 的数量，设数字 i 重排后为 p_i，则总时间为

\sum_{i=1}^m \sum_{j=1}^m cnt_{i,j}\left(\begin{cases}p_j-p_i&p_i\le p_j\\ k(p_i+p_j)&p_i>p_j\end{cases}\right)

化为

\begin{aligned} &\sum_{1\le i\le m,1\le j\le m,p_i<p_j}cnt_{i,j}(p_j-p_i)+\sum_{1\le i\le m,1\le j\le m,p_i>p_j}cnt_{i,j}k(p_i+p_j)\\ =&\sum_{i=1}^m p_i \left(\sum_{p_j<p_i}(k \times cnt_{i,j}+cnt_{j,i})+\sum_{p_j>p_i}(-cnt_{i,j}+k\times cnt_{j,i}) \right)\\ \end{aligned}

令 f_s 表示将集合 s 中的数填到 1\sim |s| 位置的最小总时间，则转移为

f_{s\cup \{i\}}\gets f_s+|s\cup \{i\}|\left(\sum_{j\in s}(k \times cnt_{i,j}+cnt_{j,i})+\sum_{j\notin (s\cup\{i\})}(-cnt_{i,j}+k\times cnt_{j,i}) \right)

令 g_{s,i}=\sum_{j\in s}(k \times cnt_{i,j}+cnt_{j,i})+\sum_{j\notin (s\cup\{i\})}(-cnt_{i,j}+k\times cnt_{j,i}) ，g 和 f 转移都容易做到 O(m2^m)

注意到对于一个 i，只会用到 i\notin s 的 g_{s,i}，因此 g 的空间可以做到 m2^{m-1} 个 int，约 400M，可以接受

总时间复杂度 O(m2^m+n)

代码

参考

QOJ #7905. Ticket to Ride

令 w_{i,j} 表示完全包含于 [i,j] 的有贡献区间的贡献和，f_{i,j}/g_{i,j} 表示 [0,j] 中删去 i 条，最后一条删去/不删去的答案，则转移为

f_{i,j}=\max_{k<j}(g_{i,k}+w_{k,j})\\ g_{i,j}=\max(g_{i-1,j-1},f_{i-1,j-1})\\

枚举 i，扫描 j 的过程中，令 t_k=g_{i,k}+w_{k,j}，则一个区间 [l,r,v] 会在 j 扫到 r 的时候令 t_{0\sim l} 加上 v，用 \max t 更新 f，然后算出 g 加入 t 末尾

转化为实现一个支持末尾插入、前缀加非负数、查询全局最大的结构

用并查集维护前缀 \max 的极大等值段即可做到均摊 O(\alpha(n))

总时间复杂度 O(\sum n(n+m)\alpha(n))，用线性序列并查集可以做到 O(\sum n(n+m))

代码

参考