P4683 详解

Lovely_Elaina · 2023-01-31 21:11:18 · 题解

前言

第一眼看到题目，~~活字印刷术？~~

其实就是给你一个~~很恶心的~~打印机，共有三种操作：

在当前词的尾部添加一个字母；
在当前次的尾部减去一个字母（至少有一个字母时）；
打印当前词。

其次，有三个注意点：

添加一个字母，用这个小写字母的自身来表示；
删去一个字母，用减号表示；
打印单词时，用 P 表示。

特别的：

所有单词都不相同；
打印结束时，允许有部分字母留在打印机内；
允许按照任意的次序打印单词。

说句题外话：这打印机谁造的。

下面的看懂了题目再来看。

思路

我们使用字典树来完成。

首先，有一个点大大的降低了题目难度，就是 打印结束时，允许有部分字母留在打印机内。

众所周知，字典树很好地利用了字符串的公共前缀，这也就是上一行出现的原因。

如果我们想要操作数尽可能少，那我们的删除数的操作就要尽可能的少。

我们来模拟一下（敲黑板）。

注：为了方便观察，我改了自己造的样例的顺序。

输入：
8
abcd
abcdef
dfg
dfgr
dgrt
plwoe
plwpo
plwpoq

构建出来的树数这样的：

~~粉色，够温馨吧。~~

虽然图画的有点丑，将就看吧。

让我们看回到上面那句话：

如果我们想要操作数尽可能少，那我们的删除数的操作就要尽可能的少。

怎么样，看出字典树的特征了吧。

先讲怎么遍历。

我们以中间那一坨为例：

先遍历 d，然后开始搜索所有子树；
发现了 f，继续往下搜索；
遇到了 g，发现是一个单词结尾，输出，还有子树，继续往下；
遇到了 r，发现是一个单词结尾，输出，发现没了，停止。

啧，是回溯。

我们要删到可以继续搜，也就是说我们的 dfs 大概是这样的：

for(int i = 0; i < 26; i++){
  if(存在该子节点 && 还有一个，下面会说){
    要输出的字符串 += 该子节点;
    dfs(该子节点);
    要输出的字符串 += '-';
  }
}

好耶。

但是这个时候有人要问了，不应该先遍历更短的子树吗？这不是删除数量更少吗？

对，这就是另外一个重点。

在输入时，我们存下最长的字符串，然后给该字符串在树中打标记。

以这个为例，我们可以发现如果想要删得更少，刚刚好 plwpoe 这一条不用删。

其余的所有字母都是必删的。

而 plwpoe 这一条是输入中最长的。

嘿嘿，懂了吗。

我们在输入的时候记下最长的，事后标记一下，优先遍历没有标记的，这样删的次数最少。

标记的函数也很简单。

void mark(string s){
  int p = 0; // 当前遍历的子树的根
  for(int i = 0; s[i]; i++){ //遍历，字符串 s 必存在
    int x = s[i] - 'a';
    tick[p][x] = 1; // 标记
    p = tree[p][x]; // 下一个
  }
}

代码

插入：

inline void insert(string s)
{
    int p = 0;
    for (int i = 0; s[i]; i++) {
        int x = s[i] - 'a';
        if (!tree[p][x])
            tree[p][x] = ++ind; // 建点
        le[tree[p][x]] = x + 'a'; // 记录
        p = tree[p][x];
    }
    en[p] = 1; //标记结尾
}

标记最长：

inline void mark(string s)
{
    int p = 0;
    for (int i = 0; s[i]; i++) {
        int x = s[i] - 'a';
        k[tree[p][x]] = 1;
        p = tree[p][x];
    }
}

dfs：

inline void dfs(int x)
{
    if (en[x] == 1 && x != 0) {
        ans++;
        output += "P";
    }

    if (ans == n) {
        cout << output.size() << endl;
        for (int i = 0; output[i]; i++)
            cout << output[i] << endl;
        return;
    }

    int reg;
    for (int i = 0; i < 26; i++) {
        reg = tree[x][i];
        if (k[reg] == 0 && reg != 0) {
            output += le[reg];
            dfs(reg);
            output += "-";
        }
    }

    for (int i = 0; i < 26; i++) {
        reg = tree[x][i];
        if (k[reg] && reg) {
            output += le[reg];
            dfs(reg);
            output += "-";
        }
    }
}

其实我格式化了代码，但是原码风挺正常的。

完整代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;

bool en[N]; // 结尾
bool k[N]; // 标记
char le[N]; // 记录树的几号节点为什么
int tree[N][26];

int n, m, ind, ans;
string s, output, l;

inline void insert(string s)
{
    int p = 0;
    for (int i = 0; s[i]; i++) {
        int x = s[i] - 'a';
        if (!tree[p][x])
            tree[p][x] = ++ind; // 建点
        le[tree[p][x]] = x + 'a'; // 记录
        p = tree[p][x];
    }
    en[p] = 1; //标记结尾
}

inline void mark(string s)
{
    int p = 0;
    for (int i = 0; s[i]; i++) {
        int x = s[i] - 'a';
        k[tree[p][x]] = 1;
        p = tree[p][x];
    }
}

inline void dfs(int x)
{
    if (en[x] == 1 && x != 0) {
        ans++;
        output += "P";
    }

    if (ans == n) {
        cout << output.size() << endl;
        for (int i = 0; output[i]; i++)
            cout << output[i] << endl;
        return;
    }

    int reg;
    for (int i = 0; i < 26; i++) {
        reg = tree[x][i];
        if (k[reg] == 0 && reg != 0) {
            output += le[reg];
            dfs(reg);
            output += "-";
        }
    }

    for (int i = 0; i < 26; i++) {
        reg = tree[x][i];
        if (k[reg] && reg) {
            output += le[reg];
            dfs(reg);
            output += "-";
        }
    }
}

int main()
{

    cin >> n;
    getchar();
    for (int i = 1; i <= n; i++) {
        cin >> s;
        insert(s);
        if (l.size() < s.size())
            l = s;
    }

    mark(l);
    dfs(0);

    return 0;
}

说两句题外话：

我一开始一边插入一边标记；
大写打成了小写。

没人像我这样吧（小声）。