题解：P12171 [蓝桥杯 2025 省 Python B] 最长字符串

__Accepted_cyx__ · 2025-12-14 21:20:44 · 题解

P12171 [蓝桥杯 2025 省 Python B] 最长字符串 题解

思路

• 我们可以将问题抽象为：

从长度为 1 的“种子”开始，按照规则“生长”出更长的字符串。关键在于，判断一个长字符串是否优美，只取决于是否存在一个比它短 1 的优美字符串，且两者的字母组成（忽略顺序）存在特定的包含关系。

• 具体步骤

1. 首先读取所有单词，并按长度进行分组。处理时必须从短到长依次处理，因为长字符串的状态依赖于短字符串的状态。

2. 将每个字符串的字母组成（即各字母的出现频次，或排序后的字符串）定义为一个状态。一个字符串是优美的，等价于它的这个状态是可达的。

3. 初始化：将所有长度为 1 的单词标记为优美字符串，并将其对应的状态加入“已确认优美”的状态集合中。

4. 递推过程（状态转移）：

• 对于长度为 len （len \ge 1） 的每个候选单词 s。

• 计算它去掉最后一个字符后剩余部分的字母组成状态 ps 。

• 检查 ps 是否存在于“已确认优美”的状态集合中。

• 如果存在，则说明 s 可以根据规则从一个优美的较短字符串扩展而来，因此 s 自身也是优美的。将 s 自身的状态也加入优美状态集合。

5. 在整个递推过程中，记录所有被标记为优美的字符串。最后，从中找出长度最大的；若长度相同，则选择字典序最小的作为答案。

代码

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

int main() {
    ifstream f("words.txt");
    vector<string> w;
    string s;

    while(getline(f, s)) w.push_back(s);

    sort(w.begin(), w.end(), [](string& a, string& b) {
        if(a.size() != b.size()) return a.size() < b.size();
        return a < b;
    });

    unordered_map<string, string> dp;
    int mx = 0;
    string ans = "";

    for(auto& t : w) {
        if(t.size() == 1) {
            string st = t;
            sort(st.begin(), st.end());
            dp[st] = t;

            if(t.size() > mx || (t.size() == mx && t < ans)) {
                mx = t.size();
                ans = t;
            }
        }
    }

    for(auto& t : w) {
        if(t.size() < 2) continue;

        string ps = t.substr(0, t.size() - 1);
        sort(ps.begin(), ps.end());

        if(dp.count(ps)) {
            string cs = t;
            sort(cs.begin(), cs.end());

            if(!dp.count(cs) || t < dp[cs]) {
                dp[cs] = t;
            }

            if(t.size() > mx || (t.size() == mx && t < ans)) {
                mx = t.size();
                ans = t;
            }
        }
    }

    cout << ans;
    return 0;
}

实际上：

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

int main(){
    cout<<"afplcu";
    return 0;
} 

:::info[声明]{open} 本文使用了 AI 润色。 :::