做题记录 25.5.4

szt100309 · 2025-05-04 12:50:34 · 个人记录

\blue\odot CF1874C Jellyfish and EVA

令 f_i 表示 i 能到达 n 的概率

从 u 开始，设 u 直接连向的点集为 S，则最优策略为按 f_u 从大到小选择 S 中的 u，证明

令 g_{d,i} 表示一个出度为 d 的点最终选择了 f 值第 j 大的出边的概率

设 u 的出边按 f 从大到小排序后为 p_{1\sim d_u}，则 f 的转移为

f_u=\sum_{i=1}^{d_u} f_{p_i} g_{d_u,i}

$$ g_{d,1}=\frac1d\\ g_{d,i}=g_{d-2,i-2}\times \frac{i-2}d+g_{d-2,i-1}\times \frac{d-i}d $$ 总时间复杂度 $O(\max n^2 +\sum m\log n)

代码

参考

位运算每一位相互独立，当 (a_i,b_i,m_i) 相同时 (c_i,d_i) 必须相同，否则无解

这样限制可以表示为八维五进制数，从低到高分别表示 (a_i,b_i,m_i)=(0,0,0),(0,0,1),(0,1,0),\cdots,(1,1,1) 时对应的 (c_i,d_i) 为 (0,0) / (0,1) / (1,0) / (1,1) / 无限制

因此预处理 (a,b,m)=(11110000,11001100,10101010) 的转移即可，时间复杂度 O(2^{16}\times8+5^8\times8+t\log V)

代码

参考

令 dp_{i,j} 表示 [1,i] 能否令异或和为 j，显然暴力实现为 O(n^3)

转移时仅考虑极小区间（不存在严格子区间使得其 \text{mex} 等于原区间的区间称为极小的）

定理：极小区间的数量为 O(n) 的

证明：

对于一个极小区间 [l,r]，若 l\ne r，则 a_l\ne a_r，否则去掉 a_l 或 a_r 一定不改变 \text{mex}
显然 \text{mex}(a_{l\sim r})>a_l，否则必有 \text{mex}(a_{l\sim r})<l，a_l 可去掉，一定不是极小的
假定存在 R>r 使得 a_l>a_R 且 [l,R] 为极小的，由于 a_R<a_l<\text{mex}(a_{l\sim r})，因此 a_R\in\{a_{l\sim r}\}，即 a_R 可以去除，一定不是极小的
即一个 l 至多对应一个 r 满足条件
这样极小区间数量不超过 3n

时间复杂度 O(n^2)

代码

参考

令 F(x) 为所有完全二叉树中，路径上点权最大值 \le x 的数量的总和，则答案为 mF(m)-\sum_{i=1}^{m-1}F(i)

令 p_n=m^n，f_n 为所有 n 个点的完全二叉树中路径上点权最大值 \le x 的数量的总和，g_n 为所有 n 个点的完全二叉树中路径上点权最大值 \le x 且一端为根的数量的总和

则 p_0=1,f_0=g_0=0，若 n\ge 1，设两子树大小分别为 L,R，则转移为

p_n=mp_Lp_R\\ g_n=x(p_Lg_R+g_Lp_R+p_Lp_R)\\ f_n=mf_Lp_R+mp_Lf_R+g_n+xg_Lg_R\\

记忆化搜索可做到 O(\sum m\log n)

代码

参考