洛谷4839 - P哥的桶

每个点维护线性基,线段树的两个子节点合并的时候直接把一个点的暴力插入到隔壁即可。

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)$ 。需要注意的是需要动态开的节点个数可能会很多,一定要开够。

Your browser is out-of-date!

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

×