做题记录 25.4.24

· · 个人记录

\purple\odot CF1903F Babysitting

二分 k，转化为 2-\text{SAT}，线段树优化建图即可

时间复杂度 O(n\log^2 n+m\log n)

由于除了首尾外点连向的区间长度固定，因此按区间长度减一分块，则连向的区间必为一段前缀加一段后缀，这样边数是 O(n+m) 的，时间复杂度 O((n+m)\log n)

代码

参考

\purple\odot (Jiandan) Mua (I) - Lexical Analyzer

正则表达式即可

代码

参考

\blue\odot CF1903D2 Maximum And Queries (hard version)

令 S=\sum a_i

当 k+S\ge n\times 2^{20} 时答案为 \lfloor\frac{k+S}n\rfloor

预处理 f_{p,v} 表示二进制下第 p 位为 0 且值为 v 的超集的 a_i 数量，g_{p,v} 表示这些数的低 p 位之和，通过高维后缀和容易 O(V\log^2 V) 求出两者

从高到低贪心，设目前需要确定第 i 位，已经确定的高位为 s，剩余可用增加量为 k

若第 i 位填 1，则 f_{i,s} 个数需要把第 i 位变为 1，低 i-1 位清空，这部分需要 f_{i,s}\times 2^i-g_{i,s} 步，记高位中已经这样操作了的 f 之和为 t，则这 t 个数各自需要 2^i 步，其余数不变，因此若 k\ge f_{i,s}\times 2^i-g_{i,s}+t\times 2^i 时这一位可以为 1，同时跟新相关值

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

代码

参考

\purple\odot CF1902F Trees and XOR Queries Again

拆为两条直链，对于每个点求出根到它路径的前缀线性基，在 \text{lca} 处合并即可

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

代码

\blue\odot CF1898F Vova Escapes the Matrix

对于 1 型点答案为 \text{.} 的数量，对于 2 型点答案为 \text{.} 的数量减去 \text{V} 到出口的最短距离

对于 3 型点，每格空地求出它到最近的出口和次近的出口的距离，答案为 \text{.} 的数量减去 到最近出口的距离，到次近出口的距离，到 \text{V} 的距离之和 的最大值

时间复杂度 O(\sum nm\log nm)，实际上代码中的 \text{dijkstra} 可以改成 \text{bfs}，时间复杂度为 O(\sum nm)

代码

参考

\purple\odot CF1896F Bracket Xoring

显然每次操作都会同时翻转 1 和 2n 位置，因此若两者不同则必然无解

由于匹配的括号串长度为偶数，因此每次都翻转长为偶数的串，串中 1 的数量奇偶性不变，因此若初始有奇数个 1 则必然无解

若 1 位置为 0，则操作 ()()\cdots() 使得整个串都翻转

此时 1 和 2n 位置都是 0，考虑令中间的每个 s_{2i} 都等于 s_{2i+1}

若 s_{2i}=s_{2i+1} 则这两个位置放置 ()，否则放置 (( 或 ))，具体只要匹配即可

这样每个 () 外有若干个 ((\cdots)) 和最外层的一个 (\cdots)，总变换次数为偶数，即不变，对于 (( 只有后一个位置变换，对于 )) 前一个位置变换

显然变换后满足 s_{2i}=s_{2i+1}

然后考虑将整个字符串置 0

此时 s_1 和 s_{2n} 都是 1，1 的数量为偶数，任意两个 1 之间都有奇数个 0，令 1 位置放置 (，2n 位置放置 )，若 s_{2i}=s_{2i+1} 都是 1 则放置 )(，否则放置 ()

显然变换后符合要求

时间复杂度 O(\sum n)

代码

参考

\purple\odot CF1895F Fancy Arrays

差分为 \min a_i\le x+k-1 的方案数减去 \max a_i<x 的方案数

对于前者，发现确定了 \min a_i 和差分数组后有且仅有一组合法的 a_i 与之对应，\min a_i 有 x+k 种选择，差分数组有 (2k+1)^{n-1} 种选择，总方案数为 (x+k)(2k+1)^{n-1}

对于后者，容易矩阵快速幂优化 dp 实现，时间复杂度 O(k^3\log n)

总时间复杂度 O(k^3\log n)

代码

参考