题解：CF566A Matching Names

· · 题解

题意

有 n 名同学，每位同学有一个真名与一个笔名，都是一个由小写英文字母组成的字符串。每位同学可以选择一位同学，使自己的真名与那位同学的笔名相匹配，产生的贡献为其最长公共前缀，每位同学的笔名只能与一人匹配，求贡献总和的最大值。

思路

把笔名插入字典树，并在每个结束点 i 打上标记，标记位置 i 到根组成的字符串是某个同学的笔名。

然后枚举每个人的真名，找字典树中所有笔名中的最长公共前缀，在最长前缀的末尾 i 打上标记，标记位置 i 到根组成的字符串是某个同学的真名与所有笔名的最长公共前缀。

最后遍历一遍字典树，进行后序遍历，若搜索至位置 i，若位置 i 上有同学的笔名标记，加入栈中。若位置 i 上有同学的真名标记，如果栈非空，就用栈内的记录的同学与之配对，其公共前缀的长度为当前节点的深度。反之，将标记上放到其父节点中，即缩小某同学的真名与所有笔名的最长公共前缀长度。

但存在一定的问题，如果已经搜索了子树 x，进行操作后栈不为空，随后又搜索了子树 y，且 y 的深度不低于 x。若子树 y 中存在同学的真名标记，就会与栈内的元素配对，而这样计算的答案就是错误的，实际匹配的贡献值应当更小。因此，在进行更深的搜索时应清空栈，但回溯后又需要还原栈的历史状态，很简单，记录搜索到当前节点时的栈大小，让搜索完当前子树后的栈大小与之作差就可以得到实际的栈大小，同时保留剩余的栈元素。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 8e5 + 5 , M = 2e5 + 5;
int n;
string s[M];
int trie[N][27] , tot , ans[M] , sta[M] , top , h = 0;
vector<int>w[N] , vis[N];
void insert(string x , int val) {
    int i = 0;
    for(auto v : x) {
        int k = v - 'a';
        if(!trie[i][k]) trie[i][k] = ++ tot;
        i = trie[i][k];
    }
    vis[i].push_back(val); // 标记位置 $i$ 到根组成的字符串是某个同学的笔名。
}
void find(string x , int val) {
    int i = 0;
    for(auto v : x) {
        int k = v - 'a';
        if(!trie[i][k]) break;
        i = trie[i][k];
    }
    w[i].push_back(val); // 标记位置 $i$ 到根组成的字符串是某个同学的真名与所有笔名的最长公共前缀。
}
void dfs(int i , int fa , int dep , int tp) {
    for(auto v : vis[i]) {
        sta[++ top] = v; // 把当前位置的笔名标记加入栈中
    }
    for(int v = 0 ; v < 26 ; v ++) {
        if(!trie[i][v]) continue;
        dfs(trie[i][v] , i , dep + 1 , top);
    }
    for(int j = w[i].size() - 1 ; j >= 0 ; j --) {
        int v = w[i][j];
        if(top - tp > 0) { // 若栈不为空
            ans[v] = sta[top --]; // 匹配
            h += dep;   // 计算答案
        } else { // 若栈为空
            w[fa].push_back(v); // 上放到其父节点中
        }
        w[i].pop_back();
    }
}
int main() {
    cin>>n;
    for(int i = 1 ; i <= n + n ; i ++) cin>>s[i];
    for(int i = n + 1 ; i <= n + n ; i ++) insert(s[i] , i - n); // 把笔名插入字典树
    for(int i = 1 ; i <= n ; i ++) find(s[i] , i); // 找每个真名与所有笔名中的最长公共前缀 
    dfs(0 , 0 , 0 , 0);
    cout<<h<<'\n';
    for(int i = 1 ; i <= n ; i ++) {
        cout<<i<<' '<<ans[i]<<'\n';
    }
    return 0;
}