题解：P13790 「CZOI-R6」Border

wuhaolinwhl · 2025-08-21 21:04:13 · 题解

P13790题解

题目大意

这道题让我们修改题目所给的字符串 s，使字符串 s 的 border 长度最大。

思路解析

我们看到题目，我们要找到一个字符串 b，使得 b 为字符串 s 的前缀和后缀。因为字符串 s 的前缀的开头永远为 s[0]，所以我们可以通过枚举字符串后缀的开头来求得答案（后缀的结尾一定为字符串的最后一位，所以我们可以求得字符串 b 的长度）。

重点

通过枚举后缀开头的方式，加上判断方案是否合法。但这样会超时，我们可以通过分类讨论的方式进行处理，当当前枚举的后缀开头等于 s[0] 时分为一类讨论，不等于 s[0] 的分为另一类讨论，取两种方案的最大值。
判断方案是否合法的方法较为简单，就是简单模拟加贪心。直接看代码吧。

#include<bits/stdc++.h>
#define down 0.996
using namespace std;
string s;
long long ans;
queue <int> q,q1;
int main()
{
    cin>>s;
    for(int i=1;i<s.size();i++)
    {
        if(s[i]==s[0])
        {
            q.push(i);
        }
        else
        {
            q1.push(i);
        }
    }
    long long u;
    while(!q.empty())
    {
        long long r=q.front(),op=0,id;
        char lst;
        q.pop();
        for(int i=r+1;i<s.size();i++)
        {
            if(s[i]!=s[i-r])
            {
                op++;
                if(op==1)
                {
                    id=i;
                    lst=s[i];
                    s[i]=s[i-r];
                }
            }
            if(op==2)
            {
                s[id]=lst;
                break;
            }
        }
        if(op<=1)
        {
            ans=s.size()-r;
            s[id]=lst;
            u=r;
            break;
        }
        s[id]=lst;
    }
    while(!q1.empty())
    {
        long long r=q1.front(),op=1;
        if(u<r) break;
        char lst=s[r];
        s[r]=s[0];
        q1.pop();
        for(int i=r+1;i<s.size();i++)
        {
            if(s[i]!=s[i-r])
            {
                op++;
            }
            if(op==2)
            {
                break;
            }
        }
        if(op<=1)
        {
            long long o=s.size()-r;
            ans=max(o,ans);
            s[r]=lst;
            break;
        }
        s[r]=lst;
    }
    cout<<ans;
    return 0;
 } 

完结撒花，又切了一道绿题。