← 返回题目列表

AtCoder · arc136_a

A. A与BB互换

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

分数: 300 点

问题陈述

给你一个字符串 S 长度 N 组成 A, B, C.

您可以对以下两种操作 S 以任意顺序任意次数。

  • 选择 A in S,删除它,然后插入 BB 在那个位置。
  • 选择两个相邻的字符 BB in S,删除它们,然后插入 A 在那个位置。

找到按字典顺序排列的最小可能字符串 S 可能会在您的操作后变成。

字典顺序是什么?

简单来说,词典顺序就是单词在词典中列出的顺序。作为更正式的定义,这里是确定不同字符串之间的字典顺序的算法 S 和 T.

下面,让 S_i 表示 i- 第一个字符 S。另外,如果 S 按字典顺序小于 T,我们将该事实表示为 S \lt T;如果 S 按字典顺序大于 T,我们将该事实表示为 S \gt T.

  1. 让 L 是以下长度中较小的一个 S 和 T。对于每个 i=1,2,\dots,L,我们检查是否 S_i 和 T_i 是相同的。
  2. 如果有 i 这样 S_i \neq T_i,让 j 是最小的这样 i。然后,我们比较 S_j 和 T_j。如果 S_j 早于 T_j 按字母顺序排列,我们确定 S \lt T 然后退出;如果 S_j 晚于 T_j,我们确定 S \gt T 然后退出。
  3. 如果没有 i 这样 S_i \neq T_i,我们比较长度 S 和 T。如果 S 短于 T,我们确定 S \lt T 然后退出;如果 S 长于 T,我们确定 S \gt T 然后退出。

约束

  • 1 \leq N \leq 200000
  • S 是一个长度为 N 组成 A, B, C.

输入

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

N
S

输出

打印答案。


示例输入 1

4
CBAA

示例输出 1

CAAB

我们应该执行以下操作。

  • 最初,我们有 S=CBAA.
  • 删除 3-rd 字符 A 并插入 BB, 制作 S=CBBBA.
  • 删除 2-nd 和 3-rd 字符 BB 并插入 A, 制作 S=CABA.
  • 删除 4- 第一个字符 A 并插入 BB, 制作 S=CABBB.
  • 删除 3-rd 和 4- 第一个字符 BB 并插入 A, 制作 S=CAAB.

我们不能让 S 按字典顺序小于 CAAB。因此,答案是 CAAB.


示例输入 2

1
A

示例输出 2

A

我们不做任何操作。


示例输入 3

6
BBBCBB

示例输出 3

ABCA