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

AT_agc066_f.[AGC066F] Beautiful String

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

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

题目描述

我们将满足以下条件的字符串称为美丽字符串：

  • 每个字符都是 A、B 或 C 之一。
  • 任意相邻的 22 个字符都不相同。

例如，AB、BCAC 是美丽字符串，而 BB、CBAAC 不是美丽字符串。

给定一个美丽字符串 SS，你可以对其反复进行如下操作：

  • 操作：交换 SS 中相邻的 22 个字符，但交换后得到的 SS 也必须是美丽字符串。

请你求出最终可能得到的字典序最小的字符串 SS。

有 TT 个测试用例，请分别输出每个测试用例的答案。

输入格式

输入通过标准输入给出，格式如下：

TT
case1\text{case}_1
⋮\vdots
caseT\text{case}_T

每个测试用例输入格式如下：

SS

输出格式

请输出 TT 行，第 ii 行输出第 ii 个测试用例最终可能得到的字典序最小的字符串。

输入输出样例

  • 输入#1

    8
CAB
ACBCB
B
AC
BACBA
BABABA
ABCBCAC
CBABACABCBABABC

    输出#1

    ABC
ABCBC
B
AC
ABABC
BABABA
ABCACBC
ABABACBCACBCBAB

说明/提示

限制

  • 1≤T≤1051\leq T\leq 10^5
  • SS 是美丽字符串。
  • 1≤∣S∣≤1061\leq |S|\leq 10^6
  • 所有测试用例中 ∣S∣|S| 的总和不超过 10610^6。

样例解释 1

对于第 11、22 个测试用例，以下是将 SS 字典序最小化的一种方式：

  • CAB → ACB → ABC
  • ACBCB → CABCB → CBACB → BCACB → BCABC → BACBC → ABCBC

由 ChatGPT 4.1 翻译

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

首页