2024.4 做题记录

4.7

CF1648D

设 $d p_{i}$ 为从 $(1, 1)$ 到 $(2, i)$ 的最小代价。答案为 $max d p_{i} + s 3_{n} - s 3_{i - 1}$ 。

$d p_{i} = ma x (max_{l_{x} \leq i} d p_{l_{x} - 1} + s 2_{i} - s 2_{l_{x} - 1} - w_{x}, max_{l_{x} \leq j \leq i} s 1_{j} + s 2_{i} - s 2_{j - 1} - w_{x})$

前面线段树维护 dp 值，按转移顺序区间 max，单点查。后面从后往前枚举 $i$ ，不断加入区间，维护 $max_{x \leq y} a (x) + b (y)$ 。另一个线段树分别维护 $ma x a, ma x b, ma xv$ 。

CF1949F

不合法情况要么完全包含要么不交，建立树形结构。按 $k_{i}$ 大小从小到大排序。实时记录每个爱好 $j$ 对应的最后的人 $f_{j}$ 。枚举 $i$ 的每个爱好 $j$ ，如果最后不合法意味着每个 $f_{j}$ 的爱好都被 $i$ 完全包含，否则找到一组解。如果最后不合法，所有 $f_{j}$ 的爱好数之和为 $k_{i}$ 。

4.16

CF1951F

对于 $i < j$ ，如果 $p_{i}$ >p_j $，无论顺序逆序对贡献为$ 1 $；否则一个逆序对贡献为$ 2 $，顺序对贡献为$ 0 $。构造一些位置上的逆序对数为$ \frac{k−inv(p)}{2}$ 。

abc348g

有决策单调性，主席树上二分。

4.18

CF1542E2

枚举前 $i - 1$ 位相同， $p_{i} = x$ 且 $q_{i} = y$ 。逆序对数的差异只与后 $n - i - 1$ 的排列有关。 $d p_{i, j}$ 表示 $i$ 个数有 $j$ 个逆序对。

$an s = \sum_{i = 0}^{n - 1} A_{n}^{i} \sum_{x = 1}^{n - i - 1} \sum_{y = x + 1}^{n - i - 1} \sum_{j = 0}^{n^{2}} \sum_{k = 0}^{j + x - y - 1} d p_{n - i - 1, j} \times d p_{n - i - 1, k}$

记 $f_{j} = \sum d p_{k}$ 。

$an s = \sum_{i = 0}^{n - 1} A_{n}^{i} \sum_{j = 0}^{n^{2}} d p_{n - i - 1, j} \sum_{x = 1}^{n - i - 1} \sum_{y = x + 1}^{n - i - 1} f_{j + x - y - 1}$

记 $g_{j} = \sum f_{k}$ 。

$an s = \sum_{i = 0}^{n - 1} A_{n}^{i} \sum_{j = 0}^{n^{2}} d p_{n - i - 1, j} \times (g_{j - 2} \times (n - i - 1) - \sum_{x = 1}^{n - i - 1} g_{j + x - n + i - 2})$

记 $h_{j} = \sum g_{k}$ 。

$an s = \sum_{i = 0}^{n - 1} A_{n}^{i} \sum_{j = 0}^{n^{2}} d p_{n - i - 1, j} \times (g_{j - 2} \times (n - i - 1) - h_{j - 2} + h_{j - n + i - 2})$

abc349g

abc349g 题解

最直接的就是并查集倍增将两段区间并起来。

可以用类似马拉车的思路得到一个贪心算法。枚举 $i$ ，用 $ba n_{i, j}$ 记录 $i$ 不能是 $j$ ，维护 $r$ 表示当前已知 $b_{1} \dots b_{r}$ 。如果 $i + a_{i} \geq r$ 就把 $r$ 更新到 $i + a_{i}$ ，否则什么也不做。最后在 hash 判断所有 $a_{i}$ 是不是都满足条件。

4.19

P3380

线段树套 FHQ，查询排名为 $k$ 时二分再查询 $mi d$ 的排名，复杂度 $O (n lo g^{3} n)$ 。

权值线段树套 FHQ，FHQ 维护位置，查询排名为 $k$ 时线段树上二分，复杂度 $O (n lo g^{2} n)$ 。

P7831

拓扑排序转移。当当前是环是拆开 $c$ 最大的边。

CF1778E

按 dfn 序，前缀线性基或合并前后缀线性基。

arc173e

观察到：只能选偶数个，且当 $n = 4 k + 2, k > 0$ 时不能全选。

线性基选偶数个数：插入 $a_{i} \oplus a_{1}$ 。

4.23

P4839

猫树分治，维护 $[l, mi d]$ 的前缀线性基和 $(mi d + 1, r]$ 的后缀线性基。在 $[ql, q r]$ 跨越 $mi d$ 时合并。复杂度 $O (n l o g^{2} n)$ 。

P5607

维护差分数组。区间 $a_{l, \dots, r}$ 的线性基等价于 $a_{l}$ 和 $b_{l + 1, \dots, r}$ 的线性基。

P10282

$d p_{i, j} \to d p_{k, l}$ 。对 $i, j$ 往后的转移按平均值从小到大，一边前缀和一边双指针。

4.25

P6134

如果删去边 $(u, v)$ 后 $u$ 到 $v$ 的路径依然存在，那就删去。bitset 维护可达性。

P3733

先找出最小生成树，线段树分治其他的边，套上线性基维护每个环的最大异或值，见 [WC2011] 最大XOR和路径。

CF938G

P3733 加强。不一定存在一直存在的生成树。线段树分治。记录每个点的父亲和到父亲的边权。对边 $(u, v)$ ，如果 $u, v$ 在同一个联通块，加入线性基；否则 $fd (u)$ 和 $fd (v)$ 连 $w \oplus d i s (u, fd (u)) \oplus d i s (v, fd (v))$ 。

4.26

CF875F

连二选一的两个点，最多允许存在基环树，求最大生成基环树。

CF1666K

每个点拆为 $a_{i}, b_{i}$ ，最小割， $s \to a_{i}$ 表示 $i \in A$ ，否则 $i \in / A$ ； $s \to b_{i}$ 表示 $i \in B$ ，否则 $i \in / B$ 。00 或 11 表示 $i \in C$ 。

P10371

每个数维护 $l_{i, 0/1}, r_{i, 0/1}$ 表示左右第一个、第二个大于 $a_{i}$ 的位置。分类讨论 $p = l, r$ 或 $l < p < r$ 。

4.28

P7497

线段树维护区间未封个数，未封之和，封了的和，封的次数。封过的区间不参与上传下放，解封时从下面上传。

4.30

agc033d

$d p_{i, j, k, l}$ 的答案，复杂度 $O (n^{5})$ 。

注意到答案小于 $lo g nm$ 。交换维度。 $d p_{an s, i, j, l}$ 表示答案为 $an s$ ， $(i, j)$ 到 $(d p_{an s, i, j, l}, l)$ 最大。

$d p_{an s, i, j, l} = max (d p_{an s - 1, i, j, l}, d p_{an s - 1, d p_{an s - 1, i, j, l} + 1, j, l}, max (min (d p_{an s - 1, i, j, k}, d p_{an s - 1, i, k + 1, l})))$

$k$ 维有单调性，双指针。

P7864

结论：一个点存在两个叶子则必胜。

CF1091H

只与和中间点的距离有关， $2 n$ 个 sg 值亦或起来。

发现 sg 值不大，记 $n x t_{j, i}$ 为 $i$ 的后继有 sg 值为 $j$ 的。预处理素数，bitset 转移。

🪴 Quartz 4.0

Explorer