P12318 [蓝桥杯 2024 国研究生组] 分割字符串 题解

· · 题解

我感觉很简单啊。

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

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

我们发现这个方案唯一会导致出错的情况是同字母区间长度大于 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;
    }
}