信息学奥赛必备：手把手教你解密病历单（附C++完整代码）

信息学奥赛实战：病历单解密算法精解与C++实现

在信息学奥赛的赛场上，字符串处理类题目一直是考察选手基本功的重要题型。病历单解密问题作为OpenJudge和NOI题库中的经典案例，融合了循环移位、逆序操作和大小写转换三大核心技巧。本文将带您深入剖析解题思路，并通过两种不同风格的C++实现方案，展示如何高效解决这类加密解密问题。

1. 问题分析与逆向思维

病历单加密过程包含三个关键步骤：

1. 循环左移3位：每个字母在字母表中向左移动3个位置（z接在a后面）
2. 逆序存储：整个字符串顺序完全颠倒
3. 大小写反转：所有大写字母转为小写，小写字母转为大写

而我们的解密任务则需要逆向执行这些操作。这里需要特别注意操作顺序的逆向处理——加密的最后一步应该是解密的第一步。因此正确的解密步骤应该是：

1. 大小写反转（对应加密的第三步）
2. 逆序存储（对应加密的第二步）
3. 循环右移3位（对应加密的第一步）

提示：在密码学中，这种分步骤的加密方式属于复合加密算法，理解每一步的逆向操作是解题的关键。

2. 核心算法实现细节

2.1 循环右移的数学原理

循环右移3位可以通过模运算优雅实现。对于任意字母字符，我们可以：

1. 将字母转换为0-25的数字（a/A=0，b/B=1，...，z/Z=25）
2. 数字值加3（右移）
3. 对26取模（实现循环）
4. 转换回字母字符

具体公式为：

• 小写字母：c = (c - 'a' + 3) % 26 + 'a'
• 大写字母：c = (c - 'A' + 3) % 26 + 'A'

// 循环右移单个字符的实现示例 char rightShift(char c) { if (c >= 'a' && c <= 'z') { return (c - 'a' + 3) % 26 + 'a'; } else if (c >= 'A' && c <= 'Z') { return (c - 'A' + 3) % 26 + 'A'; } return c; // 非字母字符保持不变 }

2.2 逆序存储的高效实现

字符串逆序可以通过双指针法高效完成，只需遍历前一半字符并进行交换：

void reverseString(char s[]) { int len = strlen(s); for (int i = 0; i < len / 2; ++i) { swap(s[i], s[len - 1 - i]); } }

2.3 大小写转换的多种方式

C++提供了多种大小写转换方法，各有优缺点：

3. 完整代码实现方案一：模块化设计

第一种实现采用模块化设计，将每个解密步骤封装为独立函数，代码结构清晰，便于调试和重用：

#include <bits/stdc++.h> using namespace std; // 逆序存储 void reverseStr(char s[]) { int len = strlen(s); for (int i = 0; i < len / 2; ++i) swap(s[i], s[len - 1 - i]); } // 大小写反转 void flipCase(char s[]) { for (int i = 0; s[i]; ++i) { if (isupper(s[i])) s[i] = tolower(s[i]); else if (islower(s[i])) s[i] = toupper(s[i]); } } // 循环右移3位 void rightShift3(char s[]) { for (int i = 0; s[i]; ++i) { if (isupper(s[i])) s[i] = (s[i] - 'A' + 3) % 26 + 'A'; else if (islower(s[i])) s[i] = (s[i] - 'a' + 3) % 26 + 'a'; } } int main() { char medicalRecord[256]; cin.getline(medicalRecord, 256); // 注意解密步骤顺序与加密相反 flipCase(medicalRecord); reverseStr(medicalRecord); rightShift3(medicalRecord); cout << medicalRecord; return 0; }

这种实现方式的优势在于：

• 每个函数只负责单一功能，符合单一职责原则
• 函数可以单独测试，便于定位问题
• 代码可读性强，易于维护和扩展

4. 完整代码实现方案二：高效单次遍历

第二种实现采用逆向思维，在单次遍历中同时完成逆序和转换操作，减少内存访问次数：

#include <bits/stdc++.h> using namespace std; int main() { char encrypted[256], decrypted[256]; cin.getline(encrypted, 256); int len = strlen(encrypted); for (int i = 0; i < len; ++i) { char c = encrypted[len - 1 - i]; // 逆序访问 // 大小写反转+右移3位 if (c >= 'a' && c <= 'z') { decrypted[i] = (c - 'a' + 3) % 26 + 'A'; // 转为大写 } else if (c >= 'A' && c <= 'Z') { decrypted[i] = (c - 'A' + 3) % 26 + 'a'; // 转为小写 } else { decrypted[i] = c; // 非字母字符不变 } } decrypted[len] = '\0'; // 字符串终止符 cout << decrypted; return 0; }

这种实现的特点包括：

• 只需一次遍历，时间复杂度O(n)
• 使用额外空间存储结果，不影响输入数据
• 合并了逆序和转换操作，减少循环次数
• 适合处理超长字符串（如长度>1MB的情况）

5. 边界条件与异常处理

在实际竞赛中，健壮的代码需要处理各种边界情况：

1. 空字符串输入：应直接返回空字符串
2. 非字母字符：应保持原样不处理
3. 超长输入：确保缓冲区足够大或使用动态分配
4. 混合字符：正确处理数字、标点等非字母字符

// 增强版的右移函数处理边界情况 char safeRightShift(char c) { if (islower(c)) { return (c - 'a' + 3) % 26 + 'a'; } else if (isupper(c)) { return (c - 'A' + 3) % 26 + 'A'; } return c; // 处理所有非字母情况 }

6. 算法优化与性能分析

对于竞赛场景，我们还需要考虑算法效率：

• 时间复杂度：两种实现都是O(n)，n为字符串长度
• 空间复杂度：
  • 方案一：原地修改，O(1)额外空间
  • 方案二：需要O(n)额外空间
• 实际性能差异：
  • 短字符串（<100字符）：差异可以忽略
  • 长字符串（>1MB）：方案二可能更快（缓存友好）

性能测试对比（假设100万次操作）：

7. 扩展应用与变种题目

掌握此类字符串处理技巧后，可以解决许多相似题目：

1. 凯撒密码变种：不同位移量或方向
2. 复杂加密规则：多步复合加密
3. 文件加解密：处理文本文件而非控制台输入
4. 网络数据传输：简单的内容混淆

例如，OpenJudge中的类似题目：

• 密码翻译（1136）：简单字母替换
• Vigenère密码（1402）：使用密钥的多表替换
• 潜伏者：更复杂的映射关系

// 通用循环移位函数示例 void circularShift(char s[], int shift, bool left) { int len = strlen(s); shift %= 26; // 确保在0-25范围内 if (shift < 0) shift += 26; // 处理负位移 for (int i = 0; i < len; ++i) { if (islower(s[i])) { int base = s[i] - 'a'; s[i] = left ? (base - shift + 26) % 26 + 'a' : (base + shift) % 26 + 'a'; } else if (isupper(s[i])) { int base = s[i] - 'A'; s[i] = left ? (base - shift + 26) % 26 + 'A' : (base + shift) % 26 + 'A'; } } }

在实际竞赛中遇到此类题目时，建议先在白纸上明确写出：

1. 加密/解密的具体步骤
2. 每个步骤的逆向操作
3. 操作的正确执行顺序
4. 边界条件的处理方式