题解 P4683 【[IOI2008] Type Printer 打印机】
StudyingFather
2019-11-28 20:24:28
首先建出 Trie 树，容易发现我们的目标是确定一种 DFS 序，使得在遍历所有节点的前提下走过的边数尽可能少。
如果走完最后一个节点要返回根节点的话，那么显然每条边至少要走两次（递归的时候走一次，回溯的时候还要走一次）。
在本题中，我们走完最后一个节点后就不需要返回了。这意味着我们可以少走从最后一个点到根的这些边。
怎样让少走的边尽可能多呢？显然只需让最深的节点最后走到即可。
于是我们可以按这样的方式进行 DFS：先找出每个节点深度最深的子树，每次 DFS 先走完其他子树，再遍历最深的子树即可。
```cpp
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int sig=26;
char res[1000005];
int ans;
struct trie
{
struct node
{
int son[sig],end,ls,dep,maxd;
}tr[500005];
int cnt;
void insert(char* s)
{
int u=0;
for(int i=0;s[i];i++)
{
int &v=tr[u].son[s[i]-'a'];
if(!v)v=++cnt;
u=v;
}
tr[u].end=1;
}
void dfs1(int u,int fa)
{
tr[u].maxd=tr[u].dep=tr[fa].dep+1;
tr[u].ls=-1;
for(int i=0;i<sig;i++)
{
int v=tr[u].son[i];
if(v)
{
dfs1(v,u);
if(tr[v].maxd>tr[u].maxd)
{
tr[u].maxd=tr[v].maxd;
tr[u].ls=i;
}
}
}
}
void dfs2(int u)
{
if(tr[u].end)res[++ans]='P';
int ls=tr[u].ls;
for(int i=0;i<sig;i++)
{
int v=tr[u].son[i];
if(v&&i!=ls)
{
res[++ans]='a'+i;
dfs2(v);
}
}
if(ls!=-1)
{
res[++ans]='a'+ls;
dfs2(tr[u].son[ls]);
}
res[++ans]='-';
}
}t;
char s[25];
int main()
{
int n;
scanf("%d",&n);
int maxl=0;
for(int i=1;i<=n;i++)
{
scanf("%s",s);
maxl=max(maxl,(int)strlen(s));
t.insert(s);
}
t.dfs1(0,0);
t.dfs2(0);
ans-=maxl+1;//排除走完最后一个点的回溯过程
printf("%d\n",ans);
for(int i=1;i<=ans;i++)
printf("%c\n",res[i]);
return 0;
}
```