Hướng dẫn giải của Lặp tên
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