Hướng giải của Trò chơi "Tạo xâu"

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tóm tắt

Hãy chia tập hợp các chuỗi đã cho thành các nhóm sao cho mỗi nhóm gồm hai chuỗi mà một chuỗi là tiền tố (hoặc toàn bộ) của chuỗi còn lại. Nhận thấy rằng bài toán này mang tính chất tiền tố, do đó chúng ta có thể sử dụng cấu trúc cây Trie để giải quyết.

Áp dụng cây Trie vào bài toán:

Chúng ta có thể thực hiện theo các bước sau:

Xây dựng cây Trie:

Đầu tiên, đưa tất cả các chuỗi vào cây Trie. Trong quá trình này, chúng ta lưu lại các cạnh của cây Trie bằng danh sách kề và đánh dấu các đỉnh kết thúc của mỗi chuỗi. Mỗi đỉnh trong cây Trie sẽ lưu chỉ số của chuỗi kết thúc tại đỉnh đó.
Duyệt cây Trie (DFS): Vì đề bài đảm bảo luôn có kết quả, chúng ta sẽ thực hiện duyệt cây Trie theo thuật toán DFS từ gốc. Tại mỗi đỉnh, đẩy (push) các chỉ số của những chuỗi kết thúc tại đỉnh này vào một stack. Khi duyệt đến nút lá, chúng ta xuất ra (pop) các chỉ số từ stack theo từng cặp, và đó sẽ là kết quả cuối cùng.

Click để xem code

/*Code by Hoang Thai*/
#include <bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
#define sz(a) a.size()
#define cell(a, i, j) a.cell[i][j]
#define ll long long
#define fto(i, a, b) for (int i = a; i <= b; ++i)
#define fdto(i, a, b) for (int i = a; i >= b; --i)
#define BIT(x, i) (((x) >> (i)) & 1)
#define MASK(i) (1LL << (i))
#define mem(x, a) memset(x, a, sizeof x)
#define rem(a, x) a.resize(x+1);
#define open(a) freopen(a".INP", "r", stdin); freopen(a".OUT", "w", stdout);
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;
const int oo = 1000000007;
const int maxN = 100005;
int n;
struct Node {
    Node *child[26];
    int exists, prefix, used;
    vector<int> pos;
    Node() {
        exists = prefix = used = 0;
        fto(i, 0, 25) child[i] = NULL;
    }
};

struct Trie {
    Node *root;
    vector<int> st;
    vector<Node*> own;
    Trie(int len) {
        root = new Node();
        own.resize(len);
    }
    void insert(const string &s, const int &x) {
        Node *p = root;
        for (char c : s) {
            if (p -> child[c - 'a'] == NULL) p -> child[c - 'a'] = new Node();
            p = p -> child[c - 'a'];
            p -> prefix++;
        }
        (p -> pos).pb(x);
        p -> exists++;
        own[x] = p;
    }
    void dfs(Node *p) {
        while (!(p -> pos.empty())) {
            st.pb(p -> pos.back());
            p->pos.pop_back();
        }
        fto(i, 0, 25) {
            if (p -> child[i] != NULL) dfs(p -> child[i]);
        }
        while (sz(st) > 1 && own[st.back()] == p) {
            cout << st.back() << " ";
            st.pop_back();
            cout << st.back() << "\n";
            st.pop_back();
        }
        return;
    }
    void search() {
        dfs(root);
        return;
    }
    void del(Node *p) {
        fto(i, 0, maxN-1) {
            if (p -> child[i] != NULL) del(p -> child[i]);
        }
        delete(p);
    }
    void destroy() {
        del(root);
    }
};

int main() {
    fastio;
    cin >> n;
    Trie str(2*n+1);
    fto(i, 1, 2*n) {
        string s; cin >> s;
        str.insert(s, i);
    }
    str.search();
    return 0;
}

Nhận xét

Không có ý kiến tại thời điểm này.