做题记录 25.10.19
szt100309
·
·
个人记录
\textcolor{blue}\odot P14154 [ICPC 2022 Nanjing R] 索道 \quad QOJ #5415. Ropeway
令 f_i 表示 [0,i] 中强制选择 i 的情况下的答案，g_i 表示 [i,n+1] 中强制选择 i 的情况下的答案，两者容易单调队列 O(n) 求出
对于修改 (p,v)，若 p 必选则答案为 f_{n+1}-a_p+v，否则令 pr_p,sf_p 为 p 前一个与后一个必选位置，答案为 \min(\min f_{\max(pr_p,p-k)\sim p-1}+v+\min g_{p+1\sim \min(sf_p,p+k)},\min_{\max(pr_p,p-k)\le x\le p-1}\min_{p+1\le y\le \min(sf_p,p+k),y-x\le k}(f_x+g_y))，容易做到 O(k)
总时间复杂度 O(n+qk)
代码：luogu \quad QOJ
参考
\purple\odot P11802 【MX-X9-T6】『GROI-R3』Graph
先考虑如何判定给定的 \{P\} 是否合法
定理：一个长度为 p 的置换的 c 次方得到 \gcd(p,c) 个长度为 \frac n{\gcd(p,c)} 的环
对于环长 i，考虑什么样的数量 j 使得存在 l 令 \frac l{\gcd(l,c)}=i 且 \gcd(l,c)\mid j，即当长度为 i 的环数量为 j 时，在 c 次变换下，它们可以拼为若干更大的环
定理：j 合法当且仅当 p\mid j，其中 p 为满足 \frac l{\gcd(l,c)}=i 的 \gcd(l,c) 的最小值，即满足 p=\gcd(p\cdot i,c) 的最小值
证明：
- 对于合法的 p，p=\gcd(p\cdot i,c)\iff p\mid c\land \gcd(i,\frac cp)=1
- 设 p 分解为 \prod {Pr_i}^{\alpha_i}，其中 Pr_i 为第 i 个质数，设 i 分解为 \beta，c 分解为 \gamma
- 则上述条件等价于 \forall i，有 \alpha_i\le \gamma_i 且 \min(\beta_i,\gamma_i-\alpha_i)=0
- 若 \beta_i=0 则 \alpha_i\le \gamma_i，否则 \alpha_i=\gamma_i
- 假如 q 也合法，其分解为 \alpha'，取 r=\gcd(p,q)，其分解为 \alpha^\ast_i=\min(\alpha_i,\alpha'_i)，显然同样满足条件
- 因此对于合法的 p,q，\gcd(p,q) 一定合法
- 由此易证原命题成立
预处理 p_i，表示对于确定的 i，合法的 p 的最小值，这部分时间复杂度为 O(nc\log n)
设 \{P\} 中长度为 i 的环的数量为 r_i，则要求每个 r_i 都能表示为若干 p_l 的倍数之和，其中 l 为 i 的倍数，显然等价于 r_i 为 p_i 的倍数
因此 \{P\} 合法当且仅当 \forall i,p_i\mid r_i
然后考虑题目给定的不完整排列
求出 l_i,r_i,m 表示长度为 i 的链数，长度为 i 的环数，孤点数
需要将 l_i 和 m 组合为若干环，使得最终的 r_i 为 p_i 的倍数，显然根据题目的限制，一个环只能由一条链加若干孤点，或完全由孤点组成，令最终的 r 为 r^\ast
令 f_{i,j,k} 表示确定了 r^\ast_{1\sim i}，目前有 j 条长度为 i 的链（可能由之前若干链和孤点拼接），剩余 k 个孤点的方案数
初始 f_{0,0,m}\gets 1，答案为 f_{n,0,0}，考虑转移
从 f_{i-1,j,k} 到 f_{i,\ast,\ast}，转移分为两步
先将 j 条长度为 i-1 的链增长至 i，并加入长度为 i 的 l_i 条链，转移为 g_{j+l_i,k-j}\gets f_{i-1,j,k}\cdot P_k^j（加入的点接在链末尾，因为是环，不用考虑接在头部的情况）
然后将这 i 条链和若干孤点组合为长度为 i 的环，枚举链组成 J 个环，孤点组成 K 个环，转移为
f_{i,j-J,k-Ki}\gets [J+K+r_i\equiv 0\pmod {p_i}]\binom jJ\cdot \frac{A_k^{Ki}}{i^KK!}\cdot g_{j,k}
其中 \frac{A_k^{Ki}}{i^KK!} 为 Ki 个点组成 K 个长度为 i 的环的方案数，i^K 为每个环循环同构的系数，K! 为环之间顺序的系数
暴力实现复杂度为 O(\sum_{i=1}^n \frac mi
\cdot \frac ni\cdot \frac ni\cdot m)=O(n^4\sum_{i=1}^n \frac 1{i^3})=O(n^4)
考虑优化最后的转移
枚举 x\in [0,p_i)，考虑所有 J\equiv x\pmod{p_i} 的转移
令 h_{j-J,k}\gets g_{i,k}\binom jJ，则
f_{j,k-Ki}\gets h_{j,k}\cdot \frac{A_{k}^{Ki}}{i^KK!}
时间复杂度 O(n^3)，常数极小，可过
代码
参考：1 \quad 2
\blue\odot P14015 [ICPC 2024 Nanjing R] 生日礼物
若不存在 2，令奇数位异或上 1，则每次操作删除相邻的 01，答案为 0 和 1 的数量之差，尽量用 2 抵消掉两者之差即可，时间复杂度 O(\sum |s_i|)
代码
\blue\odot P13968 [VKOSHP 2024] Classics
通过平衡树求出每个数在最终序列中的位置
令 f_i 表示目前为止 [1,i] 内 \text{LIS}，加入位置 p 时令 f_p\gets \max f_{1\sim p-1}+1
时间复杂度 O(n\log n)
代码
参考