題目鏈接：點擊查看

題目大意：給出n個學生的真實姓名和n個假名，問怎樣匹配能使lcp總和最大，lcp是指最大相同前綴長度

題目分析：這個題一開始是沒有思路的，但看到前綴并且數據還這么大，肯定是和字典樹脫不了干系的，但最后還是沒有合適的想法來解決這個問題，看了一下zx學長的代碼后就明白了，一種類似于貪心的策略，讓前綴盡可能長的字符串先匹配，那我們該如何用字典樹實現呢？關于字典樹的每個節點，我們可以多存儲一點信息，那就是能夠到達當前節點的字符串的編號，用vector就可以搞定，有了這樣一個信息，在建完樹后，因為字典樹也是樹狀結構，所以我們可以用dfs或bfs進行遍歷，這個題目因為需要回溯，所以我們選擇使用dfs進行遍歷，先跑到樹的最深層，也就是葉子結點，這個時候若名字和假名的id可以匹配的話，那肯定是最優解，因為此時的前綴序列最長，我們就遍歷一遍當前節點下所有的名字序號和假名序號，讓他們一一匹配即可，記得用布爾數組vis輔助標記，防止二次匹配，當前深度的所有節點匹配完畢后，就可以回溯到上一層去了，也算是一種貪心的策略

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e6+100;char s[N];vector<int>a[N],b[N];int trie[N][26];int cnt=0;bool visa[N],visb[N];int sum=0;vector<pair<int,int>>ans;void insert(vector<int> a[],int id) {int pos=0;a[pos].push_back(id);for(int i=0;s[i];i++){int to=s[i]-'a';if(!trie[pos][to])trie[pos][to]=++cnt;pos=trie[pos][to];a[pos].push_back(id);} }void dfs(int pos,int deep) {for(int i=0;i<26;i++)if(trie[pos][i])dfs(trie[pos][i],deep+1);for(int i=0;i<a[pos].size();i++){if(visa[a[pos][i]])continue;for(int j=0;j<b[pos].size();j++){if(visb[b[pos][j]])continue;visa[a[pos][i]]=visb[b[pos][j]]=true;sum+=deep;ans.push_back(make_pair(a[pos][i],b[pos][j])); break;}} }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int n;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%s",s);insert(a,i);}for(int i=1;i<=n;i++){scanf("%s",s);insert(b,i);}dfs(0,0);printf("%d\n",sum);for(int i=0;i<ans.size();i++)printf("%d %d\n",ans[i].first,ans[i].second);return 0; }

?

總結

以上是生活随笔為你收集整理的CodeForces - 566A Matching Names(字典树上贪心)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。