题目详情题解（0）讨论（0）提交记录（0）

AT_abc307_d.[ABC307D] Mismatched Parentheses

普及-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个由小写英文字母以及 (、) 组成的长度为 NN 的字符串 SS。
请重复执行如下操作，直到无法继续为止，并输出最终的 SS。

  • 可以任选 SS 的一个连续子串，要求该子串的第一个字符为 (，最后一个字符为 )，且除了首尾之外不包含任何 ( 或 )，然后将这个子串删除。

可以证明，无论操作顺序如何，最终得到的 SS 是唯一的。

输入格式

输入以以下格式从标准输入给出。

NN SS

输出格式

请输出答案。

输入输出样例

  • 输入#1

    8
a(b(d))c

    输出#1

    ac

  • 输入#2

    5
a(b)(

    输出#2

    a(

  • 输入#3

    2
()

    输出#3

  • 输入#4
    6
)))(((
    输出#4
    )))(((
说明/提示
限制条件


    

  • 1≤N≤2×1051 \leq N \leq 2 \times 10^5
    • 

  • NN 是整数
    • 

  • SS 是由小写英文字母和 (、) 组成的长度为 NN 的字符串
    • 



样例解释 1


例如，可以按如下步骤操作，最终 SS 变为 ac。


    

  • 删除 SS 的第 44 个到第 66 个字符组成的子串 (d)，此时 SS 变为 a(b)c。
    • 

  • 删除 SS 的第 22 个到第 44 个字符组成的子串 (b)，此时 SS 变为 ac。
    • 

  • 此时无法再进行操作。
    • 



样例解释 3


最终的 SS 可能为空字符串。


由 ChatGPT 4.1 翻译


输入解题思路，AI测评打分。不知道怎么写? 
首页