专栏文章

题解：P13790 「CZOI-R6」Border

wwuhaolinwhl
P13790题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mio7bgen
此快照首次捕获于
2025/12/02 14:32
3 个月前
此快照最后确认于
2025/12/02 14:32
3 个月前
查看原文

P13790题解

题目大意

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

思路解析

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

重点

通过枚举后缀开头的方式，加上判断方案是否合法。但这样会超时，我们可以通过分类讨论的方式进行处理，当当前枚举的后缀开头等于 s[0]s[0] 时分为一类讨论，不等于 s[0]s[0] 的分为另一类讨论，取两种方案的最大值。
判断方案是否合法的方法较为简单，就是简单模拟加贪心。直接看代码吧。
CPP
#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;
 }
完结撒花，又切了一道绿题。

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...