YZOJ P3385 [校内训练20171201]笔名分配问题
时间限制：1000MS 内存限制：262144KB
难度：\(5.5\)
-
题目描述
班里有 \(n\) 个同学。老师为他们选了 \(n\) 个笔名。现在要把这些笔名分配给每一个同学， 每一个同学分配到一个笔名，每一个笔名必须分配给某个同学。现在定义笔名和真名之间的相关度是他们之间的最长公共前缀。设笔名为 \(a\)，真名为 \(b\)，则他们之间的相关度为 \(lcp(a,b)\)。那么我们就可以得到匹配的质量是每一个同学笔名和真名之间相关度的和。
对于两个字符串 \(a,b\)（从 \(1\) 开始标号），定义 \(a,b\) 的最长公共前缀 \(lcp(a,b)\) 为最大的非负整数 \(k\)，使得 \(k\le |a|, k\le |b|\)，且对所有 \(i=1,2,\ldots,k\)，\(a_i = b_i\) 。
给出一种分配笔名的方案，使得匹配质量最大。
-
输入格式
第 \(1\) 行有 \(1\) 个整数 \(n\)，表示班级中同学的数目。接下来 \(n\) 行，表示每一个同学的真名。最后 \(n\) 行是老师已经安排好的笔名。每行的名称仅由小写字母组成。
-
输出格式
将分配笔名的方案输出到文件中。第一行输出一个数，表示最大匹配质量。接下来 \(n\) 行，每行两个数 \(a,b\)，表示把编号为 \(b\) 的笔名分配给编号为 \(a\) 的同学。同学和笔名均按输入顺序从 \(1\) 至 \(n\) 编号。若方案不唯一，任意输出一种即可。
-
样例输入
|
1 2 3 4 5 6 7 8 9 10 11 |
5 gennady galya boris bill toshik bilbo torin gendalf smaug galadriel |
-
样例输出
|
1 2 3 4 5 6 |
11 4 1 2 5 1 3 5 2 3 4 |
-
数据规模与约定
对于所有测试点，\(n \leq 100000\)，输入串总长 \(\leq 800000\) 。
因为是 \(lcp\) 问题，所以可以考虑Trie树。
初始把所有笔名和真名挂到字符串末尾在Trie树的节点上，挂两个链表分别表示笔名和真名。
这样就会有一种贪心策略：首先DFS其儿子节点，然后两两配对笔名和真名（配对的长度即为其深度）并删去，最后再把不为空的笔名或真名挂给其父亲节点。
dalao的简略证明
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 |
#include <cstdio> #include <cstdlib> #include <cstring> #include <climits> inline void getstr(char s[],int&ls) { register char c=0; while(!(c>='a' && c<='z')) c=getchar(); ls=0; while(c>='a' && c<='z') s[++ls]=c,c=getchar(); s[ls+1]=0; return; } char s[905050]; int cnt,son[801010][27]; int ecnt1,enext1[801010],ends1[801010],elst1[801010],eidx1[801010]; int ecnt2,enext2[801010],ends2[801010],elst2[801010],eidx2[801010]; int tans,ans[105050]; int depth; inline void DFS(register int o) { //printf("%d %d\n",o,depth); depth++; for(register int j=0,s;j<26;j++) if((s=son[o][j])) { //printf("%d --%c--> %d\n",o,j+'a',s), DFS(s); if(ends1[s]) { (elst1[o] ? enext1[elst1[o]]=ends1[s] : ends1[o]=ends1[s]); elst1[o]=elst1[s]; } if(ends2[s]) { (elst2[o] ? enext2[elst2[o]]=ends2[s] : ends2[o]=ends2[s]); elst2[o]=elst2[s]; } } depth--; for(register int j1=ends1[o],j2=ends2[o];j1 && j2;) { tans+=depth,ans[eidx1[j1]]=eidx2[j2]; ends1[o]=j1=enext1[j1],ends2[o]=j2=enext2[j2]; } } int main() { int N;scanf("%d",&N); for(register int i=1;i<=N;i++) { int ls;getstr(s,ls); register int now=0; for(register int j=1,tnow;j<=ls;j++) if(!(tnow=son[now][s[j]-'a']) || !(now=tnow)) now=son[now][s[j]-'a']=++cnt; enext1[++ecnt1]=ends1[now],ends1[now]=ecnt1,eidx1[ecnt1]=i; if(!elst1[now]) elst1[now]=ecnt1; } for(register int i=1;i<=N;i++) { int ls;getstr(s,ls); register int now=0; for(register int j=1,tnow;j<=ls;j++) if(!(tnow=son[now][s[j]-'a']) || !(now=tnow)) now=son[now][s[j]-'a']=++cnt; enext2[++ecnt2]=ends2[now],ends2[now]=ecnt2,eidx2[ecnt2]=i; if(!elst2[now]) elst2[now]=ecnt2; } DFS(0); printf("%d\n",tans); for(register int i=1;i<=N;i++) printf("%d %d\n",i,ans[i]); return 0; } |