首页 > 其他分享 >P9746 「KDOI-06-S」合并序列

P9746 「KDOI-06-S」合并序列

时间:2024-03-23 20:45:13浏览次数:34  
标签:le 06 int sum KDOI 枚举 P9746 区间 id

P9746 「KDOI-06-S」合并序列

经典区间dp+预处理

不难设计状态 \(f_{l,r}\) 表示 \([l,r]\) 能否变为一个数,转移也简单,枚举三个区间,满足 \(f_{i,a}=f_{b,c}=f_{d,r}=1\) 且异或和为 \(0\)。复杂度为 \(O(n^6)\)。

设异或和为 \(s_{l,r}\)。

考虑优化,瓶颈在于转移需要枚举三个区间。假如只枚举一个右区间 \([d,r]\),那么我们只需要判断 \([l,d-1]\) 中是否存在两个区间能缩成一个数且两区间异或和为 \(s_{d,r}\) 就可以转移。

直接设 \(h_{i,j}\) 表示满足 \(i\le a\le b\le c\) 且 \(s_{i,a}\oplus s_{b,c}=j\) 的最小 \(c\) 值。但发现还是不好预处理出来,不好找到 \([b,c]\) 区间。再设 \(g_{i,j}\) 表示满足 \(i\le a\le b\) 且 \(s_{a,b}=j\) 且 \(f_{a,b}=1\) 的最小 \(c\) 值,\(g\) 容易转移,而 \(h\) 只需要枚举 \(a\) 即可,\(h_{i,s_{i,a}\oplus j}=\min g_{a+1,j}\ (f_{i,a}=1)\)。

\(f\) 转移变为存在 \(l\le d\le r\),满足 \(h_{i,s_{d,r}}<d\) 。单次复杂度为 \(O(n^2A)\),注意当前 \(f_{l,r}\) 为 \(1\) 后可以直接 break。

\(h\) 数组和 \(g\) 数组的转移在区间 dp 时更新即可。值得注意的是,在这题中,区间 dp 的顺序只能是左端点 \(l\) 从右向左枚举,右端点 \(r\) 从 \(l\) 向 \(n\) 枚举,因为 \(h\) 数组和 \(g\) 数组的更新需要之前所有长度的 \(f_{l,r}\),如果只按长度更新会出现错误,如枚举 \(l=a=1\) 时,若按长度枚举,无法转移到 \(g_{a+1,j}\) 长度大于 \(1\) 时的区间。

对于输出方案,除了记录每个区间的前继,还需要记录 \(h\) 和 \(g\) 数组转移时的其中一个合法方案,对于编号的改变,这个体现在 dfs 中。这个输出方案还是比较重要的。

void print(int l, int r, int id) {
	if(l == r || l == 0) return;
	int d = pre[l][r], a = hl[l][sum[r] ^ sum[d - 1]];
	int now = sum[a] ^ sum[l - 1] ^ sum[r] ^ sum[d - 1];
	int b = gl[a + 1][now], c = g[a + 1][now];
	print(d, r, id + (d - l)), print(b, c, id + (b - l)), print(l, a, id);
	ans.push_back({id, id + (b - l) - (a - l), id + (d - l) - (a - l) - (c - b)});
}

对于 \(h\) 和 \(g\) 出现的动机还是挺明确的,一个是优化需要,一个注意到 \(a_i\) 的大小,就知道可以把它放进状态里了。转移需要注意。

标签:le,06,int,sum,KDOI,枚举,P9746,区间,id
From: https://www.cnblogs.com/FireRaku/p/18091652

相关文章

  • 03天【代码随想录算法训练营34期】第二章 链表part01(203.移除链表元素 、707.设计链表
    203.移除链表元素竟然可以做个假head,学到了classListNode(object):def__init__(self,val=0,next=None):self.val=valself.next=nextclassSolution(object):defremoveElements(self,head,val):dummy_head=ListNode(-1)......
  • PAT乙级 1062 最简分数 C语言
    最简分数一个分数一般写成两个整数相除的形式:N/M,其中M不为0。最简分数是指分子和分母没有公约数的分数表示形式。现给定两个不相等的正分数N1​/M1​和N2​/M2​,要求你按从小到大的顺序列出它们之间分母为K的最简分数。输入格式:输入在一行中按N/M的格式给出两个......
  • R语言--06文件读写read.table()、read.csv()
    1、读取-read.table()#文件读写部分#1.读取ex1.txtex1<-read.table("ex1.txt")ex3<-read.table("ex1.txt",header=T)看看有没有header的区别,以下是第一行代码的运行结果: 以下是第二行代码运行的结果:所以header=T的作用就是原本的文件已经给出了列名,不用重新再......
  • 关于RK1808/RK1806和RV1109/RV1126 NPU升级方法
    一、注意事项本工程主要为RockchipNPU提供驱动、示例等。**RK3399Pro用户态的库及驱动不在本工程**,请参考:https://github.com/airockchip/RK3399Pro_npuRK3566/RK3568/RK3588/RV1103/RV1106请参考:https://github.com/rockchip-linux/rknpu2二、RKNNToolkit在使用RKNNA......
  • 高速CAN 收发器AMIS30660CANH2RG 用于各种数据传输协议的调制解调器和收发器
    AMIS30660CANH2RGCAN收发器是控制器区域网络(CAN)协议控制器和物理总线之间的接口,可在12V和24V系统中使用。该收发器为总线提供差分发射功能,向CAN控制器提供差分接收功能。由于接收器输入较宽的共模电压范围和其他设计功能,能够达到出色的电磁灵敏度(EMS)。与之相......
  • 图论06-飞地的数量(Java)
    6.飞地的数量题目描述给你一个大小为mxn的二进制矩阵grid,其中0表示一个海洋单元格、1表示一个陆地单元格。一次移动是指从一个陆地单元格走到另一个相邻(上、下、左、右)的陆地单元格或跨过grid的边界。返回网格中无法在任意次数的移动中离开网格边界的陆......
  • Pytorch | Tutorial-06 优化模型参数
    这是对Pytorch官网的Tutorial教程的中文翻译。现在我们有了模型和数据,是时候通过优化模型参数来训练、验证和测试我们的模型了。训练模型是一个迭代过程,在每次迭代中,模型都会对输出进行预测,计算其预测的误差(损失),保存误差相对于其参数的导数,并使用梯度下降优化这些参数。有......
  • 06 - Debian如何启用root用户的声音
    作者:网络傅老师特别提示:未经作者允许,不得转载任何内容。违者必究!Debian如何启用root用户的声音《傅老师Debian小知识库系列之06》——原创==前言==傅老师Debian小知识库特点:1、最小化拆解Debian实用技能;2、所有操作在VM虚拟机实测完成;3、致力于最终形成Debian小知识......
  • S2-066漏洞分析与复现(CVE-2023-50164)
    Foreword自struts2官方纰漏S2-066漏洞已经有一段时间,期间断断续续地写,直到最近才完成。羞愧地回顾一下官方通告:2023.12.9发布,编号CVE-2023-50164,主要影响版本是2.5.0-2.5.32以及6.0.0-6.3.0,描述中提到了文件上传漏洞和目录穿越漏洞。开始以为这是个组合漏洞,其实不是,这是一个......
  • 060_深度学习
    目录神经网络深度学习各层负责内容神经网络深度学习各层负责内容......