CF1063A Oh Those Palindromes

    • 180通过
    • 217提交
  • 题目来源 CodeForces 1063A
  • 评测方式 RemoteJudge
  • 标签 字符串 构造 概率论,统计
  • 难度 提高+/省选-
  • 时空限制 2000ms / 256MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    题目描述

    一个非空字符串叫做回文串。如果它从左到右,从右到左读相同,那么它就是回文串。 例如,“ABCBA”,“A”和“ABBA”都是回文串,而“ABAB”和“XY”则不是。

    如果可以通过从字符串的开头和结尾删除一些(可能为零)字符来从该字符串获得新字符串, 则新字符串叫做另一个字符串的子字符串。 例如,“ABC”、“AB”和“C”是字符串“ABC”的子串,而“AC”和“D”不是。

    我们把字符串的“回文计数”定义为回文的子串个数。 例如,字符串“aaa”的回文计数是6,因为它的所有子字符串都是回文, 而字符串“abc”的回文计数是3,因为只有长度为1的子字符串是回文。

    给你一个字符串S。你可以任意地重新排列它的字符,求它的回文计数最大值。

    输入输出格式

    输入格式:

    第一行包含整数n(1≤n≤100000)表示字符串s的长度。

    第二行包含字符串S,它由n个小写字母组成。

    输出格式:

    输出字符串t,(它是字符串s的一种排列) 此外,t应该具有最大回文计数的可能值。

    如果有多个这样的字符串,输出它们中的任何一个。

    输入输出样例:

    输入样例#1:

    5
    oolol

    输出样例#1:

    ololo

    输入样例#2:

    16
    gagadbcgghhchbdf

    输出样例#2:

    16
    gagadbcgghhchbdf

    说明:

    在第一个例子中,字符串“ololo”有9个9回文子串: "o","l","o","l","o","olo","lol","olo","oloo"

    注意,即使某些子串重合,它们也会在生成的字符串中计入多次。

    在第二个例子中,字符串“abccbaghghghgdfd”的回文计数为29。

    题目描述

    A non-empty string is called palindrome, if it reads the same from the left to the right and from the right to the left. For example, "abcba", "a", and "abba" are palindromes, while "abab" and "xy" are not.

    A string is called a substring of another string, if it can be obtained from that string by dropping some (possibly zero) number of characters from the beginning and from the end of it. For example, "abc", "ab", and "c" are substrings of the string "abc", while "ac" and "d" are not.

    Let's define a palindromic count of the string as the number of its substrings that are palindromes. For example, the palindromic count of the string "aaa" is $ 6 $ because all its substrings are palindromes, and the palindromic count of the string "abc" is $ 3 $ because only its substrings of length $ 1 $ are palindromes.

    You are given a string $ s $ . You can arbitrarily rearrange its characters. You goal is to obtain a string with the maximum possible value of palindromic count.

    输入输出格式

    输入格式:

    The first line contains an integer $ n $ ( $ 1 \le n \le 100\,000 $ ) — the length of string $ s $ .

    The second line contains string $ s $ that consists of exactly $ n $ lowercase characters of Latin alphabet.

    输出格式:

    Print string $ t $ , which consists of the same set of characters (and each characters appears exactly the same number of times) as string $ s $ . Moreover, $ t $ should have the maximum possible value of palindromic count among all such strings strings.

    If there are multiple such strings, print any of them.

    输入输出样例

    输入样例#1: 复制
    5
    oolol
    
    输出样例#1: 复制
    ololo
    
    输入样例#2: 复制
    16
    gagadbcgghhchbdf
    
    输出样例#2: 复制
    abccbaghghghgdfd
    

    说明

    In the first example, string "ololo" has $ 9 $ palindromic substrings: "o", "l", "o", "l", "o", "olo", "lol", "olo", "ololo". Note, that even though some substrings coincide, they are counted as many times as they appear in the resulting string.

    In the second example, the palindromic count of string "abccbaghghghgdfd" is $ 29 $ .

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。