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

CF1975H.378QAQ and Core

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

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

题目描述

378QAQ 有一个长度为 nn 的字符串 ss。定义一个字符串的“核心”为其字典序最大的子串†^\dagger。

例如，"bazoka" 的核心是 "zoka"，"aaa" 的核心是 "aaa"。

378QAQ 想要重新排列字符串 ss，使得其核心的字典序最小。请你找出所有 ss 的重排中，核心字典序最小的方案。

†^\dagger 字符串 ss 的子串是 ss 中一段连续的字母。例如，"defor"、"code" 和 "o" 都是 "codeforces" 的子串，而 "codes" 和 "aaa" 不是。

‡^\ddagger 如果字符串 pp 满足以下任一条件，则称 pp 的字典序小于 qq：

  • pp 是 qq 的前缀，且 p≠qp \ne q；
  • 在 pp 和 qq 第一个不同的位置，pp 的该字符的 ASCII 码小于 qq 的对应字符。

例如，"code" 和 "coda" 的字典序都小于 "codeforces"，而 "codeforceston" 和 "z" 则不是。

输入格式

每个测试包含多组测试数据。第一行包含测试用例数 tt（1≤t≤1051\leq t\leq 10^5）。接下来是每组测试数据的描述。

每组测试数据的第一行包含一个整数 nn（1≤n≤1061\leq n\leq 10^6），表示字符串 ss 的长度。

接下来一行包含一个长度为 nn 的字符串 ss，仅包含小写英文字母。

保证所有测试用例中 nn 的总和不超过 10610^6。

输出格式

对于每组测试数据，输出所有重排方案中核心字典序最小的结果。

输入输出样例

  • 输入#1

    6
3
qaq
4
cccc
6
bazoka
6
zazzzz
7
ababbbb
7
ccbabcc

    输出#1

    qaq
cccc
z
zzz
bbababb
cbcacbc

说明/提示

在第一个测试用例中，所有可能的重排及其对应的核心如下：

  • "qaq"，其核心为 "qaq"。
  • "aqq"，其核心为 "qq"。
  • "qqa"，其核心为 "qqa"。

因此，所有重排方案中核心字典序最小的是 "qaq"。

由 ChatGPT 4.1 翻译

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

首页