CodeForces - 566A Matching Names(字典树上贪心)

题目链接：点击查看

题目大意：给出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(字典树上贪心)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。