P10905 [蓝桥杯 2024 省 C] 回文字符串

题目描述

小蓝最近迷上了回文字符串，他有一个只包含小写字母的字符串 $S$，小蓝可以往字符串 $S$ 的开头处加入任意数目个指定字符：l、q、b（ASCII 码分别为：$108$、$113$、$98$）。小蓝想要知道他是否能通过这种方式把字符串 $S$ 转化为一个回文字符串。

输入格式

输入的第一行包含一个整数 $T$，表示每次输入包含 $T$ 组数据。

接下来依次描述 $T$ 组数据。

每组数据一行包含一个字符串 $S$。

输出格式

输出 $T$ 行，每行包含一个字符串，依次表示每组数据的答案。如果可以将 $S$ 转化为一个回文字符串输出 Yes，否则输出 No。

输入输出样例 #1

输入 #1

3
gmgqlq
pdlbll
aaa

输出 #1

Yes
No
Yes

说明/提示

【样例说明】

对于 gmgqlq，可以在前面加上 qlq => qlqgmgqlq 转化为一个回文字符串；

对于 pdlbll，无法转化为一个回文字符串；

对于 aaa，本身就是一个回文字符串。

【评测用例规模与约定】

对于 $50\%$ 的评测用例，$1\le |S|\le 1000$，其中 $|S_j|$ 表示字符串 $S$ 的长度；
对于所有评测用例，$1\le T\le 10$，$1\le \sum |S|\le 10^6$。

C++实现

#include <bits/stdc++.h>
using namespace std;
int T,n;
char s[1000005];
int main(){
	int p1,p2;
	bool flag;
	scanf("%d",&T);
	while(T--){
		scanf("%s",s+1);
		n=strlen(s+1),p1=0,p2=n+1,flag=1;
		while(p2>1&&(s[p2-1]=='l'||s[p2-1]=='q'||s[p2-1]=='b'))  p2--;//计算右指针
		while(p1<p2-1&&(s[p1+1]=='l'||s[p1+1]=='q'||s[p1+1]=='b'))  p1++;//计算左指针
		for(int i=p1+1,j=p2-1;i<j;i++,j--)//判断中间字符串是否回文
			if(s[i]!=s[j]){
				flag=0;
				break;
			}
		if(p2+p1-1>n)  flag=0;//防止MLE
		else
			for(int i=1;i<=p1;i++)//判断左右字符串是否合法
				if(s[p1-i+1]!=s[p2+i-1]){
					flag=0;
					break;
				}
		printf("%s\n",flag?"Yes":"No");
	}
	return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容