MENU

做题笔记 2024 NFLS NOI 模拟赛

2024.5.21

树数术

给一颗 $n$ 个点的树和一个长为 $m$ 的序列 $a_{1\dots m}$,序列中每个数表示树上的一个节点。$q$ 次询问,每次询问给出 $a$ 的 $k$ 个子区间,将这 $k$ 个子区间顺次拼接成新的序列,求新序列上有多少个数是前缀 $\operatorname{lca}$。


假设 $n,m,\sum k$ 同阶。查多个区间的拼接和查一个区间没什么本质区别。

前缀信息可以用兔队线段树维护。使用 $O(n\log n)-O(1)$ 的 $\operatorname{lca}$ 容易将总复杂度做到 $O(n\log^2 n)$。这里注意兔队线段树可以在线段树结点上只维护右儿子的信息,这样不需要信息的可减性,但是如果维护整个结点的信息可以在查询时增加一些剪枝,从而优化一定的常数。本题只维护右儿子信息应该会被卡常。

查询前缀信息在不强制在线时可以离线之后用扫描线 + 二分解决。本题用这种方式容易做到 $O(n\log n)$。

Perotation

给一个 $1\sim n$ 的排列 $a$。定义一次操作为选取连续的三个数 $a_{i-1},a_i,a_{i+1}$,要求 $a_{i-1}<a_{i}<a_{i+1}$,然后将他们分别修改为 $a_{i+1},a_{i-1},a_i$。$q$ 次修改,每次修改交换 $a_x,a_y$,然后求最长的 $a$ 的后缀满足其能够从一个单调递增的序列通过若干次操作得到。


一个序列是满足条件的当且仅当每个数后面比他小的数的个数均为偶数。于是我们试图维护 $r_i$ 表示 $a_i$ 后面比 $a_i$ 小的数的个数的奇偶性,询问相当于查序列上最后一个 $1$ 的位置。

考虑分块。不妨设 $a_x<a_y$,则一次修改会对满足 $x<i<y,a_x<a_i<a_y$ 的 $r_i$ 进行翻转,$x,y$ 处的值可以暴力重新计算,这个形式可以块内用线段树维护做到 $O(n\sqrt n\log n)$,亦可以直接用 bitset 维护二维偏序做到 $O(n^2/w+n\sqrt n)$,根号来自维护表示值 $[1,i]$ 所在位置的 bitset。

一个重要的观察是,本题在询问时我们只关心一个块内是否存在 $1$,于是我们可以只维护 $r_i$ 的差分数组,这并不影响 $1$ 的存在性。考虑将 $r_i$ 按照 $a_i$ 从小到大的顺序排序,这样每次整块的修改就变成了区间翻转,转差分后即为单点修改,这就是容易维护的了。这里需要使用 std::lower_bound,会多一个 $\log$,但是 std::lower_bound 常数很小,没必要将其替换掉。总复杂度视为 $O(n\sqrt n)$。

术数树

定义 $k$ 进制异或为 $k$ 进制不进位加法。

给一张无向图,边有边权。一条路径的权值为路径上所有边的边权的 $k$ 进制异或和。求 $u\rightsquigarrow v$ 的路径的最小权值(一条边可以经过任意多次)。


$k=2$ 时这个问题是经典的,取任意 dfs 树然后将所有返祖边构成的环的权值丢到线性基里即可。

$k$ 为其他值时做法完全相同。我们可以对任意 $k\ge 2$ 构建 $k$ 进制下的异或线性基,具体方式查看 这篇博客

2024.5.24

棋盘

有一个 $n\times m$ 的棋盘,初始时有一个棋子放在 $(1,1)$ 上。Alice 和 Bob 轮流操作,Alice 先手,每人每次可以将棋子移到同行或同列的某个格子上,也可以立刻终止游戏。每个格子被移到的次数需要严格小于 $10^9$。给两个长度分别为 $n,m$ 的序列 $a,b$,格子 $(x,y)$ 的权值为 $a_x+b_y$,Alice 希望最终棋子所在的格子的权值尽可能小,Bob 希望权值尽可能大。求最终棋子所在格子的权值。


Alice 希望权值尽可能小,Bob 希望权值尽可能大,在这样的目标下,我们可以首先二分答案 $mid$,此时 Alice 希望权值 $\le mid$,我们检查 Alice 是否能够获胜即可。这样做的好处是,所有格子被简单的分成了两类,一类 Alice 希望到达,另一类 Bob 希望到达。

感性理解,限制格子被移到的次数小于 $10^9$ 和限制每个格子只能经过一次是等价的,可以考虑如果必败方让棋子走了回头路,必胜方可以反着再走回来,最后必败方必须选择一个别的点前往。虽然这个证明一点道理都没有。

我们称权值 $\le mid$ 的点为白点,权值 $>mid$ 的点为黑点。

另外需要注意到本题中双方都可以在轮到自己操作时选择结束游戏,所以如果 $(1,1)$ 为白点,Alice 立刻获胜,此外 Alice 只能将棋子移至黑点,Bob 只能将棋子移至白点,否则对方都会立刻获胜。有效的移动只发生在异色点之间,这样就构建出了本题的二分图博弈模型。

二分图博弈的结论是,先手必胜当且仅当起点被包含在二分图的所有最大匹配中,证明并不困难。

于是就有了一个暴力的做法,建出 $O(n^2)$ 个点 $O(n^3)$ 条边的二分图然后跑最大匹配,判断起点是否一定被最大匹配包含可以直接将起点删掉再跑一遍,单次检查复杂度为 $O(n^4)$。

考虑直接在原来的网格图上做最大匹配,不过匹配这个形式并不方便描述,可以将其转化为最大独立集。一个点向同行同列的异色点连边,所以最大独立集相当于选取一些行和列,选取同时落在这些行和列内的白点,以及同时落在其余行和列内的黑点,最大化所选点的个数。

如果我们将 $a,b$ 从小到大排序,则白点和黑点的分界线是一个从右上到左下的阶梯形,左上方是白点,右下方是黑点。容易发现最优情况下我们总是选择所有行和所有列的一个前缀。于是我们枚举行的分界线,最优的列分界线随行分界线的下移而右移,做一个双指针即可。删掉起点对这个过程的影响不大,特殊处理起点即可。单次检查复杂度为 $O(n)$,总复杂度 $O(n\log V)$。

2024.5.25

树的镜像 / LG4672 [BalticOI 2011 Day2] Tree Mirroring

做法很多,关键在于定位到一个叶子或者一组对应点。

叶子总是二度点,但二度点未必是叶子。我们考虑广义串并联图方法,不断缩二度点。特判掉链和环的情况,不难发现,若图合法,则我们总是能缩出重边,那么一个叶子就是其中一条边对应的原图上路径的中点。更简便的方法是,若 $u,v$ 间缩出了重边,则 $u,v$ 一定是对应点。

据此我们就可以定位出所有的叶子。分别以 $u,v$ 为起点 bfs,一个点为叶子当且仅当其到 $u$ 的距离与到 $v$ 的距离相同。

我们可以用所有叶子将图分成两部分,用树哈希判断以 $u,v$ 为根的树是否同构即可。注意本题中叶子是需要相互区分的,解决方法是给每个叶子随机分配权值。

注意细节的处理。

2024.5.27

排序幻觉

给一个长度为 $n$ 的序列 $a$,支持单点修改,每次修改后查询最小的 $x$ 使得 $\forall i\in[1,n)\ a_i\oplus x\le a_{i + 1}\oplus x$。


小于等于这个限制实际上是非常强的,这个条件满足当且仅当两数相同,或在两数最高的不同的二进制位上,较小数为 $0$,较大数为 $1$。所以如果要求 $a_i\oplus x\le a_{i + 1}\oplus x$,我们找到 $a_i$ 和 $a_{i + 1}$ 最高的不同的二进制位,视两数在该位上的取值会限制 $x$ 在该位上必须取 $0$ 或 $1$。我们用桶维护所有相邻两数对每个二进制位的限制情况,单点修改时只会影响两对相邻数,暴力更新信息即可。总复杂度 $O((n+q)\log V)$。

给一张 $n$ 个点的无向图,求它的连通导出子图的个数。答案对 $2$​ 取模。

保证无向图中的每条边 $(u,v)$ 满足 $|u-v|\le 12$。


由于有 $|u-v|\le 12$ 我们考虑 dp,从小到大逐个加点,这样我们只需要维护有关最后 $12$ 个点的信息。但是这样仍然很难做,由于要求得到的导出子图连通,我们必须维护最后 $12$ 个点的连通性信息,这样可以得到一个 $O(\operatorname{Bell}(d)\operatorname{poly}(n))$ 的做法,其中 $d=12$。

我们需要利用答案对 $2$ 取模这一性质,使得合法的导出子图贡献为 $1$,不合法的导出子图贡献为 $0$。考虑一个导出子图合法当且仅当其恰好有一个连通块,若另一个导出子图的贡献为 $2^{c-1}$,其中 $c$ 为连通块个数,则对 $2$ 取模后就达到了我们想要的效果。

为了让式子更好看一点,我们将贡献改为 $2^c$,并让答案对 $4$ 取模,这样不合法的导出子图贡献仍为 $0$。考虑为 $2^c$ 赋予组合意义,这可以视作为所有点黑白染色,要求相同连通块内点同色的方案数。

这样就可以 dp 了。设 $f_{i,S,T}$ 表示前 $i$ 个点,最后 $12$ 个点中选了 $S$,其中黑点为 $T$,$T\subseteq S$。

复杂度 $O(n3^d)$。

分身术

从 $n$ 个区间中选出尽可能多的区间使得这些区间能被分成 $k$ 组,每组内的区间两两不交。

对每个 $1\le k\le m$ 求答案。


$k=1$ 时的贪心是经典的,将区间按 $r$ 排序,依次考虑每个区间能选则选即可。

事实上 $k$ 更大时也是类似的,可以说明,选出的区间合法当且仅当不存在某个位置被 $>k$ 个区间覆盖。证明考虑 Dilworth 定理,将能分成 $k$ 组这一「最小链覆盖」转换为「最长反链」即可。

这样容易做到 $O(nm\log n)$。瓶颈在于要对每个 $k$ 求答案。

另一个符合直觉的事实是若一个区间在 $k=k_0$ 时被选,则 $k=k_0+1$ 时它也会被选。

这样若我们已经有了 $k=k_0$ 时的答案,想要求 $k=k_0+1$ 的答案只需要再另外选出一组两两不交的区间即可。此时我们不能暴力将所有区间扫一遍,用线段树二分支持快速找到下一个可选的区间即可。总复杂度 $O((n+m)\log n)$。

Last Modified: May 28, 2024
Archives Tip
QR Code for this page
Tipping QR Code