题目概括

在一个字符串前插入若干个指定字符：l、q、b，使得这个字符串成为一个回文字符串。

算法 & 数据结构 & 思想

洛谷标签：模拟

主要是了解回文串的特点，和题目中只能在字符串前面添加字符这个特点。

错误点

注意在 check 函数中，访问字符串中的位置的时候一定要判断有没有超出字符串长度或者小于 0。

思路

80 分（TLE 了两个点）

找到从后面往前数的最后一个指定字符，记录下来为 pos，然后遍历从 pos 往后的所有和 s[0] 相同的字符，然后验证每一个是否可以成为回文串。

100 分

我们发现可以分两种情况，就是第一个字符是指定字符还是不是。

如果不是给定字符，那么我们只需要验证 [0, pos - 1] 的字串是不是回文串。

如果是给定的字符，那么我们设最开始有 $x$ 个连续的指定字符 ，那么我们只用看 [0, pos - 1 + x] 是不是回文串就行了。因为字符串前面永远加的都是指定字符，而如果后来字符串回文了，那么加的一定和原先的最后面的几个是相同的。

代码（100 分）

#include <bits/stdc++.h>

using namespace std;
#define int long long

string s; 
bool check(int x) {
    if (x >= s.size()) return 0;
    for (int i = 0, j = x; i <= j && j >= 0; i ++, j --) {
        if (s[i] != s[j]) return 0;
    }
    return 1;
}
void solve() {
    vector <int> pos;
    cin >> s;

    int flag = s.size();
    for(int i = s.size() - 1;i >= 0; i --) {
        if (s[i] != 'l' && s[i] != 'q' && s[i] != 'b') break;
        else flag = i;
    }
    // cout << flag << "\n";
    if (flag == 0) {
        cout << "Yes\n";
        return;
    }
    // if (s[0] != 'l' && s[0] != 'q' && s[0] != 'b') {
    //     if (check(flag - 1)) cout << "Yes\n";
    //     else cout << "No\n";
    //     return;
    // }
    int f2 = 0;
    for (int i = 0; i < s.size(); i ++) {
        if (s[i] != 'l' && s[i] != 'q' && s[i] != 'b') {
            f2 = i;
            break;
        }
    }
    // cout << f2 << " " << flag << "\n";
    if (check(flag + f2 - 1)) cout << "Yes\n";
    else cout << "No\n";
    // for (int i = flag - 1; i < s.size(); i ++) {
    //     if (s[i] == s[0]) pos.push_back(i);
    // }
    // for (auto x : pos) {
    //     // cout << x << "\n";
    //     if (check(x)) {
    //         cout << "Yes\n";
    //         return;
    //     }
    // }
    // cout << "No\n";
}
signed main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T; cin >> T;
    while (T --) {
        solve();
    }
    return 0;
}