← 返回题目列表

AtCoder · abc350_f

I. 转置

中文机器翻译题面 查看原题

分数: 550 点

问题陈述

给你一个字符串 S = S_1 S_2 S_3 \dots S_{|S|} 由大小写英文字母组成, (,和 ).
字符串中的括号 S 正确匹配。

重复以下操作,直到无法执行更多操作:

  • 首先,选择一对整数 (l, r) 满足以下所有条件:
    • l < r
    • S_l = (
    • S_r = )
    • 每个字符 S_{l+1}, S_{l+2}, \dots, S_{r-1} 是大写或小写英文字母。
  • 让 T = \overline{S_{r-1} S_{r-2} \dots S_{l+1}}.
    • 在这里, \overline{x} 表示通过切换每个字符的大小写得到的字符串 x (大写到小写,反之亦然)。
  • 然后,删除 l-th 通过 r第一个字符 S 并插入 T 位于删除发生的位置。

请参阅示例输入和输出以进行说明。

可以证明,可以去除所有 (和 使用上述操作从字符串中生成 ),最终的字符串与操作的执行方式和顺序无关。
确定最终字符串。

中的括号是什么意思 S 是否正确匹配? 首先,正确的括号序列定义如下:
  • 正确的括号序列是满足以下条件之一的字符串:
    • 这是一个空字符串。
    • 存在正确的括号序列 A,字符串是通过连接形成的 (, A, ) 按此顺序。
    • 存在非空正确括号序列 A 和 B,字符串是通过连接形成的 A 和 B 按此顺序。
中的括号 S 正确匹配当且仅当 (和 使用上述操作从字符串中生成 )提取自 S 在不改变顺序的情况下形成了正确的括号序列。

约束

  • 1 \le |S| \le 5 \times 10^5
  • S 由大小写英文字母组成, (,和 ).
  • 中的括号 S 正确匹配。

输入

输入由标准输入按以下格式给出:

S

输出

打印最终的字符串。


示例输入 1

((A)y)x

示例输出 1

YAx

让我们执行以下操作 S = ((A)y)x.

  • 选择 l=2 和 r=4。子串 (A) 被删除并替换为 a.
    • 此操作后, S = (ay)x.
  • 选择 l=1 和 r=4。子串 (ay) 被删除并替换为 YA.
    • 此操作后, S = YAx.

去掉括号后,字符串变成 YAx,应打印。


示例输入 2

((XYZ)n(X(y)Z))

示例输出 2

XYZNXYZ

让我们执行以下操作 S = ((XYZ)n(X(y)Z)).

  • 选择 l=10 和 r=12。子串 (y) 被删除并替换为 Y.
    • 此操作后, S = ((XYZ)n(XYZ)).
  • 选择 l=2 和 r=6。子串 (XYZ) 被删除并替换为 zyx.
    • 此操作后, S = (zyxn(XYZ)).
  • 选择 l=6 和 r=10。子串 (XYZ) 被删除并替换为 zyx.
    • 此操作后, S = (zyxnzyx).
  • 选择 l=1 和 r=9。子串 (zyxnzyx) 被删除并替换为 XYZNXYZ.
    • 此操作后, S = XYZNXYZ.

去掉括号后,字符串变成 XYZNXYZ,应打印。


示例输入 3

(((()))(()))(())

示例输出 3


最终结果可能是空字符串。


示例输入 4

dF(qT(plC())NnnfR(GsdccC))PO()KjsiI((ysA)eWW)ve

示例输出 4

dFGsdccCrFNNnplCtQPOKjsiIwwEysAve