题解：P13670 [GCPC 2023] Eszett

pxyjjyyds · 2025-08-09 11:05:55 · 题解

P13670 [GCPC 2023] Eszett 题解

原题链接

（1）题目分析：

此题的问题是对输入的大写字符串进行转换，规则如下：

• 大写字符串中的两个连续的 ‘S’ 转换为两个小写 ‘B’ ；
• 大写字符串中的两个连续的 ‘S’ 转换为两个小写 ‘s’ ；
• 将为转换的大写字母转为小写；

  （2）核心思路：

  1. 通过递归生成连续含 ‘S’ 段的所有可能分解；
  2. 处理每个分块的转化结果；
  3. 组合所以分块可能性生成结果；

     （3）完整代码实现：

AC记录

#include <iostream>
#include <vector>
#include <cctype>
using namespace std;
vector<string> g(int n) {
    if (n == 0) return {""};
    if (n == 1) return {"s"};

    vector<string> result;
    for (const auto& seq : g(n - 1)) {
        result.push_back("s" + seq);
    }
    for (const auto& seq : g(n - 2)) {
        result.push_back("B" + seq);
    }
    return result;
}

int main() {
    string input;
    cin >> input; 
    vector<string> tokens;
    for (int i = 0; i < input.size();) {
        if (input[i] == 'S') {
            int j = i;
            while (j < input.size() && input[j] == 'S') j++;
            tokens.push_back(input.substr(i, j - i));
            i = j;
        } else {
            int j = i;
            while (j < input.size() && input[j] != 'S') j++;
            tokens.push_back(input.substr(i, j - i));
            i = j;
        }
    }
    vector<vector<string>> pos;
    for (const auto& token : tokens) {
        if (token.find('S') == string::npos) {
            string lowerToken;
            for (char c : token) {
                lowerToken += tolower(c); 
            }
            pos.push_back({lowerToken});
        } else {
            pos.push_back(g(token.size()));
        }
    }
    vector<string> results = {""};
    for (const auto& block : pos) {
        vector<string> ne;
        for (const auto& res : results) {
            for (const auto& seq : block) {
                ne.push_back(res + seq);
            }
        }
        results = move(ne);
    }
    for (const auto& res : results) {
        cout << res << endl;
    }
    return 0;
}

完结，点个赞吧！