avatar

目录
洛谷 P4683 [IOI2008] Type Printer 打印机

题目相关

题目链接:洛谷 P4683 [IOI2008] Type Printer 打印机

题目描述:

  你需要利用一台可移动的打印机打印出 $N$ 个单词。这种可移动式打印机是一种老式打印机,它需要你将一些小的金属块(每个包含一个字母)放到打印机上以组成单词。然后将这些小金属块压在一张纸上以打印出这个词。这种打印机允许你进行下列操作:

  • 在打印机当前词的末端(尾部)添加一个字母;
  • 在打印机当前词的尾部删去一个字母(将打印机当前词的最后一个字母删去)。仅当打印机当前至少有一个字母时才允许进行该操作;
  • 将打印机上的当前词打印出来。 初始时打印机为空,或者说它不含任何带字母的金属块。打印结束时,允许有部分字母留在打印机内。同时也允许你按照任意的次序打印单词。

  由于每一个操作都需要一定时间,所以需要你尽可能减少所需操作的总数目(将操作的总数最小化)。
  你需要编写一个程序,给定所要打印的 $N$ 个单词,找出以任意次序打印所有单词所需操作的最小数目,并输出一种这样的操作序列。

输入输出格式:

输入格式:

  • 第 $1$ 行包含一个整数 $N$ , 表示你需要打印的单词数。
  • 随后的 $N$ 行中,每一行都包含一个单词。每个词仅由小写字母(‘a’ – ‘z’)组成,而且单词的长度为 $1$ 到 $20$ 个字母(包含 $1$ 和 $20$ 在内)。所有单词都不相同。

输出格式:

  • 第一行包含一个整数 $M$ ,表示打印这 $N$ 个单词所需操作的最小数目。
  • 接下来的 $M$ 行,每行一个字符,表示你的操作序列,序列的描述方法如下:
  • 添加一个字母,用这个小写字母的自身来表示。
  • 删去一个字母,用 $-$ 表示(减号,ASCII 45)。
  • 打印单词,用 $P$ 表示(大写字母P)。

输入输出样例:

输入#1 输出#1
3
print
the
poem
20
t
h
e
P
-
-
-
p
o
e
m
P
-
-
-
r
i
n
t
P

说明:

  • 对于40分的数据,$n\leq18$ 。
  • 对于所有数据,$1\leq N\leq25000$。

博主乱搞

蒟蒻解析:

  按照正常思路,能节省操作数的一个好方式就是增加重复的地方。对此我们可以踹树(Trie字典树)来寻找字符与字符的重合关系。
  我们先抛开最后可以不用全弹完的步骤,寻找一个最短的方案。
  通过随便想想我们可以想到:最好不要重复,即关于每个点只有两个操作:向子节点下面的输出相对应字符以及返回时的输出‘-’。怎么保证一个节点操作不超过两次?只要保证遍历其他子树前正在遍历的子树全部被遍历完即可。(否则还要从其他子树回来,必定走曾经走过的路径)。
  这样子会发现很多方法,因为遍历子树的顺序不同而不同。但结果是相同的。
  回到要求:最后一个打完的单词不必弹出:那我们就让最长的字符串打完之后不必返回即可。即减去最长字符串返回根节点的步骤。所以我们先把不在最长字符串Trie上的单词打完,最后处理这个最长的即可。
  最后提醒一句,不要在空间上开的放飞自我。。。。。。

蒟蒻代码:

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
#define ll long long
#define il inline
struct node{
int son[26],isword,marked;
}tree[25000*25+10];
int root,tot;
int n;
char s[25010][25];
int max_id=0,max_num=0;
vector<char> ans;
bool over=false;
int create(){
++tot;
memset(tree[tot].son,-1,sizeof(tree[tot].son));
tree[tot].isword=tree[tot].marked=0;
return tot;
}
void add(int x){
int cur=root,len=strlen(s[x]);
int i;
for (i=0;i<len;++i){
if (tree[cur].son[s[x][i]-'a']==-1){
tree[cur].son[s[x][i]-'a']=create();
}
cur=tree[cur].son[s[x][i]-'a'];
}
tree[cur].isword=1;
}
void mark_longest(){
int cur=root;
for (int i=0;i<max_num;++i){
cur=tree[cur].son[s[max_id][i]-'a'];
tree[cur].marked=1;
}
}
void dfs(int x){
if (tree[x].isword){
ans.push_back('P');
}
int ismark=-1;
for (int i=0;i<26;++i){
if (tree[x].son[i]==-1) continue;
int cur=tree[x].son[i];
if (!tree[cur].marked){
ans.push_back('a'+i);
dfs(cur);
}else{
ismark=i;
}
}
if (ismark!=-1){
ans.push_back('a'+ismark);
dfs(tree[x].son[ismark]);
}
if (ismark==-1&&tree[x].marked) over=true;
if (!over) ans.push_back('-');
}
int main(){
scanf("%d",&n); root=create();
for (int i=1;i<=n;++i){
scanf("%s",s[i]); add(i);
if (strlen(s[i])>max_num){
max_num=strlen(s[i]); max_id=i;
}
}
mark_longest(); dfs(root);
printf("%d\n",ans.size());
for (int i=0;i<ans.size();++i){
printf("%c\n",ans[i]);
}
return 0;
}
文章作者: lonlyn
文章链接: https://lonlyn.gitee.io/blog/2019/12/19/luoguP4683/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 lonlyn's blog

评论