f462 - Shortst Names
題目描述
題目要求計算在一個村莊中，如果每個人都使用最短的前綴來稱呼其他人（包括自己），總共需要多少個字元。村莊中每個人的名字都不會是其他人的名字的前綴。
解題思路
本題的核心思想是利用 Trie 樹來儲存所有的人名。Trie 樹的每個節點代表一個字元，從根節點到葉子節點的路徑代表一個完整的人名。
在建立 Trie 樹後，我們需要找到每個名字的最短唯一前綴。這意味著找到一個前綴，使得 Trie 樹中只有一個名字以該前綴開頭。我們可以通過深度優先搜尋 (DFS) 來遍歷 Trie 樹，並檢查每個節點的子樹大小。如果一個節點的子樹大小為 1，則該節點對應的前綴就是該名字的最短唯一前綴。
最後，將所有名字的最短唯一前綴的長度加總，即可得到所需的總字元數。
複雜度分析
- 時間複雜度: O(N * M)，其中 N 是人名數量，M 是人名的平均長度。建立 Trie 樹需要 O(N * M) 的時間，DFS 遍歷 Trie 樹也需要 O(N * M) 的時間。
- 空間複雜度: O(N * M)，Trie 樹的空間複雜度取決於人名的總長度。在最壞的情況下，所有的人名都不同，則需要儲存所有字元。
程式碼
#include <iostream>
using namespace std;
struct trie{
trie* nxt[26];
int cnt = 0;
int sz = 0;
};
trie* root = new trie();
int t,n,ans;
string s;
void insert(string s){
trie* now=root;
for(int i=0;i<s.length();++i){
now->sz++;
if(now->nxt[s[i]-'a']==nullptr){
now->nxt[s[i]-'a'] = new trie();
}
now = now->nxt[s[i]-'a'];
}
now->sz++;
now->cnt++;
}
void dfs(trie* now,int it){
if(now->sz==1&&it!=0){
ans+=it;
return;
}
for(int i=0;i<26;++i){
if(now->nxt[i]!=nullptr){
dfs(now->nxt[i],it+1);
}
}
return;
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> t;
while(t--){
cin >> n;
root = new trie();
for(int i=0;i<n;++i){
cin >> s;
insert(s);
}
ans=0;
dfs(root,0);
cout << ans << "\n";
}
}