![P1071 [NOIP 2009 提高组] 潜伏者](http://pic.xiahunao.cn/yaotu/P1071 [NOIP 2009 提高组] 潜伏者)
记录156#includebits/stdc.h using namespace std; int main() { // 优化IO速度 ios::sync_with_stdio(false); cin.tie(0); string s1,s2,s3; cins1s2s3; // 1. 定义两个 map // decode_map[密文字符] 明文字符 mapchar,char decode_map; // used_map[明文字符] true (用来检查明文是否被占用) mapchar,bool used_map; int len1s1.size(); int cnt0; // 记录成功映射的字母个数 // 2. 如果长度小于26直接判负 if(len126) { coutFailed; return 0; } // 3. 遍历样本建立映射 for(int i0;ilen1;i) { char enc_chars1[i]; // 当前密文字符 char plain_chars2[i]; // 当前明文字符 // 检查这个密文字符之前是否出现过count(key) 用于查找某个键Key在容器中是否存在。 if(decode_map.count(enc_char)) { // 出现过检查它对应的明文是否和现在的一致 if(decode_map[enc_char]!plain_char) { coutFailed; return 0; } } else { // 密文第一次出现准备建立映射。先检查明文是否被占用了 if(used_map[plain_char]) { coutFailed; return 0; } // 双向绑定成功 decode_map[enc_char]plain_char; used_map[plain_char]true; cnt; } } // 4. 检查是否凑齐了26个字母 if(cnt26) { coutFailed; } else { // 5. 翻译目标密文 for(int i0;is3.size();i) { // 直接从 map 中取出对应的明文 coutdecode_map[s3[i]]; } } return 0; }题目传送门https://www.luogu.com.cn/problem/P1071前言我是一名专注信奥赛CSP-J/S、NOIP的教练。如果你觉得这篇题解对你有帮助欢迎点击关注我的CSDN账号我会持续更新高质量算法解析。我深知算法思维的构建远比单纯通过题目更重要本系列题解不局限于AC代码的堆砌而是致力于拆解题目背后的逻辑链条与核心知识点备赛路上若遇瓶颈欢迎随时评论或私信我将甄选典型疑难问题通过视频讲解或撰写专项文章的形式为你提供深度答疑。核心解题思路这道题是一道非常经典的字符串处理与哈希映射Map问题。问题转化双向映射机制题目要求我们根据已知的“密文”和“明文”样本推导出密码本。这本质上是一个双向映射问题密文 →→ 明文一个密文字符只能对应一个明文字符。明文 →→ 密文一个明文字符也只能被一个密文字符对应即不同的字母对应不同的密字。算法设计状态检查与翻译在遍历样本建立密码本的过程中我们需要时刻检查是否违反了上述两个规则。如果违反或者样本中未能覆盖 A~Z 所有的 26 个字母则直接判定为Failed。只有当密码本完美建立后我们才能利用这个密码本去翻译目标密文。代码分块详细解释1. 头文件、输入处理与前置检查#includebits/stdc.h using namespace std; int main() { // 优化IO速度 ios::sync_with_stdio(false); cin.tie(0); string s1, s2, s3; cin s1 s2 s3; // 1. 定义两个 map // decode_map[密文字符] 明文字符 mapchar, char decode_map; // used_map[明文字符] true (用来检查明文是否被占用) mapchar, bool used_map; int len1 s1.size(); int cnt 0; // 记录成功映射的字母个数 // 2. 如果长度小于26直接判负 if(len1 26) { cout Failed; return 0; }详细分析数据结构选择使用两个map容器是本题的核心。decode_map用于记录从密文到明文的翻译规则used_map作为一个标记数组记录哪些明文字母已经被“占用”。前置剪枝由于题目要求 A~Z 共 26 个字母必须全部出现才能破译成功如果样本字符串的长度小于 26绝对不可能凑齐 26 个字母因此直接输出Failed并结束程序。这避免了不必要的遍历。2. 核心逻辑遍历样本与双向绑定检查// 3. 遍历样本建立映射 for(int i 0; i len1; i) { char enc_char s1[i]; // 当前密文字符 char plain_char s2[i]; // 当前明文字符 // 检查这个密文字符之前是否出现过count(key) 用于查找某个键Key在容器中是否存在。 if(decode_map.count(enc_char)) { // 出现过检查它对应的明文是否和现在的一致 if(decode_map[enc_char] ! plain_char) { cout Failed; return 0; } } else { // 密文第一次出现准备建立映射。先检查明文是否被占用了 if(used_map[plain_char]) { cout Failed; return 0; } // 双向绑定成功 decode_map[enc_char] plain_char; used_map[plain_char] true; cnt; } }详细分析这是代码的灵魂完美处理了题目中的“自相矛盾”情况。密文一致性检查如果enc_char已经在decode_map中说明之前已经为它分配过明文。此时必须检查之前分配的明文是否等于当前的plain_char。如果不等说明同一个密文对应了多个明文违反规则直接Failed。明文唯一性检查如果enc_char是第一次出现准备建立映射前必须先检查plain_char是否已经在used_map中被标记为true。如果是说明这个明文已经被其他密文“抢走”了违反了“不同的字母对应不同的密字”规则同样直接Failed。成功绑定只有当上述两个检查都通过时才将映射关系写入decode_map标记plain_char为已占用并将成功映射的计数器cnt加 1。3. 结果判定与目标密文翻译// 4. 检查是否凑齐了26个字母 if(cnt 26) { cout Failed; } else { // 5. 翻译目标密文 for(int i 0; i s3.size(); i) { // 直接从 map 中取出对应的明文 cout decode_map[s3[i]]; } } return 0; }详细分析完整性检查遍历结束后检查cnt是否等于 26。如果小于 26说明样本中未能覆盖所有的字母无法破译完整的密码输出Failed。目标翻译如果密码本完美建立cnt 26则遍历目标密文s3。对于s3中的每一个字符直接利用decode_map作为字典进行 O(1)O(1) 级别的查找并输出对应的明文。核心逻辑总结表代码模块核心变量/操作精炼作用解决的痛点前置剪枝if(len1 26)提前判断样本长度是否足够快速排除样本长度不足导致无法覆盖 26 个字母的情况密文映射decode_map[enc_char]记录密文到明文的翻译规则解决“一个密文对应多个明文”的矛盾检查明文占用used_map[plain_char]标记明文是否已被其他密文绑定解决“多个密文对应同一个明文”的矛盾检查完整性检查if(cnt 26)检查成功映射的字母总数确保 A~Z 所有的 26 个字母都获得了相应的密字目标翻译decode_map[s3[i]]利用哈希表进行字符替换在密码本建立后以极高的效率完成目标密文的翻译
记录156#includebits/stdc.h using namespace std; int main() { // 优化IO速度 ios::sync_with_stdio(false); cin.tie(0); string s1,s2,s3; cins1s2s3; // 1. 定义两个 map // decode_map[密文字符] 明文字符 mapchar,char decode_map; // used_map[明文字符] true (用来检查明文是否被占用) mapchar,bool used_map; int len1s1.size(); int cnt0; // 记录成功映射的字母个数 // 2. 如果长度小于26直接判负 if(len126) { coutFailed; return 0; } // 3. 遍历样本建立映射 for(int i0;ilen1;i) { char enc_chars1[i]; // 当前密文字符 char plain_chars2[i]; // 当前明文字符 // 检查这个密文字符之前是否出现过count(key) 用于查找某个键Key在容器中是否存在。 if(decode_map.count(enc_char)) { // 出现过检查它对应的明文是否和现在的一致 if(decode_map[enc_char]!plain_char) { coutFailed; return 0; } } else { // 密文第一次出现准备建立映射。先检查明文是否被占用了 if(used_map[plain_char]) { coutFailed; return 0; } // 双向绑定成功 decode_map[enc_char]plain_char; used_map[plain_char]true; cnt; } } // 4. 检查是否凑齐了26个字母 if(cnt26) { coutFailed; } else { // 5. 翻译目标密文 for(int i0;is3.size();i) { // 直接从 map 中取出对应的明文 coutdecode_map[s3[i]]; } } return 0; }题目传送门https://www.luogu.com.cn/problem/P1071前言我是一名专注信奥赛CSP-J/S、NOIP的教练。如果你觉得这篇题解对你有帮助欢迎点击关注我的CSDN账号我会持续更新高质量算法解析。我深知算法思维的构建远比单纯通过题目更重要本系列题解不局限于AC代码的堆砌而是致力于拆解题目背后的逻辑链条与核心知识点备赛路上若遇瓶颈欢迎随时评论或私信我将甄选典型疑难问题通过视频讲解或撰写专项文章的形式为你提供深度答疑。核心解题思路这道题是一道非常经典的字符串处理与哈希映射Map问题。问题转化双向映射机制题目要求我们根据已知的“密文”和“明文”样本推导出密码本。这本质上是一个双向映射问题密文 →→ 明文一个密文字符只能对应一个明文字符。明文 →→ 密文一个明文字符也只能被一个密文字符对应即不同的字母对应不同的密字。算法设计状态检查与翻译在遍历样本建立密码本的过程中我们需要时刻检查是否违反了上述两个规则。如果违反或者样本中未能覆盖 A~Z 所有的 26 个字母则直接判定为Failed。只有当密码本完美建立后我们才能利用这个密码本去翻译目标密文。代码分块详细解释1. 头文件、输入处理与前置检查#includebits/stdc.h using namespace std; int main() { // 优化IO速度 ios::sync_with_stdio(false); cin.tie(0); string s1, s2, s3; cin s1 s2 s3; // 1. 定义两个 map // decode_map[密文字符] 明文字符 mapchar, char decode_map; // used_map[明文字符] true (用来检查明文是否被占用) mapchar, bool used_map; int len1 s1.size(); int cnt 0; // 记录成功映射的字母个数 // 2. 如果长度小于26直接判负 if(len1 26) { cout Failed; return 0; }详细分析数据结构选择使用两个map容器是本题的核心。decode_map用于记录从密文到明文的翻译规则used_map作为一个标记数组记录哪些明文字母已经被“占用”。前置剪枝由于题目要求 A~Z 共 26 个字母必须全部出现才能破译成功如果样本字符串的长度小于 26绝对不可能凑齐 26 个字母因此直接输出Failed并结束程序。这避免了不必要的遍历。2. 核心逻辑遍历样本与双向绑定检查// 3. 遍历样本建立映射 for(int i 0; i len1; i) { char enc_char s1[i]; // 当前密文字符 char plain_char s2[i]; // 当前明文字符 // 检查这个密文字符之前是否出现过count(key) 用于查找某个键Key在容器中是否存在。 if(decode_map.count(enc_char)) { // 出现过检查它对应的明文是否和现在的一致 if(decode_map[enc_char] ! plain_char) { cout Failed; return 0; } } else { // 密文第一次出现准备建立映射。先检查明文是否被占用了 if(used_map[plain_char]) { cout Failed; return 0; } // 双向绑定成功 decode_map[enc_char] plain_char; used_map[plain_char] true; cnt; } }详细分析这是代码的灵魂完美处理了题目中的“自相矛盾”情况。密文一致性检查如果enc_char已经在decode_map中说明之前已经为它分配过明文。此时必须检查之前分配的明文是否等于当前的plain_char。如果不等说明同一个密文对应了多个明文违反规则直接Failed。明文唯一性检查如果enc_char是第一次出现准备建立映射前必须先检查plain_char是否已经在used_map中被标记为true。如果是说明这个明文已经被其他密文“抢走”了违反了“不同的字母对应不同的密字”规则同样直接Failed。成功绑定只有当上述两个检查都通过时才将映射关系写入decode_map标记plain_char为已占用并将成功映射的计数器cnt加 1。3. 结果判定与目标密文翻译// 4. 检查是否凑齐了26个字母 if(cnt 26) { cout Failed; } else { // 5. 翻译目标密文 for(int i 0; i s3.size(); i) { // 直接从 map 中取出对应的明文 cout decode_map[s3[i]]; } } return 0; }详细分析完整性检查遍历结束后检查cnt是否等于 26。如果小于 26说明样本中未能覆盖所有的字母无法破译完整的密码输出Failed。目标翻译如果密码本完美建立cnt 26则遍历目标密文s3。对于s3中的每一个字符直接利用decode_map作为字典进行 O(1)O(1) 级别的查找并输出对应的明文。核心逻辑总结表代码模块核心变量/操作精炼作用解决的痛点前置剪枝if(len1 26)提前判断样本长度是否足够快速排除样本长度不足导致无法覆盖 26 个字母的情况密文映射decode_map[enc_char]记录密文到明文的翻译规则解决“一个密文对应多个明文”的矛盾检查明文占用used_map[plain_char]标记明文是否已被其他密文绑定解决“多个密文对应同一个明文”的矛盾检查完整性检查if(cnt 26)检查成功映射的字母总数确保 A~Z 所有的 26 个字母都获得了相应的密字目标翻译decode_map[s3[i]]利用哈希表进行字符替换在密码本建立后以极高的效率完成目标密文的翻译
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
