2024.9 做题记录

9.1

arc108e

当已经选了 $a_{l}, a_{r}$ 时， $(l, r)$ 与外面无关。区间 dp， $d p_{l, r} = \frac{\sum _{k = l, a_{l} < a_{k} < a_{r}}^{r} d p _{l, k} + d p _{k, r}}{n u m _{l, r}} + 1$ 。维护 $n u m_{l, r}, \sum d p_{l, k}, \sum d p_{k, r}$ 转移。

9.2

P5188

模拟赛 T2。

容斥强行不选 $s$ 这些材料，矩阵快速幂。

CF1949H

模拟赛 T3。

按对角线向后推，计算经过次数。不能经过 $3$ 次。经过次数形如 $0, \dots, 0, 1, 2, \dots, 2, 1, 0, \dots, 0$ 或 $0, \dots, 0, 2, 2, 0, \dots, 0$ 。维护两个 $1$ 的位置 $l, r$ 或是不是状态 2。如果 $0, \dots, 0, 1, 2, 1, 0, \dots, 0$ 的 $2$ 被禁止，去到状态 2，否则如果有 $2$ 的位置被禁止则无解。如果 $l, r$ 有被禁止，每次 $2$ 的区间 $(l, r)$ 会增加 $1$ ，否则 $(l, r)$ 会缩短 $1$ ， $2 \times n$ 个对角线后结束。

P10998

按 $d_{u} < d_{v} < d_{w}$ 排序，对于每个 $u$ 对 $(v, w)$ 进行三元组计数。

$m$ 条边的三元组计数 $O (m^{1.5})$ 。如果 $d_{u} \leq m^{\frac{2}{3}}$ ，有 $\sum d_{u} = m$ ，复杂度 $O (m^{\frac{1}{3}} (m^{\frac{2}{3}})^{1.5}) = O (m^{\frac{4}{3}})$ 。否则 $u, v, w$ 至多 $m^{\frac{1}{3}}$ 个，复杂度 $O (m^{\frac{1}{3}} ((m^{\frac{1}{3}})^{2})^{1.5}) = O (m^{\frac{4}{3}})$ 。

P4843

有源汇上下界最小流，建超级源汇点补齐流量，跑最大流，从汇点向源点连容量 $+ \infty$ ，再跑最大流。答案为汇点到源点的流量。

P4043

最小费用可行流，建超级源汇点补齐流量，费用加上下界流量乘代价，从汇点向源点连容量 $+ \infty$ 代价 $0$ 的边。费用加上超级源汇点的最小费用最大流。

CF1288F

将边 $(u, v)$ 拆为 $(u, v, 1, r)$ 和 $(v, u, 1, b)$ ，分别表示红边或蓝边，都不流就不染色。左边的红点的右边的蓝点流出大于流入，连 $(s, i, 1, + \infty, 0)$ ，反之连 $(i, t, 1, + \infty, 0)$ 。最小费用可行流。如果超级源点出边满流则合法。

9.3

P9338

要求前缀和时刻大于零。设 $c_{i}$ 为第 $i$ 个 A 前有多少个 B， $w (l, r) = \sum_{i = l}^{r} ma x (c_{i} - l + 1, 0)$ ，外层 wqs 二分。拆开 max，预处理 $* p_{i}$ 为最小的位置使得 $c_{p_{i}} - i > 0$ ，内层 $d p_{i} = min d p_{j} + s u m_{j} - s u m_{p_{j} - 1} - j \times (i - p_{j} + 1)$ ，斜率优化。

CF2006E

等价于度数 $\leq 2$ 的点到其余点的距离最大值。动态维护直径，每次中心偏移 $1$ ，dfn 序上子树加，全局 min。度数 $= 3$ 就不贡献，度数 $> 3$ 无解。

Q9123

升序排序，二分答案 $x$ 。对于每个 $i$ 可以 $O (n)$ 计算 $(i, j, k)$ 的答案。设阈值 $B$ ，前 $B$ 个的贡献 $O (n B)$ 计算。如果没超过 $k$ ， $B$ 的 $(B, j, k)$ 贡献 $\leq \frac{k}{B}$ 。后边只需要前 $\frac{k}{B}$ 小的 $(j, k)$ 对， $O (\frac{k}{B} lo g n)$ 预处理加 $O (n + \frac{k}{B})$ 计算。 $B$ 取 $\frac{k}{B}$ 。

Q5095

模拟赛 T3。

最优策略决策为从下往上每个人删掉存在的最劣的数。 $O (n^{3})$ 模拟，开始点下移时每个人的决策点单调，复杂度 $O (n^{2})$ 。

9.4

模拟赛 T4

按值从小往大 dp，枚举笛卡尔树子树内哪个位置不被确定。保证数据随机，笛卡尔树深度 $O (n lo g n)$ ，只用以 $2$ 为底的幂， $O ((V))$ 预处理 $O (1)$ 查询。

P9850

容斥，设 $f_{i}$ 为至少 $i$ 条红边的方案，蓝色四元完全子图的数量为 $f_{0} - f_{1} + f_{2} - f_{3} + f_{4} - f_{5} + f_{6}$ ，红色四元完全子图的数量为 $f_{6}$ 。分类讨论，三/四元环计数。

P7386

将一个 $1$ 和 $0$ 捆绑起来。设有 $n$ 个 $01$ 和 $m$ 个 $0$ 。最后一层 $1$ 的贡献为 $(n - 1 n + m - 1)$ 。对于一个 $0$ ，枚举上面有 $i$ 个 $10$ 和 $j$ 个 $0$ ，有 $(i i + j)$ 种可能，即有 $(i i + j)$ 个这样的 $0$ 。 $10$ 同理，算作一个大小为 $2$ 的点。要求形如 $\sum_{i = 0}^{n} \sum_{j = 0}^{m} (i i + j)$ 。有 $\sum_{i = 0}^{n} (m i) = (m + 1 n + 1)$ 。所以 $\sum_{i = 0}^{n} \sum_{j = 0}^{m} (i i + j) = (n + 1 n + m + 2) - 1$ 。lucas 定理计算。

9.5

gym102428J

模拟赛 T3

初始在 $x$ ，先向左走，令 $v l = max_{i = 1}^{x - 1} a_{i}, v r = max_{i = x + 1}^{n} a_{i}$ ，若 $v l < v$ ，答案为 $[x + 1, n]$ 中第一个 $> v l$ 的位置；否则为 $[1, x - 1]$ 中最后一个 $> max (a_{i}, v r)$ 的位置。线段树上二分。

Q7899

模拟赛 T4。

分治。记 $v l_{i} = max_{j = i}^{mi d} a_{j}, v r_{i} = max_{j = mi d + 1}^{i} a_{j}$ ， $[i, j]$ 合法等价于 $max (v l_{i}, v r_{j}) \leq j - i + 1$ ，即 $j \geq i + v l_{i} + 1, i \leq j - r_{j} + 1$ ，按 $i + v l_{i} - 1$ 排序，树状数组维护 $j$ 。正反做一遍得到划分 $[1, i]$ 的答案 $f_{i}$ 和划分 $[i, n]$ 的答案 $g_{i}$ 。

分治维护修改的变化量。当某个 $a_{i}$ 改为 $1$ 时，对于分治区间 $[l, r], l \leq i \leq mi d$ ，当 $v l_{i} > v l_{i + 1}$ 是，区间 $[ll, i]$ 的 $v l$ 值发生变化，合法的 $j$ 发生变化，重新计算 $\sum g_{j + 1}^{'}$ ，和原先应当贡献的 $\sum g_{j + 1}$ 做差。·

9.6

arc165f

模拟赛 T4。

如果 $l_{x} < l_{y}, r_{x} < r_{y}$ 则 $x$ 在 $y$ 前，跑字典序最小的拓扑序。主席树优化建图，优先拓扑主席树点，优先队列拓扑。

9.9

P7230

模拟赛 T4。

对每个左端点维护右端点 $re s_{i}$ 。操作形如删去一个数再加入一个数。如果删掉 $p$ 上的 $a_{p}$ ，找到左右最近的 $l, r$ 使得 $a_{l} = a_{r} = a_{p}$ 。那么 $re s_{l + 1}, \dots, re s_{p}$ 对 $r$ 取 max。实际上要维护 $max re s_{i} - i + 1$ ，因为 $re s_{i}$ 单调，所以相当于线段树上二分找到最左的小于 $r$ 的位置然后区间覆盖。

删除好做，加入难做，考虑线段树分治。先把所有的时刻的 $a_{i}$ 都当作存在，右移右端点维护出所有 $re s_{i}$ 。 multiset 维护每个值出现的位置来求 $l, r$ 。进入一个区间后进行删除操作。撤销操作记录下所有修改和下传的位置和值。

P4617

$u$ 先手胜当且仅当 $u$ 一定在最大匹配上。找出一个最大流， $u$ 一定在最大匹配上当且仅当 $u$ 被选且残量网络缩点后 $u$ 和 $s$ 不在同一强连通分量。

9.10

模拟赛 T2

去掉头尾相等的。枚举回文中心 $i$ ，取最长回文串 $s [l, r]$ ，求最大 $j$ 使得 $s [1, j] = s^{'} [r + 1, r + j]$ 。等价于反串和自己匹配，kmp。翻转再做一遍。

CF1149D

模拟赛 T3。

令 $a < b$ ， $a$ 边构成若干连通块，合法 $b$ 边跨过两个连通块。不能走 $b$ 边离开一个连通块再走 $b$ 边返回， $3 a > 2 b$ ，只有 $s i z > 3$ 的连通块有用，状压，最短路， $2^{\frac{n}{4}} m lo g 2^{\frac{n}{4}} m$ 。

9.11

P6684

模拟赛 T4。

等价对于每个 $r$ 求最小的 $l$ 使得 $[1, l]$ 和 $[r, m]$ 的边能组成奇环。将边复制一遍接在后面，即对于每个 $i$ 求最小的 $p$ 使得 $[i, p]$ 间的边组成奇环。 $p$ 有单调性。依次求每个 $i$ ，每次右移 $p$ ，加入的这条边 $p$ 会在求 $[i, p]$ 时都有贡献。插入容易删除困难，用线段树分治。初始没有边，分治到 $i$ 时会对之后一个区间加入若干条边，一共加边 $m$ 次。

P7307

答案为最大度数。允许误差，每次将边集一分为二。希望将每个点度数除以 $2$ 上取整，在左右部点各建一个虚点，将度数补齐为全是偶数，存在欧拉回路，将相邻的边分开得到两个边集，分别递归。 $lo g max d_{i}$ 轮后 $max d_{i} = 1$ ，将此时边集中的点染成一种颜色。

ucup 记录

9.12

joisc2017e

将 $x$ 三进制拆分， $0 \to 01, 1 \to 10, 2 \to 11$ ，如果 $i$ 或 $i + 1$ 被影响就不选。两边用同个随机排列来遍历数组，并尽量利用坏段。

Q9237

先补一个 $0$ ，在一直补 $1$ 至 $1024$ 。还原时把最后一个 $0$ 以后扔掉。有 $16 \times 66 = 1056$ 个有效位，要用 $1056 - 1024 = 32$ 位说明哪些位置被控制。令 $c_{i} = 0$ 后最近的 $c_{j} = 0$ ，前 $j - i - 1$ 条信息第 $i$ 位为 $0$ ，第 $j - i$ 条信息第 $i$ 位为 $0$ 。还原时可以建图，找 $31$ 个点的内向基环树的长为 $16$ 的环，是唯一的。

agc034e

记 $s u m = \sum_{c_{i} = 1} d i s_{i, x}$ ，每步 $s u m$ 减小 $2$ 最优。维护 $m n_{u}, m x_{u}$ 表示最多最少能将 $u$ 子树内 $\sum_{v = s u b t ree (u), c_{v} = 1} d i s (u, v)$ 变为多少。讨论最大的子树是否大于一半。

arc110e

用异或表示。令 $a \to 1, b \to 2, c \to 3$ ， $f (s) = \oplus s_{i}$ 不变。设 $d p_{i}$ 为划分 $s [1, i]$ 的方案，枚举最后一个字符是什么。

P6790

广义串并联图。删 $1$ 度点，缩 $2$ 度点，叠合重边。记 $f_{i}$ 为第 $i$ 条边在生成树上的方案数， $g_{i}$ 为不在的方案数。删一度点， $f_{i}$ 乘进答案；缩 $2$ 度点， $f_{i} = f_{u} f_{v}, g_{i} = f_{u} g_{v} + f_{v} g_{u}$ ；叠合重边， $f_{i} = f_{u} g_{v} + f_{v} g_{u}, g_{i} = g_{u} g_{v}$ 。

9.13

模拟赛 T4

建 trie 树。先假设全选 $A$ ，计算答案与 $\sum d_{i} A c_{i}$ 的差值。按 dfn 序转移，设 $d p_{i}$ 为上一个单词在 $i$ 的答案， $d p_{x} = max d p_{i} + (B - d e p_{l c a - 1} A) c_{x}$ 。李超线段树维护转移。

9.14

abc308h

枚举连向环外的点 $u$ 。在挖掉 $u$ 的子图中求全源最短路，答案为 $min d i s_{x, y} + e_{u, x} + e_{u, y} + min_{i \neq = x, i \neq = y} e_{u, i}$ 。线段树分治，加入点时进行松弛操作。复杂度 $O (n^{3} lo g n)$ 。

9.15

模拟赛 T4

Boruvka 算法。每次对于每个连通块找到最小的到连通块外的边，全部连起来。每次连通块数量减半。将矩阵加对对角线翻转，扫描线找到每个 $i$ 的最小边。线段树分别维护最小值和连通块不同的次小值。

9.16

CF901D

模拟赛 T3。

找出一颗生成树，满足除了根以外的所有点。调整根，只有奇环有用。只要有一个奇环， $a_{1}$ 就可以减去 $2 \times v a l$ 。因为保证 $a_{1}$ 和 $d_{1}$ 奇偶性相同，找一颗 bfs 的生成树即可。

9.18

Q8948

模拟赛 T3。

对于一个菊花，有 $n 0$ 个黑色儿子， $n 1$ 个白色儿子， $n 0 > n 1$ 当做 $n 0 - n 1 + 1$ 个黑； $n 1 > n 0$ 当做 $n 1 - n 0 - 1$ 个白；否则若 $n$ 为偶 Bob 要先走当做黑；否则当做白。

P10214

模拟赛 T4。

设 $d p_{u}$ 为 $u$ 被投出时的票数， $(d p_{u}, u)$ 和 $(d p_{v}, v)$ 较大者先出。 $u$ 的儿子 $v$ 影响 $d p_{u}$ 。对 $v$ 按投出先后排序，二分一个前缀在 $u$ 前被投出，即 $a_{u} + \sum b_{v} - s_{i - 1} > d p_{v_{i}}$ 。平衡树维护每个点的儿子，支持插入删除二分。

此时单点修改复杂度为 $O (d e p)$ 。重链剖分，求出 $u$ 在轻儿子中二分的结果 $an s$ ，若 $an s > d p_{so n}$ ， $d p_{u} = an s$ ；否则在轻儿子中二分 $a_{u} + \sum b_{v} - b_{so n}$ 。 $d p_{u}$ 为关于 $d p_{so n}$ 的分段常函数，段数为 $2$ ，可以合并。线段树维护重链信息乘积，修改时改链顶父亲的轻儿子的平衡树，查询时从链底 dp 值加上区间信息求 dp 值。

9.19

CF1647F

模拟赛 T3。

假设一个最大值为左边峰顶。设 $f_{i}$ 表示前缀 $[1, i]$ ，一个序列在 $i$ ，另一个序列最小在哪里。 $g_{j}$ 为后缀。从左边峰顶到 $n$ 枚举右边峰顶，设 $d p_{i, 0/1}$ 表示当前左/右序列在 $i$ ，另一序列的最大最小值。

CF1494F

模拟赛 T4。

最后是菊花，枚举菊花中心 $u$ ，删去与 $u$ 连边的奇度数点找欧拉路径。

9.23

CF1635F

模拟赛 T3。

枚举可能贡献的答案对的较大值，只有左右第一个比 $i$ 小的 $j$ 才有贡献。

CF1784F

模拟赛 T4。

被删除的连续段长度一定是偶数；不会删去 $n + k$ 以后的数；第二段关于中心对称。

枚举第一段长度 $i$ ， $2 i < n$ ，枚举第二段在 $n$ 左侧长为 $j$ 。 $\sum_{i = 0}^{k} [2 i < n] \sum_{j = 0}^{m i n (k - i, n - 2 i - 1)} (k - i - j i)$ 。下指标关于 $i$ 变换量为 $O (1)$ ， $\sum_{i = l}^{r} (i p) = 2 \times \sum_{i = l}^{r} (i p - 1) - (r p - 1) + (l - 1 p - 1)$ 。否则剩余长度 $n + k - 2 i - 1$ ，剩 $k - i$ 次操作， $(k - i n + k - 2 i - 1 - ( k - i ))$ 。

arc184b

对于不是 $2, 3$ 倍数的 $i$ ，将 $\frac{n}{i}$ 中的 $2^{a} 3^{b}$ 找出来，每次加入 $(a, b), (a + 1, b), (a, b + 1)$ ，有 $lo g_{3} n$ 级别宽的网格。状压 $d p_{i, j, s}$ 表示前 $i - 1$ 行已经选完，第 $i$ 行选到 $j$ 列，当前面上状态为 $s$ 。 $\frac{n}{i}$ 只有 $O (n)$ 级别，可过。

9.24

模拟赛 T4

扫描线维护编号较小的最大编号为 $i$ ，点边容斥强行选 $i$ ，主席树维护矩阵。交换 $a_{x}, a_{x + 1}$ 时重新做第 $x, x + 1$ 棵主席树即可。

9.25

【5校day1】构造题

从右上往左下确定每个点的颜色。对于点 $u$ 最多有 $4$ 个入边。如果不包含所以颜色，就赋没有出现的颜色。否则如果 $v 1, v 3$ 通过 $co l_{v 1}, co l_{v 3}$ 的连通块联通，那么 $v 2, v 4$ 一定不通过 $co l_{v 2}, co l_{v 4}$ 的连通块联通。

【5校day2】祖先

设 $s_{u}$ 为 $\sum_{v \in s u b t ree (u)} a_{v}$ ，答案为 $\frac{s _{u}^{2} - a _{u}^{2} - \sum _{v \in so n (u)} s _{v}^{2}}{2}$ 。单点加为链加。类似动态 dp 维护轻儿子处的 $\sum s_{v}^{2}$ 。区间加单点查。子树加，先加上 $u$ 到根的贡献，再打上子树 tag，维护 $0/1/2$ 次方和。树剖时先进入重儿子，再去到每个儿子，再进入轻儿子子树。

9.26

joisc2020q

模拟赛 T4。

对 $∣ t_{i} - t_{j} ∣ \leq r_{i} - l_{j} + 1$ 连 $i \to j$ 求 $1 \to n$ 的最短路。边权赋在点上，一个点只入队一次。按 $t_{i}$ 建线段树，取出合法的 $v$ 并删除。

【5校day5】签到题

先二分出 $c n t_{a}, c n t_{b}, c n t_{c}$ ，令 $c n t_{a} \leq c n t_{b} \leq c n t_{c}$ 。先将序列放 $c n t_{a}$ 个 $a$ ，每次加一个 $b$ ，每次加一个 $c$ 。次数为 $2 c n t_{a} + 2 c n t b_{c} n t c \leq \frac{5}{3} n$ 。

9.27

模拟赛 T3

dij 状求答案，与除去 $(u, v)$ 的 $u \to t$ 最短路相关。找出最短路树，非树边进行路径取 min。

模拟赛 T4

有决策单调性，二分栈，主席树维护前 $k$ 大的和。统计答案，只有不交区间有贡献，区间对区间 $k$ 大取 min，如果一个点最后的值小于自己的值就可以选。

9.29

模拟赛 T4

每个位置对答案的贡献为向下递归的层数。设 $\leq i$ 的数最后出现在 $p_{i}$ ， $(i, i + 1)$ 被断开的层为 $p_{i} - i$ 。 $i$ 的贡献为 $max (p_{i - 1} - (i - 1), p_{i} - i)$ 。取到后面的为 $a_{p_{i}} = i$ 。

$an s = \sum_{i} (n - i)! (\sum_{j} (i - 1 j - 1) (i - 1)! (j - i) + (i j) (i! - (i - 1)!) (j - i + 1))$

上指标求和，最后只与 $i$ 有关的式子。

9.30

CF1648F

模拟赛 T4。

建出 dfs 树，非树边赋随机权值，随机异或哈希。如果割两条树边，只能是 $h s h_{u} = h s h_{v}$ 。相同的 $h s h_{i}$ 都在到根的链上，且有决策单调性，对于每个相同权值放在序列上分治。两边 $(u, f a_{u}), (v, f a_{v})$ 的答案为：跨过 $u$ 的点对减跨过 $v$ 的点对加两倍没有跨过 $u$ 但跨过 $v$ 的点对。后面的贡献在 dfs 序上维护主席树，在两点处 $+ 2$ ，lca 处 $- 4$ 。

Explorer

2024.9 做题记录

9.1

9.2

9.3

9.4

9.5

9.6

9.9

9.10

9.11

9.12

9.13

9.14

9.15

9.16

9.18

9.19

9.23

9.24

9.25

9.26

9.27

9.29

9.30

Graph View

Table of Contents

Backlinks