Java教程

2022/09

本文主要是介绍2022/09,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

摆烂记录

P5283

选出 \(k\) 个不重复子区间,使得区间异或之和最大。

典中典,首先前缀异或和,转化为 \(p_r \ xor \ p_{l-1}\) 最大。

首先初始时对于每个 \(r\),求出 \(k\),使得 \(p_r \ xor \ p_k\) 最大(\(0\le k<r\))。

做法是 trie 树,每次插入权值在叶子节点记录 \(l\)(任意一个)。

用堆维护初始数组一开始的 \((v,l=1,r,k,ori)\),其中 \(v\) 表示 \(l=1\) 为左端点,\(ori = r\) 为右端点最大的疑惑和。\(ori\) 这个在后面回用到。

然后取出一个堆顶,\((v,l,r,k,ori)\)。表示开始时在 \([1,ori]\) 取出 \(l\),使得 \(p_{ori} \ xor \ p_{l-1}\) 最大。这个必然在答案中。

这里需要用到可持久化 trie。维护过程只是把(任意一个)改成最大的编号。这样查询 \([l,r]\) 的时候,如果存在 \(k\) 和他异或最大, 则最大的 \(k\),一定满足 \(k\in [l,r]\)。

然后我们需要分裂这个区间。即,在 \([l,k-1]\) 找到 \(k'\) 使得 \(v' = p_{ori} \ xor \ p_{k'}\) 最大,插入 \((v',l,k-1,k',ori)\)。 右边同理。

弹出题目中 \(k\) 个的时候,即可结束,正确性显然。时间复杂度两个 log。

哈哈

P4592

  1. 子树内选一个数与 \(z\) 异或最大 2. 路径选个数 \(z\) 异或最大。
这篇关于2022/09的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!