[洛谷 4683][IOI2008]Type Printer

题目链接

https://www.luogu.com.cn/problem/P4683

题解

首先建出 Trie 树，容易发现我们的目标是确定一种 DFS 序，使得在遍历所有节点的前提下走过的边数尽可能少。

如果走完最后一个节点要返回根节点的话，那么显然每条边至少要走两次（递归的时候走一次，回溯的时候还要走一次）。

在本题中，我们走完最后一个节点后就不需要返回了。这意味着我们可以少走从最后一个点到根的这些边。

怎样让少走的边尽可能多呢？显然只需让最深的节点最后走到即可。

于是我们可以按这样的方式进行 DFS：先找出每个节点深度最深的子树，每次 DFS 先走完其他子树，再遍历最深的子树即可。

#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;
}