问题 2843 --括号序列

2843: 括号序列

"
时间限制 $1$ 秒/Second(s) 内存限制 $512$ 兆字节/Megabyte(s)
提交总数 $344$ 正确数量 $78$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 递归 动态规划
括号序列是指由“和)组成的序列,假如一个括号序列中,包含相同数量的左括
号和右括号,并且对于每一个右括号,在他的左侧都有左括号和他匹配,则这个
括号序列就是一个合法括号序列。比如(())()就是一个合法括号序列,但
(()) ( ()不是合法括号序列。
给出两个长度相同的合法括号序列A和B,那么A<B当且仅当:
●A和B 至少有一位不相同。
●在A和B从左往右数第一个不相同的位置i, A[i]=(, B[i]=)
比如A=(())(),B=()()(),则A<B,因为从左边数第一个不相同的
是第二个字符,A[2] = (,B[2] = ).对于长度N,由于定义了小于关系,
则可以通过这个关系推出所有长度为N的合法括号序列的大小关系,对于长度
为6的合法括号序列,从小到大排列顺序如下:
1. ((()))
2.(()())
3. (()) ()
4.()(())
5.()()()

给出N和M,求长度为N的合法括号序列中,
第M小的合法括号序列是?
6 1
((()))

推荐代码 查看2843 所有题解 上传题解视频得图灵币

本题记录 用 户(点击查看用户) 运行号(点击购买题解) 时 间
算法最快[$0 $ms] nnonj 614309 2020-10-05 09:59:24
内存最少[$0 $KB] zs 704055 2021-01-09 14:32:36
第一AC 王子涵 436929 2019-06-06 18:56:39
第一挑战 奥利给 431234 2019-05-20 23:32:02

赛题来源/所属竞赛 2019安徽省程序设计竞赛 N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛