专栏文章

题解：B4101 [CSP-X2023 山东] 回文字符串

DDL_ZZS_114514
B4101题解参与者 4已保存评论 3

文章操作

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

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

B4101 题目传送门

可以利用双指针的思想

设立指针 LL 从左到右移动遍历字符串 ss，RR 从右到左移动，直到, L≥RL\geq R 则：
  • 如果 s[L]=s[R]s[L]=s[R]，那就说明这两个字符可以满足形成两个回文的子串，此时 ansans 就增加2。
  • 否则，s[L]≠s[R]s[L]\neq s[R]，此时无法满足条件，那么就从这里开始构造两个字符串 slsl 和 srsr，继续遍历，slsl 和 srsr 分别表示从此时的 LL 和 RR 开始，一直到两个字符串互为回文，或者 L≥RL\geq R （即 LL,RR 相遇）时的字符串。
    • 其中如果构造的两个字符串互为回文，则又有了两个满足条件的子串。ansans 增加2。
    • 如果直到 LL 和 RR 相遇还无法满足，那么只有这两个串合起来的一个大串。ansans 增加1。

注意一点：

当判断构造的两个子串 slsl 和 srsr 是否满足互为回文的条件时，只需要判断两个子串是否相等，因为已知了此时 s[L]≠s[R]s[L]\neq s[R]，所以两个字符串无法在相对位置回文。

参考代码

CPP
#include <bits/stdc++.h>
#define int long long
using namespace std;
string s;
int ans;
signed main() {
	//freopen("palindrome.in","r",stdin);
	//freopen("palindrom.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
  //如果你用cin，建议关闭同步流增加效率
	cin>>s;
	int l=0,r=s.size()-1;
	while(l<r){
		if(s[l]==s[r]){
			ans+=2;
			l++;r--;//继续遍历
			if(l==r) ans++;//如果再遍历一步后，L和R正好重合，那么此时又能创造一个大字符串，所以ans再加一
		}
		else{
			string sl,sr;
			while(l<r){
				sl+=s[l++];
				sr=s[r--]+sr;//给子串拼接新遍历的字符
				if(sl==sr) break;//判断是否互为回文
			}
			if(sl!=sr){
				ans++;    //不回文，增加一个
			}
			else ans+=2;//回文，增加两个
		}
	}
	if(ans<=1){
		cout<<"NO\n";
	}//如果到最后只有一个串满足，那就是大串自己，所以输出 NO
	else{
		cout<<"YES\n"<<ans<<"\n";
	}//否则，大串满足条件，再输出能分割成的子串数 ans
	return 0;
    //完结撒花
}

这是小蒟蒻的第一篇题解，可以给个赞吗%%

评论

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

正在加载评论...