自动搬运

查看原文

来自洛谷，原作者为

	FjswYuzu Rainybunny狂热粉丝!111111 | Last Goodbye

搬运于2025-08-24 22:14:28，当前版本为作者最后更新于2019-12-14 12:05:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$\ \ \ \ \ \ \$初看这道题目，这是一道判定性问题，并且能够给出一个正确的序列。题意即为：有一个长 $2n$ 的由小写字母组成的字符串。判定有没有这些字母构成的一个首尾相连的字符串，使得任何一个长度为 $n$ 的字符串不等。

$\ \ \ \ \ \ \$我们无法找到内在的规律，考虑构造。

• 如果出现最多的字母出现次数小于 $n$，显然可以发现相同插进一个，可以的。

• 否则：

  • 如果只有一种字母，显然不能。

  • 如果有两种字母，并且另外一种字母出现次数小于 2，仍然不能。

  • 否则可以。首先输出 $n$ 个出现次数最多的字母，然后任意放一个其他字符，放完出现次数最多的字母，最后把剩下的字母全部输出，按出现最多的字母出现次数小于 $n$ 的方式输出。

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
char str[1000005];
int n,cnt[27];
int main(){
	scanf("%s",str+1);
	n=strlen(str+1);
	for(int i=1;i<=n;++i)	++cnt[str[i]-'a'];
	bool flag=false;
	int acs=0,where=0;
	for(int i=0;i<=25;++i)
	{
		if(cnt[i])	++acs;
		if(cnt[i]>n/2)
		{
			flag=true;
			where=i;
		}
	}
	if(flag)
	{
		if(acs==1)	return puts("NO")&0;
		if(acs==2 && n-cnt[where]<=2)	return puts("NO")&0;
		puts("YES");
		for(int i=1;i<=n/2;++i)	putchar(where+'a');
		for(int i=0;i<=25;++i)
		{
			if(cnt[i] && i!=where)
			{
				putchar(i+'a');
				--cnt[i];
				break;
			}
		}
		for(int i=1;i<=cnt[where]-n/2;++i)	putchar(where+'a');
		for(int i=0;i<=25;++i)	if(i!=where)	for(int j=1;j<=cnt[i];++j)	putchar(i+'a');
	}
	else
	{
		puts("YES");
		for(int i=0;i<=25;++i)	for(int j=1;j<=cnt[i];++j)	putchar(i+'a');
	}
	return 0;
}