跳至正文

1 条题解

  • 0
    @ 2026-10-2 2:22:35

    只使用实际出现的字母,比较相邻单词的第一个不同字符建立去重的有向边;检查错误前缀和矛盾环。每一步恰好一个入度0字母才能唯一还原,重复单词和重复约束不重复计数。

    #include <bits/stdc++.h>
    using namespace std;
    
    int main(){ios::sync_with_stdio(false);cin.tie(nullptr);
    
    int n;cin>>n;vector<string>words(n);array<bool,26>present{};for(string&s:words){cin>>s;for(char c:s)present[c-'a']=true;}string target;cin>>target;for(char c:target)present[c-'a']=true;bool g[26][26]={};int degree[26]={};for(int i=0;i+1<n;i++){size_t k=0;while(k<words[i].size()&&k<words[i+1].size()&&words[i][k]==words[i+1][k])k++;if(k==min(words[i].size(),words[i+1].size())){if(words[i].size()>words[i+1].size()){cout<<"0\n";return 0;}}else{int a=words[i][k]-'a',b=words[i+1][k]-'a';if(!g[a][b]){g[a][b]=true;degree[b]++;}}}vector<int>order;while(order.size()<count(present.begin(),present.end(),true)){int u=-1,candidates=0;for(int i=0;i<26;i++)if(present[i]&&degree[i]==0){u=i;candidates++;}if(candidates!=1){cout<<"0\n";return 0;}degree[u]=-1;order.push_back(u);for(int v=0;v<26;v++)if(g[u][v])degree[v]--;}char map[26]={};for(size_t i=0;i<order.size();i++)map[order[i]]='a'+i;for(char c:target)cout<<map[c-'a'];cout<<"\n";
    
    return 0;
    }
    
    • 1

    信息

    ID
    4071
    时间
    1000ms
    内存
    128MiB
    难度
    5
    标签
    递交数
    0
    已通过
    0
    上传者