首页 > 其他分享 >受不了了,浅谈维护括号序列最长全不匹配段的最长长度的两种方法

受不了了,浅谈维护括号序列最长全不匹配段的最长长度的两种方法

时间:2024-07-04 19:31:47浏览次数:22  
标签:rnxt lnxt 匹配段 浅谈 lpre 括号 pushup 维护 最长

首先我们亲爱的 zyr 同学在 2 道几乎一样的括号序列题上面用了 2 种不同的方式来维护 pushup,而这和每道题题解的趋势几乎一致。

但是我直接交的他的代码。

所以写一下 zyr 队爷的思路。

以下直接设 ( 为 \(1\),) 为 \(-1\)。

一、结论法

答案为右最大前缀和 - 左最小后缀和。(跨越区间)

根据这个,类似 https://www.becoder.com.cn/article/15845 那样维护即可。(真是碰巧,完全一样维护)

二、暴力法

每次 pushup 合并左右括号,并统计答案。

发现有些东西是需要保留原始的状态的(先不消除合法括号)。

由于你合并的时候是这样子的:

\(L_{lnxt} + |L_{rnxt}-R_{lpre}|+R_{rpre}\)

\(lnxt\) 表示后缀中的 ) 个数。

所以暴力拆绝对值,维护 \(lnxt+rnxt,lnxt-rnxt,lpre+rpre,rpre-lpre\) 即可。代码:

void pushup(int p) { 
	if(T[p << 1].lsum > T[p << 1 | 1].rsum) T[p].rsum = T[p << 1].rsum, T[p].lsum = T[p << 1].lsum + T[p << 1 | 1].lsum - T[p << 1 | 1].rsum;
	else T[p].lsum = T[p << 1 | 1].lsum, T[p].rsum = T[p << 1].rsum + T[p << 1 | 1].rsum - T[p << 1].lsum;
	
	T[p].pre1 = max({T[p << 1].pre1, T[p << 1].rsum + T[p << 1].lsum + T[p << 1 | 1].pre2, // 多一点 (( 
		T[p << 1 | 1].pre1 + T[p << 1].rsum - T[p << 1].lsum}); // 多一点 )))) 
	// 表示的是 ))(((
	T[p].pre2 = max({T[p << 1].pre2, T[p << 1 | 1].pre2 + T[p << 1].lsum - T[p << 1].rsum});
	// 表示 (((((( 且前面 )) 被减去 
	
	T[p].nxt1 = max({T[p << 1 | 1].nxt1, T[p << 1].nxt1 + T[p << 1 | 1].lsum - T[p << 1 | 1].rsum, 
		T[p << 1].nxt2 + T[p << 1 | 1].lsum + T[p << 1 | 1].rsum});
	T[p].nxt2 = max({T[p << 1 | 1].nxt2, T[p << 1].nxt2 + T[p << 1 | 1].rsum - T[p << 1 | 1].lsum});
	
	T[p].maxn = max({T[p << 1].maxn, T[p << 1 | 1].maxn, T[p << 1 | 1].pre1 + T[p << 1].nxt2,
	T[p << 1 | 1].pre2 + T[p << 1].nxt1});
}

// 维护 pre(R + L) pre(L - R)
// nxt(R + L) nxt(R - L)
// 参考:)( 是 RL  的 

好像式子的 \(l,r\) 写反了。

标签:rnxt,lnxt,匹配段,浅谈,lpre,括号,pushup,维护,最长
From: https://www.cnblogs.com/LCat90/p/18284512

相关文章

  • 浅谈前置处理器之取样器超时
    浅谈前置处理器之取样器超时取样器取样器超时设置决定了JMeter等待取样器完成并接收响应的最大时间长度。如果在这个时间内未收到响应,取样器将标记该请求为超时错误。参数说明●在取样器超时的配置界面找到“Sampletimeout(inmilliseconds)进行设置。●超时值以毫秒......
  • 浅谈前置处理器之用户参数
    浅谈前置处理器之用户参数“用户参数”前置处理器是一个非常实用的功能,它可以在每个请求执行前动态地为HTTP请求等添加或替换变量值。本文档将详细介绍“用户参数”前置处理器的使用方法、特点以及与用户定义变量的区别。用户参数前置处理器简介用户参数前置处理器允许你......
  • 浅谈逻辑控制器之模块控制器
    浅谈逻辑控制器之模块控制器模块控制器(ModuleController)是一种高级逻辑控制器,它提供了一个强大的机制来复用和组织测试计划中的组件。本文档将深入介绍模块控制器的功能、配置方法及其应用场景。功能概述模块控制器允许用户在测试计划中引用另一个测试片段(通常是一个简......
  • 万字长文浅谈系统稳定性建设
    1.背景京东的期中考试:618即将到来,各个团队都在进行期中考试前的模拟考试:军演压测,故障演练,系统的梳理以检测系统的稳定性以应对高可用,高性能,高并发。我们知道系统的稳定性建设是贯穿整个研发流程:需求阶段,研发阶段,测试阶段,上线阶段,运维阶段;整个流程中的所有参与人员:产品,研发,测试,......
  • 「动态规划」如何求最长递增子序列的长度?
    300.最长递增子序列https://leetcode.cn/problems/longest-increasing-subsequence/description/给你一个整数数组nums,找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7]是数组[0,3,1,6,2,2,7]......
  • 【算法探秘】无重复字符的最长子串:解锁字符串中的独特风景
    【算法探秘】无重复字符的最长子串:解锁字符串中的独特风景一、引言:在字符的海洋中航行二、技术概述:独步字符森林技术定义核心特性代码示例:初尝甜蜜果实三、技术细节:拨开迷雾,洞悉本质原理解析难点剖析四、实战应用:字节跳跃,解密信息应用场景案例展示五、优化与改进:精益......
  • 浅谈 K8s Service 网络机制
    浅谈K8sService网络机制云原生运维圈 2024-07-0112:03 上海 1人听过 以下文章来源于腾讯云原生 ,作者王成腾讯云原生.云原生技术交流阵地,汇聚云原生最新技术资讯、文章、活动,以及云原生产品及用户最佳实践内容。王成,腾讯云研发工程师,Kubernetesmember,从......
  • 代码随想录算法训练营第50天 | 1143.最长公共子序列 、1035.不相交的线 、53. 最大子
    这几题都挺类似,都是求最长公共子序列,有些题目稍微变了下1143.最长公共子序列体会一下本题和718.最长重复子数组的区别视频讲解:https://www.bilibili.com/video/BV1ye4y1L7CQhttps://programmercarl.com/1143.最长公共子序列.html/***@param{string}text1*@param{......
  • 代码随想录算法训练营第49天 | 300.最长递增子序列 、674. 最长连续递增序列 、718.
    300.最长递增子序列今天开始正式子序列系列,本题是比较简单的,感受感受一下子序列题目的思路。视频讲解:https://www.bilibili.com/video/BV1ng411J7xPhttps://programmercarl.com/0300.最长上升子序列.html/***@param{number[]}nums*@return{number}*/varlengthOfL......
  • 浅谈 Selenium 控制浏览器操作
    控制浏览器操作:(1)最大化、最小化浏览器:driver.maximize_window()(2)控制、获取浏览器大小:driver.get_window_size()(3)获取当前标签页title、url:print("标签页title:{}".format(driver.title))print("标签页url:{}".format(driver.current_url))(4)前进、后退、刷新:#前进driver......