题解 P4683 【[IOI2008] Type Printer 打印机】

2019-09-28 11:28:55


发我的第一篇IOI的题解

本题容易想到最后保留的肯定是一条链

并且能够print的,能早print一定比晚print要优

所以只用一遍dfs先dfs不是最长链上的

边做边输出即可

//code by luotc
#include<bits/stdc++.h>

using namespace std;

const int maxn=500005;

int n,ed[maxn],lenth[25005],td,mx,tot,ans,last;
int ch[500005][26],belong[maxn];
string s[25005];

inline void insert(string s){
    int len=s.length(),now=0;
    for(int i=0;i<len;i++){
        int t=s[i]-'a';
        if(!ch[now][t]) ch[now][t]=++tot;
        now=ch[now][t];
    }
    ed[now]=1;
}

inline void modify(string s){
    int len=s.length(),now=0;
    for(int i=0;i<len;i++){
        int t=s[i]-'a';
        if(!ch[now][t]) ch[now][t]=++tot;
        now=ch[now][t];
        belong[now]=1;
    }
    ed[now]=1;
    last=now;
}

inline void dfs(int x){
    if(ed[x]) printf("P\n");
    if(x==last) return;
    for(int i=0;i<=25;i++){
        if(ch[x][i]){
            if(belong[ch[x][i]]) continue;
            printf("%c\n",i+'a');
            dfs(ch[x][i]);
            printf("-\n");
        }
    }
    for(int i=0;i<=25;i++){
        if(belong[ch[x][i]]){
            printf("%c\n",i+'a');
            dfs(ch[x][i]);
        }
    }
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        lenth[i]=s[i].length();
        if(mx<lenth[i]){
            td=i;
            mx=lenth[i];
        }
    }
    for(int i=1;i<=n;i++){
        if(i==td){
            modify(s[i]);
            continue;
        }
        insert(s[i]);
    }
    cout<<tot*2+n-mx<<endl;
    dfs(0);
    return 0;
}

求管理大大放过。。。。