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

这题怎么没人做呢？NOIP难度的水题 简化一下题意，找一种字典树的DFS序，满足：从根节点开始，经过所有节点，最后到达一个叶节点，且长度最短。 不难发现，只要找出一个最长的字符串，先在其他字符串上走，后走最长的字符串即可。DFS前，在最长的串上一路打标记，在DFS时后走有标记的点，这样可以保证最短。 ``` #include<cstdio> #include<iostream> #include<string> struct Node { int next[26]; bool mark,end; }trie[25000*20]; int cnt; using std::string; string l; void Insert(string s) { int length=s.length(); int u=0; for(int i=0;i<length;++i) { if(!trie[u].next[s[i]-'a']) trie[u].next[s[i]-'a']=++cnt; u=trie[u].next[s[i]-'a']; } trie[u].end=1; } void Mark(string s) { int length=s.length(); int u=0; for(int i=0;i<length;++i) { u=trie[u].next[s[i]-'a']; trie[u].mark=1; } } char opt[1000000]; int m; bool finish; void dfs(int u) { int mark=-1; if(trie[u].end) opt[++m]='P'; for(int i=0;i<26;++i) { if(trie[trie[u].next[i]].mark) mark=i; else if(trie[u].next[i]) { opt[++m]=i+'a'; dfs(trie[u].next[i]); } } if(mark!=-1) { opt[++m]='a'+mark; dfs(trie[u].next[mark]); } if(trie[u].mark&&mark==-1) finish=1; if(!finish) opt[++m]=45; return; } int main() { int n; std::cin>>n; string s; for(int i=0;i<n;++i) { std::cin>>s; Insert(s); if(s.length()>l.length()) l=s; } Mark(l); dfs(0); printf("%d\n",m); for(int i=1;i<=m;++i) { printf("%c\n",opt[i]); } return 0; } ```