[arc113_e]Rvom and Rsrev

ID: 2573

传统题

2000ms

1024MiB

尝试: 0

已通过: 0

难度: 省选/NOI-

上传者:

admin

标签>

2700+

問題文

a と b からなる文字列 $S$ が与えられます。 $S$ に以下の操作を $0$ 回以上繰り返してできる辞書順最大の文字列を求めてください。

同一の文字である $S$ の $2$ 箇所の文字を選ぶ。それらの間の文字列を前後反転させ、選んだ $2$ 文字を削除する。すなわち、 $S$ の $i$ 文字目を $s_i$ と表すことにすれば、 $s_i=s_j$ なる $i < j$ を選んで $S$ を $s_1\\dots s_{i-1}s_{j-1}\\dots s_{i+1}s_{j+1}\\dots s_{|S|}$ で置き換える。

なお、この問題ではテストケースが $T$ 個与えられます。 $i$ 個目のテストケースは文字列 $S_i$ で表され、 $S=S_i$ に対して上記の問題を解く問題です。

制約

$1 \\leq T \\leq 2\\times 10^5$
$1 \\leq |S_i|\\quad (i=1,\\dots, T)$
$1 \\leq |S_1| + \\dots + |S_T| \\leq 2\\times 10^5$
$S_i$ は a と b からなる

入力

入力は以下の形式で標準入力から与えられる。

$T$ $S_1$ $\\vdots$ $S_T$

出力

$T$ 行出力せよ。 $i$ 行目には、 $S_i$ に操作を $0$ 回以上繰り返してできる辞書順最大の文字列を出力せよ。

入力例 1

20
abbaa
babbb
aabbabaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
bbabaaaaabbaababaaabbabbbbbaaaaa
babbbaaaabaababbbabaabaaaaababaa
bbaababababbbaaabaabababaabbabab
abaabbabaabaaaaabaaaabbaabaaaaab
aabababbabbabbabbaaaabbabbbabaab
aabababbabbbbaaaabbaaaaabbaaaabb
abbbbaabaaabababaaaababababbaabb
aaaaaaaaaaaaaaaaaaaaaaabbbbbbbbb
aaaaaaaaaabbbbbbbbbbbbbbbbbbbbbb
abababaaababaaabbbbbaaaaaaabbbbb
aabbaaaaababaabbbbbbbbbaabaaabbb
babababbababbbababbbbbababbbabbb
bbbbababbababbbabababbabbabbbbbb
aaaaaaaaaaaaaaaaababababbbabbbbb
aabababbabbabababababababbbbabbb

出力例 1

bba
bba
bbba
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbaaaaaaaa
bbbbbbbbbbbbbaaaaaaa
bbbbbbbbbbbbbbbb
bbbbbbbbbb
bbbbbbbbbbbbbbbbab
bbbbbbbbbbbbbb
bbbbbbbbbbbbbabb
abbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbaaaaaaaaa
bbbbbbbbbbbbbbbaaaaa
bbbbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbba
bbbbbbbbbaaaaaaaaaaaaaaa
bbbbbbbbbbbbbbbbba

$1$ 個目のテストケースは、 $1$ 文字目と $4$ 文字目に対して操作を行うことで $S$ を bba にできます。
$2$ 個目のテストケースは、 $1$ 文字目と $5$ 文字目に対して操作を行うことで $S$ を bba にできます。
$3$ 個目のテストケースは、 $1$ 文字目と $2$ 文字目に対して操作を行うことで $S$ を bbabaa にでき、その後 $3$ 文字目と $5$ 文字目に対して操作を行うことで $S$ を bbba にできます。

#arc113e. [arc113_e]Rvom and Rsrev

問題文

制約

入力

出力

入力例 1

出力例 1

登录