企业官网建设流程全解析

记录156

#include<bits/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[密文字符] = 明文字符 map<char,char> decode_map; // used_map[明文字符] = true (用来检查明文是否被占用) map<char,bool> used_map; int len1=s1.size(); int cnt=0; // 记录成功映射的字母个数 // 2. 如果长度小于26，直接判负 if(len1<26) { cout<<"Failed"; return 0; } // 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++; } } // 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; }

题目传送门https://www.luogu.com.cn/problem/P1071

前言

我是一名专注信奥赛（CSP-J/S、NOIP）的教练。

• 如果你觉得这篇题解对你有帮助，欢迎点击关注我的CSDN账号，我会持续更新高质量算法解析。
• 我深知算法思维的构建远比单纯通过题目更重要，本系列题解不局限于AC代码的堆砌，而是致力于拆解题目背后的逻辑链条与核心知识点
• 备赛路上若遇瓶颈，欢迎随时评论或私信，我将甄选典型疑难问题，通过视频讲解或撰写专项文章的形式，为你提供深度答疑。

核心解题思路

这道题是一道非常经典的字符串处理与哈希映射（Map）问题。

1. 问题转化（双向映射机制）：
   题目要求我们根据已知的“密文”和“明文”样本，推导出密码本。这本质上是一个双向映射问题：

   • 密文 →→ 明文：一个密文字符只能对应一个明文字符。
   • 明文 →→ 密文：一个明文字符也只能被一个密文字符对应（即不同的字母对应不同的密字）。

2. 算法设计（状态检查与翻译）：
   在遍历样本建立密码本的过程中，我们需要时刻检查是否违反了上述两个规则。如果违反，或者样本中未能覆盖 A~Z 所有的 26 个字母，则直接判定为Failed。只有当密码本完美建立后，我们才能利用这个密码本去翻译目标密文。

代码分块详细解释

1. 头文件、输入处理与前置检查

#include<bits/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[密文字符] = 明文字符 map<char, char> decode_map; // used_map[明文字符] = true (用来检查明文是否被占用) map<char, 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) 级别的查找，并输出对应的明文。

核心逻辑总结表