题解：P1071 [NOIP 2009 提高组] 潜伏者

· · 题解

具体思路，用 map 处理已知密文到明文匹配。每做一次破译，成功则记录到 map，遇到破译矛盾直接 Failed 结束（状态 3）。匹配处理完成后，破译匹配数量达到 26 则成功（状态 1），否则 Failed 结束（状态 2）。最后对目标密文进行破译输出。

一个难点是破译矛盾（状态 3）的判断，有大佬用双向 map 非常好用，我这里用 map 直接判断密文到明文是否有映射不一致，用一个 set 记录已经被映射的明文，从而来判断明文是否被其他密文已经映射过。

这题开始还入了个小坑。状态 2 判读，读题时误以为是针对要破解的信息找不到原信息，后来发现是必须要通过原文和密文破解全部 26 个字母。

AC 代码

#include <bits/stdc++.h>
using namespace std;
map<char, char> mp; //密文到明文匹配
set<char> st; //被匹配过的明文 
int main(){
    string s1, s2, s3, t;
    cin >> s1 >> s2 >> s3;
    for(int i = 0; i < s1.size(); i++){
        //密文是否被匹配过 
        if(mp.count(s1[i])) {
            //匹配过，但匹配矛盾，状态3错误 
            if(mp[s1[i]] != s2[i]) {
                cout << "Failed";
                return 0;
            }
        }else{
            //明文被其他密文匹配过，状态3错误          
            if(st.count(s2[i])) {
                cout << "Failed";
                return 0;
            }           
            //匹配成功，建立密文到明文匹配，并记录已经匹配过的明文 
            mp[s1[i]] = s2[i];
            st.insert(s2[i]);
        }
    }   
    //如果没有匹配到26对，状态2错误 
    if(mp.size() < 26){
        cout << "Failed";
        return 0;
    }
    //根据密文匹配输出
    for(int i = 0; i < s3.size(); i++){
        cout << mp[s3[i]];
    }
    return 0;
}