做题记录 25.3.21

· · 个人记录

\purple\odot CF1983E I Love Balls

有 n-k 个普通的球，奇数位上的计入 \text A，偶数位上的计入 \text B，前者比例为 \frac{\lceil\frac{n-k}2\rceil}{n-k}，后者比例为 \frac{\lfloor\frac{n-k}2\rfloor}{n-k}

这 n-k 个普通球形成 n-k+1 个空隙，每个特殊球要放入一个空隙，若放入奇数位上的则计入 \text A，放入偶数位上的计入 \text B，前者比例为 \frac{\lceil\frac{n-k+1}2\rceil}{n-k+1}，后者比例为 \frac{\lfloor\frac{n-k+1}2\rfloor}{n-k+1}

设 sx 为普通球权值和，sy 为特殊球权值和，则 \text A 的期望权值和为 \frac{\lceil\frac{n-k}2\rceil}{n-k}sx+\frac{\lceil\frac{n-k+1}2\rceil}{n-k+1}sy，\text B 期望权值和为 \frac{\lfloor\frac{n-k}2\rfloor}{n-k}sx+\frac{\lfloor\frac{n-k+1}2\rfloor}{n-k+1}sy

时间复杂度 O(\sum n)

代码

参考

\blue\odot CF1984E Shuffle

相当于每次取出一个大小 >1 的连通块，删掉其中一个点，最大化最终剩下的连通块数量，若第一次选择的为叶子则再加一

显然最终剩下的一定为原树的一个独立集，且可证每个独立集都可通过一定顺序次操作得到

可证一定存在一种最优情况使得第一次选择的为叶子

问题转化为求出树可同时选择一个叶子和其父亲情况下的最大独立集大小

先一次 dp 求出 f_{i,0/1} 表示子树 i 内是否选择 i 时的最大独立集

然后换根 dp 求出 g_{i,0/1} 表示整棵树是否选择 i 时的最大独立集

答案为 \max_{i\in L} g_{i,0}+1，其中 L 为叶子集合

时间复杂度 O(n)

代码

参考

\purple\odot CF1982F Sorting Problem Again

假设不完全有序，则左端点为 最大的 p 满足 a_{1\sim p} 有序且 \forall t>p,a_t\ge a_p 加一，可以线段树上二分求出，时间复杂度 O(\log n)，右端点同理

总时间复杂度 O(n+q\log n)

代码

\blue\odot CF1982E Number of k-good subarrays

数位 dp

对于给定的 k，令 (l,r,rs,L) 表示一个区间，左侧 l 个和右侧 r 个的 \text {popcount} 都 \le k，区间内合法连续段数量为 rs，区间长度为 L

区间信息合并是容易的

令 dp_{n,k} 表示 [0,2^n) 取 k 时的信息，转移为 dp_{n,k}=dp_{n-1,k}+dp_{n-1,k-1}，其中 + 为信息并，注意边界情况

对于一组询问 (n,k)，令 n=2^a+2^b+\cdots，其中 a>b>\cdots，则 [0,n) 可拆为 [0,2^a)，[2^a,2^a+2^b)，\cdots，依次合并 dp_{a,k}，dp_{b,k-1}，\cdots 即可

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

代码

\purple\odot CF1981E Turtle and Intersected Segments

若三条线段两两相交，设按 a 从小到大排序为 s_1,s_2,s_3，则 s_1 和 s_3 之间的连边无效

扫描数轴，l 处加入，r+1 处删除（同位置先删除再加入），则每次加入时需要向以 a 排序的前驱后继连边

这样总边数为 O(n) 的，直接计算 \text {MST} 即可

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

代码

参考

\blue\odot CF1980G Yasya and the Mysterious Tree

令 xt 为全局异或标记，令 ds_u 表示原树中 u 到根的路径上边权异或和，则询问 (u,x) 相当于查询 \max_{v\ne u} x\oplus ds_u\oplus ds_v\oplus[dep_u\equiv dep_v\pmod 2]

对于 dep\equiv 0 和 dep\equiv 1 的分别用 \text {Trie} 维护即可，注意查询时要先撤销 x，求出答案后再加入

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

代码

\blue\odot CF1980F2 Field Division (hard version)

对于不给任何喷泉的情况，显然直接单调栈即可，对于给一个喷泉的情况，暴力枚举这个喷泉覆盖的（单调栈扫描过程中由于它而弹出的）位置，类似地计算即可，时间复杂度 O(\sum k\log k)

瓶颈在于扫描前的排序

代码