首页 > 其他分享 >启发式合并

启发式合并

时间:2024-02-01 09:44:30浏览次数:34  
标签:结点 val 路径 合并 异或 LCA 启发式 dp

例题:CF600E

有一种暴力的想法是先 DFS 每个结点,再对每个结点 DFS 它的子树,用 \(cnt\) 数组记录每个结点子树的颜色出现情况。复杂度 \(O(n^2)\)。

一个平平无奇的优化:第一层 DFS 的时候,把重儿子放到最后搜索。在搜索重儿子的子树后,不清空 \(cnt\) 数组。然后在 DFS 这个结点的子树的时候,重儿子的颜色出现情况直接把重儿子的 \(cnt\) 数组拿来用,在这基础上 DFS 轻儿子的子树。

这个优化可以把算法变成 \(O(n\log n)\)!


类比并查集的按秩合并优化。每次都是小的向大的连,复杂度是小集合的规模。这样每个小集合要做贡献,规模都至少翻倍,所以复杂度 \(O(n\log n)\)。

这一题,每一个结点想要贡献复杂度,必须出现在某个轻儿子的子树内。而每个轻儿子的父结点的规模,至少是轻儿子规模的两倍。所以一个结点贡献的次数不会超过 \(O(\log n)\)。

CF1825E

可参考

\(dp_{u,w}\) 表示把 \(u\) 的子树的叶子到根的异或值全部变成 \(w\) 的最小操作次数。

观察到一个性质:\(dp_{u,?}\) 只有两种取值。

证明:若 \(dp_{u,w1}-dp_{u,w2}>1\),用一次操作令 \(u\) 的权值变为 \(w1\bigoplus w2\),再采用 \(dp_{u,w2}\) 的方法。此时构造出一种方法使得所有叶子到根的异或值是 \(w1\) 且只需要 \(dp_{u,w2}+1\) 步,矛盾。

令 \(S_u\) 表示令 \(dp_{u,?}\) 取到最小值时,\(w\) 的集合。

发现 \(S_u\) 就是 \(S_{v1\sim vk}\) 中出现次数最多的数的集合。

如果对每一个结点,都循环它的子结点,再循环它的子结点的 \(s\),暴力找出现次数最多的数,显然会超时。

但是要启发式合并,好像也不太好搞啊?我们可以启发式和暴力,交叉着用。

  1. 如果 \(S_{v1\sim vk}\) 每个数只出现一次,用启发式合并。令 \(v_{heavy}\) 为重儿子,先令 \(S_u=S_{v_{heavy}}\),然后再让 \(S_u\) 和其他的 \(S_{vi}\) 合并。

  2. 如果出现次数最多的数,至少出现两次。可以暴力用 \(map\) 统计出出现次数最多的数。因为至少出现两次,所以 \(|S_u|\) 至多是 \(\dfrac{1}{2}\times \sum |S_{vi}|\)。

还有遗留两个问题:

  1. 如何判断是否每个数只出现一次?

    我们可以先啥都不管,就先执行启发式合并的流程。等到 \(S_{vi}\) 中发现一个数在当前 \(S_u\) 中已经有了,才进入第二种情况。

    这样做复杂度不会爆,因为至多也就是让复杂度加上 \(O(n\log n)\)。

  2. 如何快速让 \(S_u\) 中的数异或上父结点的权值?

    我们可以设置一个偏移量,\(S_u\) 中的数不是真实的让 \(dp_{u,?}\) 最小的数,异或上偏移量才是。

XOR Tree

点权的异或路径,先来一个经典 trick:求出每个点到根的异或是多少,记为 \(b_u\)。两点路径的异或就是 \(b_u\bigoplus b_v\bigoplus a_{lca}\)。

注意到可以改成任意整数。所以第 \(i\) 次操作直接把操作的结点改成 \(2^{32+i}\),这样所有经过这个结点的异或值就都不是 \(0\) 了。

把一条异或为 \(0\) 的路径称为坏路径。考虑所有坏路径的 LCA。我们在这些 LCA 中取深度最深的,肯定会最优。

证明:记这个 LCA 为 \(u\)。\(u\) 是一条坏路径的 LCA。而这条坏路径要被销毁,显然必须在这条坏路径上选一个点改了。而选其他的点 \(v\) 一定不如选 \(u\)。因为 \(u\) 是最深的 LCA,如果其他路径经过 \(v\),则一定经过 \(u\):否则 \(v\) 才是最深的 LCA。

所以现在的任务就是快速求出最深的坏路径 LCA。但是如果每次求出所有 LCA,实在是太慢了。

可以转换一下思路:不去找所有 LCA,而是从深到浅枚举结点,判断一下这个点是否是坏路径的 LCA!

具体而言,对每个结点维护一个 set:\(val[x]\) 包含 \(x\) 的子树中有可能作为坏路径一段的点。为了方便,我们不记录点,而是记录这些点的 \(b_{()}\)。

当我们 DFS 到一个结点 \(u\) 时,循环它所有的子结点 \(v\),先递归 DFS \(v\)。

这个时候我们已经得到了所有 \(val[v]\)。然后看 \(val[u]\) 和 \(val[v]\) 中有没有两个元素可以异或得到 \(0\)。(注意不是直接异或得到 \(0\),而是异或起来再异或 \(a[u]\) 是否得到 \(0\))

如果不存在,令 \(val[u]\) 为所有 \(val[v]\) 的并;否则,我们肯定就要修改 \(u\),然后使所有通过 \(u\) 的坏路径都变成不为 \(0\) 的,于是 \(val[u]\) 就直接当一个空集合就行了。

直接这么做肯定 TLE,但是我们可以做一个优化:在算 \(val[v]\) 的并的时候,每次都是从 \(val[u],val[v]\) 中选规模较小的向规模较大的合并。

这样一个 \(b[x]\) 想要在合并时贡献复杂度,说明它一定是在某次在规模较小的集合中。

标签:结点,val,路径,合并,异或,LCA,启发式,dp
From: https://www.cnblogs.com/FLY-lai/p/18000568

相关文章

  • 空值合并运算符 '??' 与 || 比较
    空值合并运算符'??'与||比较https://zh.javascript.info/nullish-coalescing-operator或运算符||可以以与??运算符相同的方式使用。`letfirstName=null;letlastName=null;letnickName="Supercoder";//显示第一个真值:alert(firstName||lastName||nic......
  • SQL Server MERGE(合并)语句
    来源 https://www.cnblogs.com/yigegaozhongsheng/p/11941734.html如何使用SQLServerMERGE语句基于与另一个表匹配的值来更新表中的数据。  SQLServer MERGE语句 假设有两个表,分别称为源表和目标表,并且需要根据与源表匹配的值来更新目标表。有以下三种情况: 源表......
  • 代码随想录 day36 无重叠区间 划分字母区间 合并区间
    无重叠区间这里的思路是找到有几个非重叠区间然后总数减去非重叠区间就是剩下的重叠区间数首先排好序按左或者右都可以这里按左排好然后发现边界不重叠就++边界重叠那么由于左边界优先对齐了所以右边界更新作为一个新的整体区间和下一个区间比较划分字母区间......
  • [office] excel表格sheet如何合并
    在进行excel操作的时候,我们经常遇到多个sheet表合并的问题,这些表的字段是一致的,为了能够更好的分析和处理,需要把这些表合并成一个。下面让小编为你带来excel表格合并sheet的方法。excel表格sheet合并步骤如下:表一:需要汇总的各表表二:汇总地段列表如图所示,需要将......
  • Power BI - 5分钟学习创建合并列
    每天5分钟,今天介绍PowerBI如何创建合并列什么是合并列顾名思义合并列就是把两个列信息拼接到一个列中显示。工作中经常会有类似需求,把产品编码和产品名称放到一个筛选器或者单元格中展示。那我们在PowerBI中应该如何进行类似创建合并列的操作呢?首先导入样例产品表;(Excel数据......
  • Hive参数调优:如何控制reduce个数与参数调优(合并小文件和拆分大文件)
    reduce的个数一般最后决定了输出文件的个数,如果想多输出文件的个数(这样文件变小,但有可能程序变慢),那么可以人为增加reduce个数。如果想减少文件个数,也可以手动较少reduce个数(同样可能程序变慢)。但实际开发中,reduce的个数一般通过程序自动推定,而不人为干涉,因为人为控制的话,如果使用......
  • notepad 将多行转换成字符串,合并成一行
    notepad将多行转换成字符串,合并成一行(1)快捷键ctrl+H,选择【替换】,(2)【查找目标】,输入\r\n,这个正则表达式的含义是换行回到行首,相当于windows的enter键:\r(即CR,CarriageReturn)表示回车,使光标到行首;\n(即LF,Linefeed)表示换行。(3)下面的【替换为】输入分隔......
  • 使用mergekit 合并大型语言模型
    模型合并是近年来兴起的一种新技术。它允许将多个模型合并成一个模型。这样做不仅可以保持质量,还可以获得额外的好处。假设我们有几个模型:一个擅长解决数学问题,另一个擅长编写代码。在两种模型之间切换是一个很麻烦的问题,但是我们可以将它们组合起来,利用两者的优点。而且这种组......
  • OB的内存&转储&合并
    OB的内存&转储&合并 转:https://www.cnblogs.com/z-uncle/p/17916448.html内存OBserver内存:物理总内存=OBserver内存+OS剩余内存。OBserver的内存分为两部分,一部分是system内存,一部分是租户内存。通过参数设定observer占用的内存上限:memory_limit_percentage=80--->80%......
  • 线段树合并
    线段树合并线段树合并可以使很多跑不过的暴力,特别是树上暴力的时间复杂度正确,与树分治的区别在于,线段树合并必须依次处理节点,但优势在于,保持了树的形态。算法思路引入CF600ELomsatgelral使用一个数组记录该子树内的颜色出现次数。每次每个节点暴力将儿子的信息合并到自己......