题目描述
Teachers of one programming summer school decided to make a surprise for the students by giving them names in the style of the “Hobbit” movie. Each student must get a pseudonym maximally similar to his own name. The pseudonym must be a name of some character of the popular saga and now the teachers are busy matching pseudonyms to student names.
There are $n$ students in a summer school. Teachers chose exactly $n$ pseudonyms for them. Each student must get exactly one pseudonym corresponding to him. Let us determine the relevance of a pseudonym $b$ to a student with name $a$ as the length of the largest common prefix $a$ and $b$. We will represent such value as $LCP(a, b)$. Then we can determine the quality of matching of the pseudonyms to students as a sum of relevances of all pseudonyms to the corresponding students.
Find the matching between students and pseudonyms with the maximum quality.
题意概述
给定$2n$个字符串$s_i$,前$n$个为一组,后$n$个为一组。要求将它们建立匹配(不能匹配同一组的字符串),使得两两匹配的字符串的$LCP$的长度之和最大。求最大值及方案。
数据范围:$1 \le n \le 10^5, \; 1 \le \sum |s_i| \le 8 \times 10^5$。
算法分析
首先对所有串建立Trie树,并记录下每个节点是哪些串的前缀。
考虑贪心——在Trie树上DFS(后序遍历),若在一个节点上有未匹配的不同组的串,则直接将它们匹配。这样做的正确性是显而易见的:若它们在之后匹配或与其他串匹配,则一定没有直接匹配更优。
具体实现时可以用vector启发式合并来维护每个节点上的值。
代码
#include <cstdio> #include <vector> #include <cstring> #include <algorithm> int min(int a, int b) { return a < b ? a : b; } static const int N = 800005; int numn = 1, tot; char s[N]; struct Trie { int child[26]; std :: vector <int> rec[2]; } node[N]; std :: vector <std :: pair <int, int> > ans; void insert(char s[], int id, int val) { int len = strlen(s), root = 0; for (int i = 0; i < len; ++ i) { if (! node[root].child[s[i] - 'a']) node[root].child[s[i] - 'a'] = numn ++; root = node[root].child[s[i] - 'a']; } node[root].rec[val].push_back(id); } void merge(std :: vector <int> &a, std :: vector <int> &b) { if (a.size() < b.size()) swap(a, b); a.insert(a.end(), b.begin(), b.end()); } void dfs(int t, int dep) { for (int i = 0; i < 26; ++ i) if (node[t].child[i]) { dfs(node[t].child[i], dep + 1); merge(node[t].rec[0], node[node[t].child[i]].rec[0]); merge(node[t].rec[1], node[node[t].child[i]].rec[1]); } while (! node[t].rec[0].empty() && ! node[t].rec[1].empty()) { tot += dep; ans.push_back(std :: make_pair(node[t].rec[0][node[t].rec[0].size() - 1], node[t].rec[1][node[t].rec[1].size() - 1])); node[t].rec[0].pop_back(), node[t].rec[1].pop_back(); } } int main() { int n; scanf("%d", &n); for (int i = 0; i < n; ++ i) scanf(" %s", s), insert(s, i + 1, 0); for (int i = 0; i < n; ++ i) scanf(" %s", s), insert(s, i + 1, 1); dfs(0, 0); printf("%d\n", tot); for (int i = 0; i < n; ++ i) printf("%d %d\n", ans[i].first, ans[i].second); return 0; }