20181211 - NOI模拟赛

T1、T3 的思路基本都成型但是由于自己傻逼最后一个都没调出来。

LCM

考虑一个数最多被分解为一个大于 $\sqrt {\max a_i}$ 的质数和一些小于 $\sqrt {\max a_i} $ 的质数的乘积。考虑小于的部分,最多有 4320 种状态,我们可以用一种简单背包的方法统计出每一种值的个数。对于大于的部分,相当于我们给上一步统计的个数的时候给个数加上一个权值。通过一些简单的处理避免超过 $\sqrt { \max a_i }$ 的质数被重复计算。理论复杂度 $O(n \times 4320 \times (\log n + \log 4320))$ 。

Xor

不知道为什么出题人要把题意搞的这么迷。我们直接把边权异或到两个端点上,计算割的价值就是一边的点的权值的异或和。考虑贪心,把点按照权值从大到小排序,利用线性基维护会不会产生 $0$ ,不会就加上价值,否则减掉即可。

Lis

考虑把从左到右的最长上升子序列转变为从右到左的最长下降子序列,这样每次操作最多影响十棵树。树套树(树状数组套权值线段树)维护一个后缀高度大于指定值的 dp 值的最大值,每次暴力重算那十棵树即可。复杂度 $O(n \log^2 n \times 10)$ 。需要注意的是需要动态开的节点个数可能会很多,一定要开够。

这题洛谷的数据太…水,克鲁斯卡尔重构树不连通都可水过。

  • 3545: [ONTAK2010]Peaks
  • 3551: [ONTAK2010]Peaks加强版

在线算法:克鲁斯卡尔重构树套主席树。

在克鲁斯卡尔重构树上维护 DFS 序(或树链剖分)再套上主席树,维护第 $k$ 大。

当然非加强版由于你是重构树(被针对了)可能要大力卡常。比如加个 fread 以及离散化一下什么的。

BZOJ2588 - Count on a tree

询问树上路径第 $k$ 大:二分答案 + 树上查询。查询时用主席树差分:

$$tree[now] = tree[u] + tree[v] - tree[lca(u,v)] - tree[father(lca(u,v))]$$

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

主席树(洛谷P3834)

在 mwh 大佬的指引下,我最近学习了主席树。

思想

主席树是一种特殊的线段树,能够存储线段树的历史版本,我们称这种性质叫做可持久化。

主席树的可持久化通过这样来实现:我们每次修改单个节点,必然只会经过 $log_2n​$ 条“线段”,对于这些线段,我们都新开节点来存储。显然对于每一次修改操作,根节点都会被新建。那么我们只要存储下来每一次修改说对应的根节点即可。空间占用 $O(n log n)​$

具体思路可参考 https://www.luogu.org/blog/LonecharmRiver/zhu-xi-shu ss中的图片。

关于模板题

我们要维护静态区间第 k 小。可以先把数组离散化,比如:

1
2
3
离散化前 4 1 1 2 8 9 4 4 3
离散化后 4 1 1 2 5 6 4 4 3
离散数组 1 2 3 4 8 9

我们根据离散数组作为所维护的区间。第 i 棵树存储 [1, i] 内各数值出现的次数。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×