老式打印机(Type Printer) 题解

思路分析

按题目要求使用对应数据结构与算法模拟/递推求解，注意数据范围边界与时间复杂度。

参考代码

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

struct Node {
    int ch[26];
    int max_dep;
    int heavy;
    bool is_end;
    Node() {
        fill(begin(ch), end(ch), 0);
        max_dep = 0;
        heavy = -1;
        is_end = false;
    }
};

vector<Node> tr;
vector<char> ops;

void prep(int u) {
    tr[u].max_dep = 0;
    tr[u].heavy = -1;
    for (int c = 0; c < 26; ++c) {
        int v = tr[u].ch[c];
        if (!v) continue;
        prep(v);
        if (tr[v].max_dep + 1 > tr[u].max_dep) {
            tr[u].max_dep = tr[v].max_dep + 1;
            tr[u].heavy = c;
        }
    }
}

void dfs(int u) {
    if (tr[u].is_end) ops.push_back('P');
    for (int c = 0; c < 26; ++c) {
        if (c == tr[u].heavy) continue;
        int v = tr[u].ch[c];
        if (!v) continue;
        ops.push_back(char('a' + c));
        dfs(v);
        ops.push_back('-');
    }
    if (tr[u].heavy != -1) {
        int c = tr[u].heavy;
        int v = tr[u].ch[c];
        ops.push_back(char('a' + c));
        dfs(v);
        ops.push_back('-');
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    tr.reserve(n * 20 + 5);
    tr.emplace_back();
    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        int u = 0;
        for (char ch : s) {
            int c = ch - 'a';
            if (!tr[u].ch[c]) {
                tr[u].ch[c] = (int)tr.size();
                tr.emplace_back();
            }
            u = tr[u].ch[c];
        }
        tr[u].is_end = true;
    }
    prep(0);
    dfs(0);
    while (!ops.empty() && ops.back() == '-') ops.pop_back();
    cout << ops.size() << "\n";
    for (char c : ops) cout << c << "\n";
    return 0;
}