题解

题目解析

• 输入输出：第一行输入整数 $n$ 表示字符串数量。随后 $n$ 行每行一个仅含小写字母的字符串。对每个字符串，若其能拆分为两个长度均不小于 $2$ 的回文子串首尾拼接而成，则输出 Yes，否则输出 No。
• 数据范围：$1 \le n \le 10$，单个字符串长度不超过 $100$。数据规模较小，允许 $O(L^2)$ 的暴力解法（$L$ 为字符串长度）。
• 复杂度要求：单串处理复杂度 $O(L^2)$（枚举分割点 $O(L)$，每次回文判断 $O(L)$），总复杂度 $O(n \cdot L^2) \le 10 \times 10^4 = 10^5$，轻松满足时限。
• 算法知识点：回文串判定、字符串枚举、子串提取

思路解析

1. 长度剪枝：若字符串长度小于 $4$，则无法分割为两个长度至少为 $2$ 的子串（$2+2=4$），直接判定为 No。
2. 枚举分割点：设分割位置为 $i$（表示前 $i+1$ 个字符为第一部分），$i$ 的取值范围为 $[1, L-3]$（$L$ 为串长）。此范围确保：
   • 前半部分长度 $i+1 \ge 2$
   • 后半部分长度 $L-(i+1) \ge 2$
3. 回文判定：对每一个分割位置，提取前后两个子串，分别与其反转字符串比较。若两者均为回文（即子串等于其反转），则找到合法拆分，输出 Yes 并提前退出。
4. 终止条件：若枚举完所有可能的分割点均未发现双回文结构，则输出 No。

完整代码

#include <bits/stdc++.h>
using namespace std;

void solve() {
    string s;
    cin >> s;
    // 剪枝：长度小于4无法拆分为两个长度>=2的子串
    if (s.size() < 4) {
        cout << "No" << endl;
        return;
    }
    // 枚举分割点i：s[0..i]为第一部分，s[i+1..end]为第二部分
    // i从1开始保证第一部分长度>=2，i < s.size()-2保证第二部分长度>=2
    for (int i = 1; i < s.size() - 2; i++) {
        string s1 = s.substr(0, i + 1);      // 提取前半段
        string s2 = s.substr(i + 1);         // 提取后半段
        string re_s1 = s1, re_s2 = s2;
        reverse(re_s1.begin(), re_s1.end()); // 反转前半段
        reverse(re_s2.begin(), re_s2.end()); // 反转后半段
        // 关键判断：两部分均为回文串
        if (s1 == re_s1 && s2 == re_s2) {
            cout << "Yes" << endl;
            return;  // 找到即返回，无需继续枚举
        }
    }
    cout << "No" << endl;
}

int main() {
    int t;
    cin >> t;
    while(t--) solve();  // 处理t组数据
    return 0;
}