NOI2021 赛前训练日志

训练赛可能是有独立的文章的。这里主要是一些杂题。

离散计数中的迭代思想

题型1：

计算最小的$n$使得$1,\ldots, n$中满足某一条件的数占比大于等于$p$。$0\le p < 1$。

考虑一个迭代的过程。设$f(n)$表示$n$以内满足该条件的数的个数。

若当前的$n$不满足$\frac{f(n)}{n} \ge p$，我们就找到一个最小的$c$使得$\frac{f(n + c)}{n + c} \ge p$，然后令$n \gets n + c$。这样迭代下去直到$n$满足条件。

复杂度与满足该条件的数的分布有关。大多数时候是随机的，跑得应该比较快。

题型2：

有$m$个条件。计算大于等于$n$的同时满足这$m$个条件的数的最小值。

我们设$f(n, i)$表示大于等于$n$的满足第$i$个条件的数的最小值。

那么每次我们令$n \gets \max_i f(n, i)$，直到$n$不发生变化。

复杂度也和数据分布有关。

BalticOI 小丑

双指针 决策单调性

其实双指针的应用前提就是决策单调性。只不过大多数时候双指针的题目使用迭代足以胜任。

给出$n$个点$m$条边无向图，$q$次询问$(l, r)$，问删除编号在$[l, r]$的边后图是否是二分图。$n, m, q\le 2\times 10^5$。

首先我们考虑的是一个前缀和一个后缀的边集的并在一起是不是二分图。这个东西显然具有双指针性质。那么记$f(i)$表示最小的$j$使得$[1, i]$和$[j, m]$的边的并集是二分图。

直接在线维护动态图看起来很不太行。但是直接分治优化决策单调性就可以，思路也很显然，带撤销并查集即可。

另外，带撤销并查集是不能路径压缩的，虽然不知道为啥能过。应该是只能按秩合并的。

复杂度$O(n\log^2n)$。

代码

BalticOI 病毒

AC 自动机 DP 转移优化 最短路

对抗体建 AC 自动机，把抗体结尾的结点 ban 掉。这样就将问题转化为是否存在一种突变使得不会走到 ban 的点，以及满足要求的最短突变长度。

一个初步的想法是设$f(i, j, k)$表示将基因$i$突变展开，且恰能够从 AC 自动机上的状态$j$走到状态$k$的最短展开长度。

这个东西不容易转移。

容易想到改进的方法。将每个突变的每个前缀建点。设$f(i, j, k)$表示将结点$i$突变展开，且恰能够从$j$走到$k$的最短展开长度。

这样就可以写出一些像样的转移。初始状态形如$f(i, x, x) = 0$。

但是容易发现这个转移有后效性。因为 AC 自动机不是 DAG。

那么一个经典的优化是用最短路优化。

但本题的转移其实更为特殊——会出现形如$f(i, x, y) + f(t, y, z) \to f(i + 1, x, z)$的转移。也就是说这个式子既可以理解为$f(i, x, y)$松弛$f(i + 1, x, z)$，也可以理解为$f(t, y, z)$松弛$f(i + 1, x, z)$。

那么如何实现？其实就是最短路优化 DP 的写法。上述特殊的转移并不会增加代码难度，只是笔者认为有必要告知，以辅助思考 DP 的转移方程。

代码

BalticOI 2020 村庄

结论题。不太想写代码。

最小：

• 方法一：树上最大匹配，每个点的贡献是$1$。单点可以找与它相邻的环加进去，贡献是$2$。匹配可以看作二元环。
• 方法二：树形 DP 也可以，相当于子树要么全部匹配要么只剩它一个。

最大：用每条边被遍历的次数算出上界。找到树的重心，删除重心的邻边后做$\frac{n}{2}$个匹配，要求不能是相同的连通块。可以证明这样构造恰好能达到上界。

Julia the snail

分块 莫队 线段树 吉老师线段树 势能分析

有$n$个点，$m$个形如$(l, r)$，其中$l \le r$且$r$互不相同的传送门，表示你可以从结点$l$跳到$r$。

有$q$个询问$(x, y)$其中$x\le y$，问从$x$出发在不经过编号大于$y$的结点的情况下能走到的编号最大的点。

$n, m, q\le 10^5$。

算法一

分块。

假设已知$(x, y)$的答案，记作$ans(x, y)$。

算法 A：考虑求$(x, y + 1)$的答案。那么我们考虑右端点为$y + 1$，左端点大于等于$x$的传送门。如果存在一个这样的传送门其左端点小于等于$ans(x, y)$，那么我们就可以通过这个传送门走到$y + 1$。也就是说我们可以$O(\log)$更新答案。

算法 B：考虑求$(x - 1, y)$的答案。那么我们考虑左端点为$x - 1$，右端点小于等于$y$的传送门，找到其中右端点最大的那个，记作$(x - 1, y')$。那么显然有$ans(x - 1, y) = \max_{x\le z\le y'} ans(z, y)$。因此固定$y$计算询问我们可以倒着枚举$x$，单调栈维护最大值。

将上述两种方法结合。分块后将询问按右端点所在块分类，算法 A 可以简单撤销，所以很容易想到回滚莫队做法。

实际上在结合两种算法后会发现，算法过程中左端点是单调递减的，因此算法 A 可以优化为$O(1)$。

时间复杂度$O(n\sqrt{n})$。

算法二

考虑上述算法 B，直接对右端点做扫描线，记$c_i$表示在当前扫描线状态下左端点为$i$时的答案。

当$y \to y + 1$时，枚举所有以$y + 1$为右端点的传送门，记作$(x', y + 1)$。我们会将$c[1, x']$中所有$\ge x'$的值都赋值为$y + 1$。

也就是说我们会将一个区间里大于等于某个阈值$t$的数赋值为另一个$\ge t$的数。

这个可以用势能分析线段树（吉老师线段树）做。记区间最大值和去重的次大值即可。

实现过程会稍显细节。但只要把握要点就不会写错：pushup 时儿子结点的信息是【同步且正确】的，pushdown 时 儿子结点的信息在这次操作之前是【同步且正确】的。详见代码中的 pushdown 函数。

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

代码

随机点分相关套路

将一棵树随机点分的计数问题有这样一些套路。

随机点分方案数。

将两个连通块连在一起，两者对应的点分树变化只与某些点有关。具体地说，设连上的边是$(u, v)$，两者的点分树根节点分别是$A$和$B$，那么点分方案合并本质上是点分树上$A$到$u$的路径与$B$到$v$的路径合并。因此只需要记$u$和$v$在点分方案中的深度即可完成 DP 转移。时间复杂度$O(n^2)$。详见此文。

随机点分的贡献和。

这个问题视具体情况而定，但通常来讲是难以应用方才讲述的套路的。这种时候可以考虑将贡献均摊到点上，枚举每个点分别计算。

具体来说考虑以下问题：

随机点分，计算点分树上每个结点的子树大小之和的期望。即随机点分期望复杂度。

结点子树大小之和很容易转化为点分树上结点的深度之和，进而将原问题转化为每个结点在点分树上深度的期望之和。

结点$u$在点分树上的深度的期望等价于：枚举一个点$v$，计算$v$是$u$点分树上祖先的概率之和。

要让$v$是$u$点分树上的祖先，那么就要求$v$比$u$到$v$路径上的点（包括$u$）都早删除。

因此不妨定$u$为树根，则深度期望可以简单表示为$\sum_{v \ne u} \frac{1}{\text{dep}_v}$，其中$\text{dep}$表示深度。

时间复杂度$O(n^2)$。可能可以优化。