B4039 [GESP202409 三级] 回文拼接 题解

ClV_Csy · 2024-11-10 18:59:27 · 题解

B4039 [GESP202409 三级] 回文拼接

题意

输入 n 个字符串，判断它们是否能分解为两个长度大于等于 2 的回文串。

思路

下文中提到的 a 表示原字符串，x_1 表示分解后的第一个子串，x_2 表示分解后的第二个子串。

考虑枚举每一个可能的回文串断点 [0,a\text{.size()}-1]（即两个回文串之间的下标）。很容易写出以下代码。

for (int j = 0; j <= a.size() - 1; j++) { //枚举断点从0到a.size() - 1 
    string x1, x2; //两个分割开的字符串
    for (int k = 0; k < j; k++) {
        x1 += a[k];
    }
    for (int k = j; k <= a.size() - 1; k++) {
        x2 += a[k];
    }
}

又需要分解成两个长度大于等于 2 的字符串，可以将断点枚举的范围缩小到 [2,a.\text{size()}-2]，其中的原因是：当 a.\text{size()}\ge4 时，即使断点为最小的 2 或最大的 a\text{.size()}-2，x_1\text{.size(),}x2\text{.size()} 也都大于等于 2。
还有几个特例：当 a\text{.size()}<4 时是不可能分解出 2 个长度大于等于 2 的子串的，所以这种情况不用枚举，直接输出"No"。
注：当 a\text{.size()}=1 时会RE。本蒟蒻太菜，不知道为什么。

所以可以将代码优化为如下代码。

for (int j = 2; j <= a.size() - 2; j++) { //枚举断点从2到a.size() - 2 
    string x1, x2; //两个分割开的字符串
    for (int k = 0; k < j; k++) {
        x1 += a[k];
    }
    for (int k = j; k <= a.size() - 1; k++) {
        x2 += a[k];
    }
}

最后再写一个判断回文串的函数就可以了。

bool is(string a) {
    string b;
    for (int i = a.size() - 1; i >= 0; i--) {
        b += a[i];
    }
    return (a == b);
}

当然以下代码也可以。

#include <algorithm>
bool is(string a) {
    string b = a;
    reverse(a.begin(), a.end());
    return (a == b);
}

代码

#include <iostream>
using namespace std;
bool is(string a) {
    string b;
    for (int i = a.size() - 1; i >= 0; i--) {
        b += a[i];
    }
    return (a == b);
}
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        string a;
        cin >> a;
        bool flag = 0;
        if (a.size() <= 3) {
            cout << "No\n";
            continue;
        }
        for (int j = 2; j <= a.size() - 2; j++) { //枚举断点 
            string x1, x2;
            for (int k = 0; k < j; k++) {
                x1 += a[k];
            }
            for (int k = j; k <= a.size() - 1; k++) {
                x2 += a[k];
            }
            if (is(x1) && is(x2)) {
                flag = 1;
            }
        }
        if (flag == 0) {
            cout << "No\n";
        }
        else {
            cout << "Yes\n";
        }
    }
    return 0;
}