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

whyl

2019-09-28 11:28:55

Solution

发我的第一篇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; } ``` 求管理大大放过。。。。