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

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

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

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

AC 代码

CPP

#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;
}

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

文章操作

相关推荐

评论

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