题解 P4683 【[IOI2008] Type Printer 打印机】
whyl
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;
}
```
求管理大大放过。。。。