题目 3225: 蓝桥杯2024年第十五届省赛真题-回文字符串

题目 3225: 蓝桥杯2024年第十五届省赛真题-回文字符串
时间限制: 2s 内存限制: 512MB 提交: 1804 解决: 200
题目描述
小蓝最近迷上了回文字符串，他有一个只包含小写字母的字符串 S ，小蓝可以往字符串 S 的开头处加入任意数目个指定字符：l、q、b （ASCII 码分别为：108、113、98）。小蓝想要知道他是否能通过这种方式把字符串 S 转化为一个回文字符串。
输入格式
输入的第一行包含一个整数 T，表示每次输入包含 T 组数据。接下来依次描述 T 组数据。每组数据一行包含一个字符串 S 。
输出格式
输出 T 行，每行包含一个字符串，依次表示每组数据的答案。如果可以将S 转化为一个回文字符串输出 Yes，否则输出 No 。
样例输入复制
3
gmgq
lqpdlbll
aaa
样例输出复制
Yes
No
Yes
提示
【样例说明】

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

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

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

【评测用例规模与约定】

对于 50% 的评测用例，1 ≤ |S | ≤ 1000 ，其中 |S | 表示字符串 S 的长度；对于所有评测用例，1 ≤ T ≤ 10 ，1 ≤∑|S | ≤ 106 。

1.分析

        减去末尾连续的l  q   b ，判断之后的字符是否为回文。如果是就可以通过在前面添加形回文字符串。

2.代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int MAX = 1e5+10;
typedef long long LL;
int T;
string str;
bool check(string s) {
    for (int i = 0; i < s.size() / 2; i++) {
        if (s[i] != s[s.size() - 1 - i]) return false;
    }
    return true;
}
int main() {
    cin >> T;
    while (T--) {
        cin >> str;
        int d = 0;
        for (int i = str.size() - 1; i >= 0; i--) {
            if (str[i] != 'l' && str[i] != 'q' && str[i] != 'b') {
                d = i;
                break;
            }
        }
        string s = "";
        for (int i = 0; i <= d; i++) {
            s += str[i];
        }
        if (check(s) || s == "") cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}