题解：CF777D Cloud of Hashtags

Cybrex · 2025-09-02 19:31:32 · 题解

怎么没人写字典树？我来补一篇。

发现要使字符串序列字符串序列最小，则对于两个相邻的字符串 s_i，s_j，s_{i,k}\le s_{j,k}，不难发现用字典树倒序插入是好维护的，只需在字典树上每遍历到一个节点，判断是否本节点下一层已存在比当前字符字典序更小的字符即可。

发现难以处理字符串长度不一的情况，这时我们只需标记字符串结尾为一个独立节点，使其小于所有字符，每次额外判断即可。

复杂度 O(n\times26)，n 为字符串总长度。

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N=5e5+10;
int t[N][30];
int cnt;
string ans[N];
void ins(string s,int xx){
    int u=0;
    int w=-1;
    for(int i=0;i<s.size()-1;i++){
        int x=s[i]-'a'+1;
        bool mx=0;
        for(int j=x-1;j>=0;j--){
            if(t[u][j]){
                mx=1;break; 
            }
        }
        if(mx){
            break;
        }
        if(!t[u][x]){
            t[u][x]=++cnt;
        }
        u=t[u][x];
        w=i;
    }
    t[u][0]=++cnt;
    ans[xx]='#';
    for(int i=0;i<=w;i++){
        ans[xx]+=s[i];
    }
} 
string S[N];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        string s;cin>>s;
        for(int i=0;i<s.size();i++){
            s[i]=s[i+1];
        }
        S[i]=s;
    }
    for(int i=n;i>=1;i--){
        ins(S[i],i);
    }
    for(int i=1;i<=n;i++){
        cout<<ans[i]<<endl;
    }
    return 0;
}