题解 P5799 【[SEERC2019]Cycle String?】
FjswYuzu
·
·
题解
$\ \ \ \ \ \ \ $我们无法找到内在的规律，考虑构造。
- 如果出现最多的字母出现次数小于 $n$，显然可以发现相同插进一个，可以的。
- 否则：
- 如果只有一种字母，显然不能。
- 如果有两种字母，并且另外一种字母出现次数小于 2，仍然不能。
- 否则可以。首先输出 $n$ 个出现次数最多的字母，然后任意放一个其他字符，放完出现次数最多的字母，最后把剩下的字母全部输出，按出现最多的字母出现次数小于 $n$ 的方式输出。
```cpp
#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;
}
```