AT_agc026_e.[AGC026E] Synchronized Subsequence

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

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

题目描述

给定一个由 $N$ 个 a 和 $N$ 个 b 组成的长度为 $2N$ 的字符串 $S$ 。

你可以从 $S$ 中选择一些字符。但对于每个 $i=1,2,\ldots,N$ ，你不能只选择 $S$ 中第 $i$ 个出现的 a 或第 $i$ 个出现的 b 中的一个。也就是说，对于每一对第 $i$ 个 a 和第 $i$ 个 b，要么都选，要么都不选。然后将选中的字符（按照 $S$ 中的顺序）拼接起来。

请你求出在满足上述条件的所有字符串中，字典序最大的一个。

输入格式

输入从标准输入中给出，格式如下：

$N$ $S$

输出格式

请输出满足条件的 $T$ 中，字典序最大的一个。

输入输出样例

输入#1
```
3
aababb
```
输出#1
```
abab
```
输入#2
```
3
bbabaa
```
输出#2
```
bbabaa
```
输入#3
```
6
bbbaabbabaaa
```
输出#3
```
bbbabaaa
```
输入#4
```
9
abbbaababaababbaba
```
输出#4
```
bbaababababa
```

说明/提示

限制

$1 \leq N \leq 3000$
$S$ 是由 $N$ 个 a 和 $N$ 个 b 组成的长度为 $2N$ 的字符串。

样例解释 1

由 $S$ 的第 $1,3,4,6$ 个字符组成的子序列 $T$ 满足条件。

样例解释 2

也可以选择所有字符。

由 ChatGPT 4.1 翻译

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

首页