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

AT_agc036_e.[AGC036E] ABC String

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

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

题目描述

给定一个由 A、B、C 组成的字符串 SS。

请你求出 SS 的一个不一定连续的子序列 xx，使得 xx 满足以下所有条件，并且在所有满足条件的子序列中长度最长。子序列指的是从 SS 中删除 00 个或多个字符后得到的字符串。

  • xx 中包含的 A、B、C 的数量都相等。
  • 在 xx 中，相同的字符不会相邻出现。

输入格式

输入从标准输入读取，格式如下：

SS

输出格式

请输出满足条件的最长子序列中的一个。如果有多个答案，输出其中任意一个都视为正确。

输入输出样例

  • 输入#1

    ABBCBCAB

    输出#1

    ACBCAB

  • 输入#2

    ABABABABACACACAC

    输出#2

    BABCAC

  • 输入#3

    ABCABACBCBABABACBCBCBCBCBCAB

    输出#3

    ACABACABABACBCBCBCBCA

  • 输入#4

    AAA

    输出#4

说明/提示
限制


    

  • 1≤∣S∣≤1061 \leq |S| \leq 10^6
    • 

  • SS 仅由 A、B、C 组成。
    • 



样例解释 1


以 SS 的子序列 ACBCAB 为例，它满足所有条件，并且是最长的。ABCBCA 也是满足条件的最长子序列。ABCBCAB、ABBCCA 等虽然是 SS 的子序列，但不满足条件。


样例解释 4


有时，唯一满足条件的子序列可能是空字符串。


由 ChatGPT 4.1 翻译


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