自动搬运

查看原文

来自洛谷，原作者为

	DengDuck 澳門現役 OIer，萌萌未花日奈雙推人一枚

搬运于2025-08-24 23:14:33，当前版本为作者最后更新于2025-04-23 20:32:38，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

我感觉很简单啊。

就是，你考虑枚举所有的长度小于等于五的子串，然后目标是搞定左右的划分。

我们发现一种最简单有效的划分方法是一个同样字母的区间划分成一段，这样能保证出现的字母尽可能少而且区间长度经可能小，从而尽量满足条件。

我们发现这个方案唯一会导致出错的情况是同字母区间长度大于 $5$，这种本来就没有解，所以这个方案是最佳的。

然后我们只需要记录全局是否有解，没解的话所有枚举的子串都不可能出现在解里面，他们全部退役。否则对于每个枚举的子串，你考虑只要左右不冲突就一定有满足上述条件的方案，所以你 Check 区间 $S[L,R]$ 的时候只需要判断 $S_{L-1},S_{R+1}\in S[L,R]$ 就可以了。

时间复杂度是 $\mathcal O(n\log n)$ 的，因为用了 set 和 map。

可能没实现好。

#include<bits/stdc++.h>
using namespace std;
string S;
int n,Hav;
set<string>Se;
map<string,int>Ma;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>S;
	n=S.size(),S=" "+S;
	for(int i=1;i<=n-5;i++)
	{
		int Flg=1;
		for(int j=1;j<=6;j++)
		Flg&=S[i+j]==S[i];
		Hav|=Flg;	
	}
	for(int i=1;i<=n;i++)
	for(int j=1;j<=5;j++)
	{
		if(i+j-1>n)break;
		if(Hav)continue;
		int Flg=1;
		if(i!=1)
		for(int x=0;x<j;x++)if(S[i-1]==S[i+x])Flg=0;
		if(i+j-1!=n)
		for(int x=0;x<j;x++)if(S[i+j]==S[i+x])Flg=0;
		if(Flg)Ma[S.substr(i,j)]=1;
	}
	for(int i=1;i<=n;i++)
	for(int j=1;j<=5;j++)
	{
		if(i+j-1>n)break;
		Se.insert(S.substr(i,j));
	}
	vector<string>V;
	for(auto i:Se)
	{
		if(Ma[i])continue;
		V.push_back(i);
	}
	cout<<V.size()<<endl;
	for(auto i:V)
	{
		cout<<i<<endl;
	}
}