首页 星云 工具 资源 星选 资讯 热门工具
:

PDF转图片 完全免费 小红书视频下载 无水印 抖音视频下载 无水印 数字星空

关于求合法括号子序列个数

编程知识
2024年09月08日 15:37

求合法括号子序列个数

题意

背景

合法括号串的定义如下:

  1. () 是合法括号串。
  2. 如果 A 是合法括号串,则 (A) 是合法括号串。
  3. 如果 AB 是合法括号串,则 AB 是合法括号串。

子串不同的子串的定义如下:

  1. 字符串 S 的子串是 S连续的任意个字符组成的字符串。S 的子串可用起始位置 \(l\) 与终止位置 \(r\) 来表示,记为 \(S (l, r)\)\(1 \leq l \leq r \leq |S |\)\(|S |\) 表示 S 的长度)。
  2. S 的两个子串视作不同当且仅当它们在 S 中的位置不同,即 \(l\) 不同或 \(r\) 不同。

题目

给出一个括号串 \(s\)(其不一定是合法括号串),问 \(s\) 中有多少个互不相同的子串合法括号串

样例

样例输入

(()()

样例输出

2

分析

观察序列1:

()()()

\(pos = 2\) 的时候,对答案的贡献值为 \(1\)

\(pos = 4\) 的时候,本身 \([3, 4]\) 就有一个满足要求的括号序列,再合并上前面的成为 \([1, 4]\) ,于是对答案的贡献值就为 \(2\) ,再加上前面 \([1, 2]\) 本身有的括号序列,总共为 \(3\)

\(pos = 6\) 时,总共的贡献值为 \(3\) ,加上前面的有 \(3 + 3 = 6\) 种。其他位置均没有贡献(左括号没有贡献值)。

总之,\(pos\)\(1 \sim 6\) 时对答案的贡献分别为 \(0, 1, 0, 2, 0, 3\) ,合并后的总答案为 \(0, 1, 1, 3, 3, 6\)


观察序列2:

())()

\(pos = 2\) 时,对答案贡献为 \(1\)

\(pos = 3\) 时,由于不满足成匹配的括号序列,所以没有贡献(我们只看右括号的贡献值)。

\(pos = 5\) 时,由于 \(pos = 3\) 时多了一个后括号,所以 \([1, 3]\) 不匹配,导致 \([1, 5]\) 成不了一个匹配的括号序列,所以对答案的贡献仍为 \(1\)

\(pos\)\(1 \sim 5\) 时对答案的贡献分别为 \(0, 1, 0, 0, 1\) ,合并后的总答案为 \(0, 1, 1, 1, 2\)


观察序列3:

()(())

\(pos = 2\) 时,贡献为 \(1\)

\(pos = 5\) 时,由于 \(pos = 3\) 是在中间断开,所以 \([1, 5]\) 不能匹配,所以贡献仍为 \(1\)

\(pos = 6\) 时,我们发现 \([1, 2]\) 是匹配的。故 \([1, 2], [3, 6]\) 能合成一个匹配的序列,所以对答案贡献为 \(2\)

\(pos\)\(1 \sim 6\) 时对答案的贡献分别为 \(0, 1, 0, 0, 1, 2\) ,合并后的总答案为 \(0, 1, 1, 1, 2, 4\)


可以发现,一个后括号如果能匹配一个前括号,假设这个前括号的前1位同样有一个已经匹配了的后括号,那么我们就可以把当前的匹配括号序列和之前的匹配括号序列合并。当前的这个后括号的贡献值,其实就等于前面那个后括号的贡献值 + 1。

Elaina's Code

int sum=0,tot[N];
string s;
stack<int> sta;
signed main(){
	cin>>s;
	for(int i=0;i<s.size();i++){
		if(s[i]=='(') sta.push(i);
		if(s[i]==')'){
			if(!sta.empty()){
				int l=sta.top();
				sta.pop();
				tot[i]=tot[l-1]+1;
			}
		}
		sum+=tot[i];
	}
	cout<<sum;
	return Elaina;
}
From:https://www.cnblogs.com/Elaina-0/p/18403043
本文地址: http://www.shuzixingkong.net/article/1831
0评论
提交 加载更多评论
其他文章 万字长文带你窥探Spring中所有的扩展点
写在前面 Spring的核心思想就是容器,当容器refresh的时候,外部看上去风平浪静,其实内部则是一片惊涛骇浪,汪洋一片。Springboot更是封装了Spring,遵循约定大于配置,加上自动装配的机制。很多时候我们只要引用了一个依赖,几乎是零配置就能完成一个功能的装配。 由spring提供的、
万字长文带你窥探Spring中所有的扩展点 万字长文带你窥探Spring中所有的扩展点
Git Extensions:一个.NET开源的 Git 图形用户界面(GUI)工具
前言 今天大姚给大家分享一个.NET开源、免费的用于管理 Git 存储库的独立图形用户界面(GUI)工具,它还与 Windows 资源管理器和 Microsoft Visual Studio (2015/2017/2019/2022) 集成:Git Extensions。 Git新手指南:从基础到实
Git Extensions:一个.NET开源的 Git 图形用户界面(GUI)工具 Git Extensions:一个.NET开源的 Git 图形用户界面(GUI)工具 Git Extensions:一个.NET开源的 Git 图形用户界面(GUI)工具
红日靶机(一) 笔记
红日靶机(一)笔记 概述 域渗透靶机,可以练习对域渗透的一些知识,主要还是要熟悉 powershell 语法,powershell 往往比 cmd 的命令行更加强大,而很多渗透开源的脚本都是 powershell 的。例如 NiShang,PowerView 等等。这是域渗透的初学靶机。其中也遇到了
红日靶机(一) 笔记 红日靶机(一) 笔记 红日靶机(一) 笔记
八,SpringBoot Web 开发访问静态资源(附+详细源码剖析)
八,SpringBoot Web 开发访问静态资源(附+详细源码剖析) @目录八,SpringBoot Web 开发访问静态资源(附+详细源码剖析)1. 基本介绍2. 快速入门2.1 准备工作3. 改变静态资源访问前缀,定义为我们自己想要的4. 改变Spring Boot当中的默认的静态资源路径(实
八,SpringBoot Web 开发访问静态资源(附+详细源码剖析) 八,SpringBoot Web 开发访问静态资源(附+详细源码剖析) 八,SpringBoot Web 开发访问静态资源(附+详细源码剖析)
红黑树
概述 红黑树(Red-Black Tree,R-BTree)是一种自平衡的二叉查找树,在红黑树的每个节点都多出一个存储位表示节点的颜色,颜色只能是红(Red)或者黑(Black)。 红黑树的特性如下: 每个节点或者是黑色的,或者是红色的 根节点是黑色的 每个叶子节点都是黑色的,这里的叶子节点指的是最
红黑树 红黑树 红黑树
实现人形角色的攀爬
在Unity实现角色攀爬 前言 开放世界类型的游戏近年也热门起来了,自由攀爬也成了这一类游戏的一大特色。攀爬给了玩家更多探索路径的选择,也让地图设计有了更多思路。这次,我们就来尝试在Unity中制作一个人形角色的攀爬。 注:攀爬是一个角色完整动作系统的一部分,本文暂且抛开其它动作,也不涉及动画,仅针
实现人形角色的攀爬 实现人形角色的攀爬 实现人形角色的攀爬
Pipeline流水线通过git拉取Jenkinsfile报错 error: RPC failed; result=22, HTTP code = 404
Pipeline流水线通过git拉取Jenkinsfile报错 error: RPC failed; result=22, HTTP code = 404 在学习共享库时使用通过git拉取jenkinsfile时,报错在排查gitlab服务状态,网络通讯,防火墙规则以及Jenkins凭据均可以正常使
Pipeline流水线通过git拉取Jenkinsfile报错 error: RPC failed; result=22, HTTP code = 404 Pipeline流水线通过git拉取Jenkinsfile报错 error: RPC failed; result=22, HTTP code = 404 Pipeline流水线通过git拉取Jenkinsfile报错 error: RPC failed; result=22, HTTP code = 404
题解:AT_arc116_b [ARC116B] Products of Min-Max
在题库里面乱翻,就翻到了。 因为在这道题里面子序列不需要考虑元素顺序,所以原序列无论是什么顺序都不会影响答案。 所以先把元素按照从大到小的顺序排列,然后考虑每个元素的贡献。 在当前序列中,对于元素 \(a_i\),不妨设其为最小值,并去寻找它能作为哪些序列的最小值。容易发现它作为最小值的时候只能和