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

LotleTos · 2025-10-13 21:06:39 · 题解

长度大于一的优美字符串都得从长度更小的推过来，所以把所有字符串按长度从小到大排序。使用一个集合 s 来存放已知的优美字符串。

接着一个一个遍历：

• 长度等于一的直接加到 s 里。
• 长度大于一的，设它的长度为 l，把长度为 l-1 的前缀单独拉出来按字典序排序，看集合里有没有和排序完的前缀相等的，如果有它就是。
• 长度大于一的是优美字符串的话，看能不能更新答案，然后，把他整个拉出来按字典序排序，加到 s 里。

code

#include<bits/stdc++.h>
using namespace std;
set<string> a;
string s[500010];
bool cmp(string x,string y){
    return x.size()<y.size();
}
int main(){
    string anss;
    int cnt=0;
    int ans=-1;
    while(cin>>s[cnt]){
        if(!s[cnt].empty()){
            cnt++;
        }
    }
    sort(s,s+cnt,cmp);
    for(int i=0;i<cnt;i++){
        if(s[i].empty()){
            continue;
        }
        if(s[i].size()==1){
            a.insert(s[i]);
            continue;
        }
        string s1=s[i];
        s1.erase(s1.size()-1,1);
        sort(s1.begin(),s1.end());
        if(a.find(s1)!=a.end()){
            if(ans<(int)s[i].size()){
                ans=s[i].size();
                anss=s[i];
            }
            if(ans==(int)s[i].size()){
                if(s[i]<anss){
                    anss=s[i];
                }
            }
            sort(s[i].begin(),s[i].end());
            a.insert(s[i]);
        }
    }
    cout<<anss;
}