IT届的菜鸟 2020-05-17 22:38 采纳率: 0%
浏览 741

安徽省赛ACM G题括号序列 怎么算的,除了代码还有详细解释

G:括号序列
时间:2 s

题目描述:

括号序列是指由 ‘(’ 和 ‘)’ 组成的序列,假如一个括号序列中,包含相同数量的左括号和右括号,并且对于每一个右括号,在他的左侧都有左括号和他匹配,则这个 括号序列就是一个合法括号序列,如(( ))( )就是一个合法括号序列,但(( ))(( )不是合法括号序列.
给出两个长度相同的合法括号序列 A 和 B , 那么 A < B 当且仅当:

A和B至少有一位不相同
在A和B从左往右数第一个不相同的位置i,A[i] = ( ,B[i]= ) ;
比如A = (( ))(), B = ( )( ) ( ), 则 A < B 。因为从左边数第一个不相同的是第二个字符,A[2] = ( , B[2] = )。对于长度 N,由于定义了小于关系,则可以通过这个关系推出所有长度为N的合法括号序列的大小关系,对于长度为6的合法括号序列,从小到大排列顺序如下:

((( )))

(()())

(( ))( )

( )(( ))

( )( )( )

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

输入
输入的第一行是 N 和 M
2 <= N <= 2000
1 <= M <= 10^18

输出
输出一个字符串,表示长度为 N 的平衡括号序列从小到大排列, 序号为 M 的字符串

  • 写回答

1条回答 默认 最新

  • 胖狗子修行之路 2020-05-18 09:54
    关注

    如果只需要答案,next_permutation()完美解决问题
    如果想弄懂,可以参考一下leetcode的下一个排序问题
    给自己打个广告https://blog.csdn.net/qq_42685012/article/details/105675932

    评论

报告相同问题?

悬赏问题

  • ¥15 数学的三元一次方程求解
  • ¥20 iqoo11 如何下载安装工程模式
  • ¥15 本题的答案是不是有问题
  • ¥15 关于#r语言#的问题:(svydesign)为什么在一个大的数据集中抽取了一个小数据集
  • ¥15 C++使用Gunplot
  • ¥15 这个电路是如何实现路灯控制器的,原理是什么,怎么求解灯亮起后熄灭的时间如图?
  • ¥15 matlab数字图像处理频率域滤波
  • ¥15 在abaqus做了二维正交切削模型,给刀具添加了超声振动条件后输出切削力为什么比普通切削增大这么多
  • ¥15 ELGamal和paillier计算效率谁快?
  • ¥15 蓝桥杯单片机第十三届第一场,整点继电器吸合,5s后断开出现了问题