题解：SP28 HMRO - Help the Military Recruitment Office!

ggc123 · 2025-07-11 16:45:36 · 题解

题意

已知 n 个人的 PIESL 码和所属的 MRO。将 m 个 MRO 替换为新的 MRO。询问 t 次，输出询问的 MRO。

思路

按照题目模拟。使用两个 map<string,string> 分别为 m1 和 fa.

• m1 存储每个人的 PIESL 和旧的 MRO。
• fa 存储旧的 MRO 和新的 MRO。

使用并查集进行优化。

代码

#include<bits/stdc++.h>
#define int long long

using namespace std;

int T, n, m, t;
map<string, string> m1, fa;
string findfa(string x) {
    return fa[x] = (fa[x] == x ? x : findfa(fa[x]));
}
signed main() {
    cin.tie(0), cout.tie(0);
    cin >> T;
    while (T--) {
        m1.clear(), fa.clear();

        cin >> n;
        for (int i = 1; i <= n; i++) {
            string PIESL, MRO;
            cin >> PIESL >> MRO;
            m1[PIESL] = MRO;
            fa[MRO] = MRO;
        }
        cin >> m;
        for (int i = 1; i <= m; i++) {
            string Old, New;
            cin >> Old >> New;
            fa[findfa(Old)] = findfa(New);
        }
        cin >> t;
        for (int i = 1; i <= t; i++) {
            string q;
            cin >> q;
            cout << q << " " << findfa(m1[q]) << "\n";
        }
    }
    return 0;
}

附上 AC 记录