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]]利用哈希表进行字符替换在密码本建立后以极高的效率完成目标密文的翻译

相关新闻

鸿蒙 ArkTS 实战:Taxi Fare Estimator 从打车费用估算到出行费用应用完整解析

鸿蒙 ArkTS 实战:Taxi Fare Estimator 从打车费用估算到出行费用应用完整解析

鸿蒙 ArkTS 实战:Taxi Fare Estimator 从打车费用估算到出行费用应用完整解析 前言 打车费用估算 是一个典型的鸿蒙 ArkTS 轻量工具页面。它围绕“根据车型、里程和等待时间估算打车费用,支持快车、专车和豪华三种计价模型。”这个明确需求&#xff0c…

2026/11/16 5:13:09 阅读更多 →
TI PRCM时钟源选择:从寄存器配置到系统级时钟管理实战

TI PRCM时钟源选择:从寄存器配置到系统级时钟管理实战

1. 项目概述:从寄存器手册到系统级时钟设计如果你和我一样,常年泡在嵌入式底层开发里,那对TI(德州仪器)的PRCM模块一定不陌生。手册里那些密密麻麻的寄存器位域描述,像MPU_CLKSRC、VIDEO_PLL_CLKSRC&#x…

2026/11/16 5:13:09 阅读更多 →
DSP硬件设计核心:时序参数与热阻特性深度解析与实战指南

DSP硬件设计核心:时序参数与热阻特性深度解析与实战指南

1. 项目概述:为什么DSP的时序与热阻是硬件设计的“命门”在通信基站、专业音频处理设备或者医疗成像系统里,我们这些硬件工程师选型DSP芯片时,除了看主频、算力、内存这些显性指标,有两个藏在数据手册深处的参数,往往决…

2026/11/16 5:13:16 阅读更多 →

最新新闻

Electron桌面应用开发实战:从环境搭建到打包发布全流程

Electron桌面应用开发实战:从环境搭建到打包发布全流程

做前端这些年,我大部分时间都在跟浏览器标签页打交道,直到第一次把桌面应用跑起来,才发现原来自己一直被限制在地址栏和刷新按钮围起来的框框里。Electron这个词,最开始是在某段时间频繁出现在同事的讨论里,一个用HTML…

2026/11/16 8:22:12 阅读更多 →
滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

简介:亚太天能T109滑盖智能锁产品说明书是一份PDF格式的官方技术文档,主要面向智能锁安装人员、终端用户及售后维护者,帮助快速掌握产品安装、配置与常见故障处理。全包仅1个PDF文件,大小4.37MB,内容结构清晰&#xff…

2026/11/16 6:41:34 阅读更多 →
PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

上个月我在调试一台高速AGV的驱动系统,整车要求空载跑到8m/s,电机转速已经拉到额定点,驱动器的输出电压也顶到了母线电压极限附近。再往上踩速度指令,转速纹丝不动,三相电流反而开始震荡。那会儿我的第一反应就是&…

2026/11/16 8:22:12 阅读更多 →
C++核心知识点:从内存管理到STL的实战指南

C++核心知识点:从内存管理到STL的实战指南

C 这门语言我前前后后折腾了十几年,用它写过嵌入式驱动、做过游戏服务端,也搭过基础组件库。每次看到新人一头扎进"C 核心知识点"这个搜索词,我其实挺感慨的——这门语言的难点从来不是语法多,而是知识点之间的耦合太深…

2026/11/16 8:22:12 阅读更多 →
T109滑盖智能锁怎么装?安装调试与故障排查全攻略

T109滑盖智能锁怎么装?安装调试与故障排查全攻略

简介:亚太天能T109滑盖智能锁产品说明书以PDF格式发布,适合智能锁用户、安装人员与售后维修人员阅读。内容围绕T109系列指纹密码刷卡锁展开,先介绍前面板、后面板、锁体、机械钥匙、电池盒盖等部件名称与功能,再给出完整安装步骤&…

2026/11/16 7:30:18 阅读更多 →
LLM知识降熵:从信息垄断到理解权下放

LLM知识降熵:从信息垄断到理解权下放

你有没有过这种经历:翻开源码注释、论文摘要或者一份专业报告,每个字都认识,连在一起却像天书。想找人聊聊,身边要么没人懂,要么懂的懒得跟你解释。后来我试着把同一段内容丢给一个大语言模型,几秒钟之后&a…

2026/11/16 8:22:12 阅读更多 →

日新闻

周新闻

月新闻