Hướng dẫn giải của Lặp tên


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Lời giải: Xây trie ~T~ cho các xâu. Với mỗi xâu ta có thể để nguyên hoặc dịch xâu đó lên một node tổ tiên, sao cho không có hai xâu nào kết thúc ở cùng một node. Ta có thuật tham lam như sau: Xét các đỉnh của ~T~ từ lá lên gốc. Nếu đỉnh ~u~ đang không có xâu nào, chọn xâu kết thúc ở đỉnh nằm trong subtree của ~u~ và ở xa gốc nhất để đặt vào ~u~. Nếu có sẵn một xâu kết thúc ở ~u~ rồi thì không làm gì.

Khi xét mỗi node ~u~ ta cần tìm xâu thuộc subtree của ~u~ này và xa gốc nhất nhanh. Để làm vậy ta có thể lưu ~S_u~ là tập các xâu thuộc subtree của ~u~. Ta có thể dùng std::set và kỹ thuật gộp set small-to-large. Thuật này có độ phức tạp ~O(M + N log^2(N))~, trong đó ~M~ là tổng độ dài các xâu. Ngoài ra ta có thể gộp các tập mà không dùng đến kỹ thuật small-to-large với tổng độ phức tạp ~O(M)~, với nhận xét là xâu có độ dài ~len~ sẽ bị di chuyển tối đa ~len~ lần.

Code C++:

#include <bits/stdc++.h>

using namespace std;

#define loop(i, l, r) for(int i = (int) l; i <= (int) r; i++)
#define rloop(i, r, l) for(int i = (int) r; i >= (int) l; i--)

#define sp ' '

const int maxn = 1e5 + 5;

int n;
int g[maxn][26]; int le[maxn]; 
int sum[maxn]; 
int d[maxn]; 
int sz[maxn]; 

multiset<int> s[maxn]; 

int cnt = 0; 
int ans = 0;
void add(string s) {
    int now = 0; 
    for(char c: s) {
        int e = c - 'a'; 
        if(g[now][e] == -1) {
            g[now][e] = ++cnt; 
        }
        now = g[now][e]; 
    }
    le[now] = 1; 
}

void dfs(int i) {
    if(le[i]) {
        sz[i] = 1; 
        s[i].insert(d[i]);
    }
    for(int j: g[i]) {
        if(j != -1) {
            d[j] = d[i] + 1; 
            dfs(j); 
            sz[i] += sz[j]; 
            sum[i] += sum[j] + sz[j]; 
            if(s[i].size() < s[j].size()) s[i].swap(s[j]); 
            for(int d: s[j]) {
                s[i].insert(d); 
            }
            s[j].clear(); 
        }
    }
    if(!le[i] and s[i].size() and i > 0) {
        auto it = prev(s[i].end()); 
        sum[i] -= *it - d[i]; 
        s[i].erase(it); 
        s[i].insert(d[i]); 
    }
}


signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n; 
    loop(i, 0, maxn - 1) {
        fill(begin(g[i]), end(g[i]), -1); 
    }
    loop(i, 1, n) {
        string s; 
        cin >> s; 
        add(s); 
    }
    dfs(0); 
    cout << sum[0]; 
}

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.