2022/09
2022/9/16 23:19:46
本文主要是介绍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
- 子树内选一个数与 \(z\) 异或最大 2. 路径选个数 \(z\) 异或最大。
这篇关于2022/09的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-01为什么公共事业机构会偏爱 TiDB :TiDB 数据库在某省妇幼健康管理系统的应用
- 2024-04-26敏捷开发:想要快速交付就必须舍弃产品质量?
- 2024-04-26静态代码分析的这些好处,我竟然都不知道?
- 2024-04-26你在测试金字塔的哪一层?(下)
- 2024-04-26快刀斩乱麻,DevOps让代码评审也自动起来
- 2024-04-262024年最好用的10款ER图神器!
- 2024-04-2203-为啥大模型LLM还没能完全替代你?
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署