关于cf题
  • 板块CF25E Test
  • 楼主lc_lca
  • 当前回复3
  • 已保存回复3
  • 发布时间2020/6/3 21:20
  • 上次更新2023/11/7 01:13:19
查看原帖
关于cf题
120340
lc_lca楼主2020/6/3 21:20

哪位大佬能把cf25e的第九个数据弄下来啊网太卡了上不去, 我调了好久还是认为自己考虑到了所有的情况,想看看这个第九个数据究竟是啥。

我知道可能很大,但是看样子应该是很有规律的

大佬要是发现代码漏洞也好啊,感谢

#include<iostream>
#include<cstring>
#define int long long
using namespace std;
string s[5];
int nxt[100010];
int min(int q,int w)
{
    if(q<w) return q;
    return w;
}
char ta[100010],tb[100010],f[100010];
int kmp(string a,string b)
{
    swap(a,b);
    memset(nxt,0,sizeof nxt);
    memset(f,0,sizeof f);
    int lena=a.size();
    for(int i=0;i<lena;i++)
    {
        ta[i+1]=a[i];
    }
    int lenb=b.size();
    for(int i=0;i<lenb;i++)
    {
        tb[i+1]=b[i];
    }
    nxt[1]=0;
    for(int i(2),j(0);i<=a.length();++i)
    {
        while(j>0 && ta[i]!=ta[j+1])j=nxt[j];
        if(ta[i]==ta[j+1])j++;
        nxt[i]=j;
    }
    for(int i(1),j(0);i<=b.length();++i)
    {
        while(j>0 && (j==a.length() || tb[i]!=ta[j+1]))j=nxt[j];
        if(tb[i]==ta[j+1])j++;
        f[i]=j;
        if(f[i]==a.length()) return -928;
    }
    return f[b.length()];
}
signed main()
{
    cin>>s[1]>>s[2]>>s[3];
    int ans=s[1].size()+s[2].size()+s[3].size();
    for(int i=1;i<=3;i++)
    {
        for(int j=1;j<=3;j++)
        {
            for(int h=1;h<=3;h++)
            {
                if(i==j || i==h || j==h) continue;
                int chonghe1=kmp(s[i],s[j]);
                string tmp="";
                if(chonghe1==-928)
                    tmp=s[i];
                else
                {
                    tmp+=s[i].substr(0,s[i].length()-chonghe1);
                    tmp+=s[j];
                }
                int chonghe2=kmp(tmp,s[h]);
                if(chonghe2==-928)
                {
                    ans=min(ans,tmp.length());
                }
                else ans=min(ans,tmp.length()+s[h].length()-chonghe2);
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

2020/6/3 21:20
加载中...