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

· · 题解

P10905（模拟）

题目大意：

给出一个字符串，求是否可以在左边任意加 l、q、b 三个字符，使得字符串变成回文字符串。

思路分析：

首先我们发现有三种情况是可以变成回文的：

  1. 整个字符串本来就是回文的。
  2. 整个字符串都由 l、q、b 三个字符组成。
  3. 左边有一部分字符串是回文的，右边的字符串都由 l、q、b 三个字符组成。

于是我们有了一个想法：把右边连续的由 l、q、b 组成的字符串删掉，然后判断左边是否回文。

然而这个想法是错误的（我就在这卡了很久），因为有些字符串如果把右边的 l、q、b 都删掉的话左边就没法形成回文字符串了（比如 qwq）。

然后我们可以想到把左、右侧连续的 l、q、b 都取出来，那么中间剩下的这一段必须是回文的，然后我们再判断一下左边的字符串是否可以和右边字符串的前面一部分形成回文串就可以了（因为右边字符串的后面部分可以通过再整个字符串前面添加一些字符得到）。

注意：如果整个字符串都由 l、q、b 组成，左右指针可能会分别跑到右端点、左端点，一定要判断一下。

完整代码：

#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;
}