很麻烦的一题

我的做法是先确定最长的两个串是前缀还是后缀

然后每个串用最长的串判断属于前缀还是后缀

如果都可以的话就均分

注意细节,特别是均分有一些细节

具体可以看看代码就懂了

比赛时我没有判断好最长的两个串是前缀还是后缀结果赛后被hack了

复杂度是O(n^2)

代码

#include <bits/stdc++.h>
#define il inline
#define Max 2005
#define int long long
using namespace std;
il int read()
{
    char c=getchar();
    int x=0,f=1;
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
char pr[Max],sf[Max],s[Max][Max],h[Max],t[Max],l,r;
int n,len[Max],bl[Max],cnt1,cnt2,cnth[Max],cntt[Max],st[Max],tp,cnt,s1[Max],s2[Max],maxlen,a,b;
il bool check(int x,int t,int opt)
{
    if(opt==2)
    {
        for(int i=1;i<=len[x];i++)
            if(s[x][i]!=s[t][i]) return 0;
        return 1;
    }
    else if(opt==1)
    {
        for(int i=1;i<=len[x];i++)
            if(s[x][len[x]-i+1]!=s[t][len[t]-i+1]) return 0;
        return 1;
    }
    return 1;
}
signed main()
{
    cin>>n;n=2*n-2;
    for(int i=1;i<=n;i++)
    {
        scanf("%s",s[i]+1);
        len[i]=strlen(s[i]+1);
        maxlen=max(maxlen,len[i]);
    }
    for(int i=1;i<=n;i++)
        if(len[i]==maxlen)
        {
            if(!b) b=i;
            else a=i;
        }
    for(int i=1;i<=n;i++)
    {
        if((!check(i,a,2))&&(!check(i,b,1))) swap(a,b),cnt++;
    }
    cnt=0;
    for(int i=1;i<=n;i++)
    {
        if(bl[i]) continue;
        if(check(i,b,1)&&!check(i,a,2)) bl[i]=2,cnt2++;
        else if(check(i,a,2)&&!check(i,b,1)) bl[i]=1,cnt1++;
        else if(check(i,b,1)&&check(i,a,2)) st[++tp]=i;
    }
    for(int i=1;i<=tp;i++)
    {
        if(cnt1<=cnt2) bl[st[i]]=1,cnt1++;
        else bl[st[i]]=2,cnt2++;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i!=j&&len[i]==len[j]&&check(i,j,2))
            {
                if(bl[i]==bl[j])
                    bl[i]=3-bl[i];
            }
        }
    }
    for(int i=1;i<=n;i++)
        if(bl[i]==1) putchar('P');
        else putchar('S');
    puts("");
}