Oh Those Palindromes

wjh15101051's space

卧薪尝胆，厚积薄发。

Date: Wed Oct 17 08:01:22 CST 2018

In Category: NoCategory

Description：

给一个字符串，重排他的所有字母使得新的串有最多的回文子串。

$1\leqslant n\leqslant 10^5$

Solution：

首先考虑回文子串的上限，每一对原串中相同的字母对都最多产生一个贡献，代表作为一个回文串的最左最右端，考虑怎么达到这个上限，发现只要排序，相同的就会跑到一起，然后就能达到上限了。

Code：


#include<bits/stdc++.h>

using namespace std;

#define MAXN 100010

char c[MAXN];

int main()

{

	int n;cin >> n;

	scanf("%s",c + 1);

	sort(c + 1,c + 1 + n);

	for(int i = 1;i <= n;++i)cout << c[i];cout << endl;

	return 0;

}

In tag: 玄学

wjh15101051