洛谷字符串题解：从自动修正到凯撒密码的实战技巧（附完整代码）

从“自动修正”到“凯撒密码”：在洛谷上磨砺你的字符串处理利刃

如果你刚开始接触程序设计竞赛，面对洛谷上那些名字听起来就让人头大的字符串题目，是不是有点无从下手？别担心，这几乎是每个竞赛新手的必经之路。字符串处理，这个听起来基础得不能再基础的概念，恰恰是算法竞赛中区分“能写”和“能快速写对”的关键分水岭。它不像动态规划那样需要复杂的状态设计，也不如图论那样有深邃的理论背景，但正是这种看似简单的题目，最容易在细节上让你栽跟头——一个忘记处理的边界条件，一个没考虑到的特殊字符，就足以让整个程序崩溃。

这篇文章就是为你准备的。我们不打算照本宣科地复述教材，而是想和你一起，像侦探一样拆解洛谷上几个经典的字符串问题。我们会从最基础的字符大小写转换（自动修正）出发，一路探索到充满古典密码学趣味的凯撒加密，过程中会穿插大量我早期刷题时踩过的坑、总结的技巧，以及如何让代码既清晰又高效的实战心得。我们的目标很明确：让你不仅能看懂题解，更能理解背后的思路，最终能独立、自信地解决同类问题。

1. 基石：理解字符串在内存中的“模样”

在动手写第一行代码之前，我们必须先达成一个共识：在计算机眼里，字符串到底是什么？很多初学者的问题，根源就在于对这个基本事实的模糊认识。

在C++中，处理字符串通常有两种方式：C风格字符数组和C++的std::string类。它们底层都是连续的字符序列，但“性格”迥异。

• C风格字符串（字符数组）：它更像一个老实巴交的工人，你需要手动管理一切。它的结尾必须有一个特殊的哨兵字符——\0（空字符）来标识字符串的终止。如果你忘了设置它，或者数组空间开小了，程序就会读取到数组边界外的内存垃圾，导致不可预知的行为（通常是崩溃）。这种方式的优点是极致轻量，在某些对性能要求极高的场景下仍有价值。
• std::string类：这是C++提供的“智能管家”。你不需要操心内存分配和结尾符，string对象自己会管理长度和容量。它提供了append、substr、find等一大堆现成的方法，极大提升了开发效率和代码安全性。对于竞赛，我强烈建议初学者优先使用std::string，它能帮你避开90%因内存管理导致的低级错误。

注意：即使使用std::string，当你需要与一些传统的C库函数（如printf、scanf）交互时，可能需要通过.c_str()方法获取其内部的C风格字符串指针。这是一个常见的转换点。

理解了这个，我们再来看一个核心操作：遍历。无论是数组还是string，遍历都是所有字符串处理的基础。这里有一个我早期常犯的错误：

// 错误示例：使用整数与字符串长度直接比较 char s[100] = "hello"; for(int i = 0; i < strlen(s); i++) { // 处理s[i] }

问题在哪？strlen(s)在每次循环条件判断时都会被调用一次，而strlen是一个O(n)复杂度的函数（它需要遍历字符串直到找到\0）。如果字符串长1000，这个循环就相当于做了1000 * 1000次操作，效率极低。

正确的做法是：

// 方法1：对于C风格字符串，利用'\0'作为终止条件 char s[100] = "hello"; for(int i = 0; s[i] != '\0'; i++) { // 处理s[i] } // 方法2：对于std::string，先获取长度 std::string str = "hello"; int len = str.length(); // 或 str.size() for(int i = 0; i < len; i++) { // 处理str[i] }

第二种方法中，str.length()的复杂度是O(1)，因为string对象自己存储了长度信息。

2. 实战拆解：从“自动修正”看字符的本质

洛谷的“自动修正”题目（P5733）是一个绝佳的热身。题目要求很简单：将输入字符串中的所有小写字母转换为大写。但正是这种简单，让我们可以聚焦于字符运算的核心原理。

字符在计算机中是以ASCII码（或Unicode码）存储的整数。大小写字母的编码是连续且有规律的。看下面这个表格，你就能一目了然：

观察一下，同一个字母的大小写，ASCII码值相差32（‘a’ - ‘A’ = 97 - 65 = 32）。因此，小写转大写的核心操作就是：s[i] = s[i] - 32;或者更优雅地：s[i] = s[i] - ('a' - 'A');

后一种写法更好，因为它直接表达了“字符间的距离”，意图更清晰，且不依赖具体的魔法数字32。

但这里有一个至关重要的细节：题目只要求转换小写字母。如果字符串里混有数字、标点或其他字符呢？直接减去32会把它们变成奇怪的符号。所以我们必须先判断。

#include <iostream> #include <string> using namespace std; int main() { string s; cin >> s; // 或使用getline(cin, s)如果需要读入空格 for (int i = 0; i < s.length(); i++) { // 判断是否为小写字母 if (s[i] >= 'a' && s[i] <= 'z') { s[i] = s[i] - ('a' - 'A'); // 小写转大写 } } cout << s << endl; return 0; }

看起来完美了？这里还藏着一个输入上的坑。cin >> s会以空格、制表符、换行符作为分隔符。如果题目输入是“Hello World”，cin只会读到“Hello”。这时就需要用到getline(cin, s)来读取整行。务必仔细阅读题目对输入格式的描述，这是竞赛中节省调试时间的关键。

3. 进阶：凯撒密码与“模运算”的魔法

掌握了字符的“加减法”，我们就可以玩点更有趣的了——凯撒密码（P1914）。这是一种古老的替换加密，将明文中的所有字母都在字母表上向后（或向前）偏移一个固定数目后形成密文。

例如，偏移量n=3时：

• A -> D, B -> E, …, X -> A, Y -> B, Z -> C

这里的核心挑战是循环移位。当字母偏移后超过‘z’时，它应该绕回到‘a’。这正是模运算（%）大显身手的地方。

模运算可以理解为一个“循环计数器”。对于26个字母，我们可以将字母‘a’到‘z’映射为数字0到25。

• ‘a’的索引：‘a’ - ‘a’ = 0
• ‘z’的索引：‘z’ - ‘a’ = 25

加密过程就是：新索引 = (原索引 + 偏移量n) % 26。然后再将新索引转换回字符：新字符 = 新索引 + ‘a’。

#include <iostream> #include <string> using namespace std; int main() { int n; string s; cin >> n >> s; for (int i = 0; i < s.length(); i++) { // 假设输入保证全是小写字母 int original_index = s[i] - 'a'; // 得到0-25的索引 int new_index = (original_index + n) % 26; // 循环移位 s[i] = new_index + 'a'; // 转回字符 } cout << s << endl; return 0; }

这段代码简洁有力。但如果我们想让它更健壮，处理可能的大写字母或非字母字符呢？我们可以扩展一下逻辑：

for (int i = 0; i < s.length(); i++) { if (s[i] >= 'a' && s[i] <= 'z') { // 处理小写字母 s[i] = 'a' + (s[i] - 'a' + n) % 26; } else if (s[i] >= 'A' && s[i] <= 'Z') { // 处理大写字母 s[i] = 'A' + (s[i] - 'A' + n) % 26; } // 其他字符保持不变 }

凯撒密码题目完美展示了如何将一个问题抽象成数学模型（模运算），并用简洁的代码实现。这种“抽象-建模-编码”的思维，是解决更复杂算法问题的基石。

4. 核心武器库：必须掌握的字符串处理函数

当问题变得复杂，手动用循环处理每一个字符会非常繁琐且易错。这时，std::string提供的成员函数就成了你的瑞士军刀。我们结合洛谷“文字处理软件”（P5738）这道题，来熟悉几个最常用的。

下表总结了几个核心操作及其对应函数：

“文字处理软件”这道题直接考察了这四个操作。它的代码框架非常典型：

#include <iostream> #include <string> using namespace std; int main() { int q; // 操作次数 string str; cin >> q >> str; while (q--) { int op; cin >> op; if (op == 1) { string s; cin >> s; str += s; // 或 str.append(s) cout << str << endl; } else if (op == 2) { int a, b; cin >> a >> b; str = str.substr(a, b); // 截取 cout << str << endl; } else if (op == 3) { int a; string s; cin >> a >> s; str.insert(a, s); // 插入 cout << str << endl; } else if (op == 4) { string s; cin >> s; size_t pos = str.find(s); if (pos == string::npos) { cout << -1 << endl; } else { cout << pos << endl; } } } return 0; }

提示：string::npos是一个静态常量，表示“未找到”的特殊值。它是一个非常大的数（通常是size_t类型的最大值），用于和find函数的返回值进行比较。

通过这道题，你不仅学会了函数调用，更重要的是理解了如何根据不同的操作指令（op），来组织分支逻辑和输入读取。这是很多“模拟题”的通用解法。

5. 输入的艺术：避开字符串题的第一个大坑

我见过太多初学者，算法思路完全正确，却卡在如何正确读入数据这一步。字符串题的输入格式往往多变，选错了读入方式，就会丢失数据或得到错误结果。

• cin >> str：最简单的读入，但遇到空格、制表符、换行符就会停止。适合读取没有空白字符的单个单词。
• getline(cin, str)：读取一整行，包括开头的空白符，直到遇到换行符（换行符会被读取但不会存入str）。这是读取带空格句子或整行文本的首选。
• scanf(“%s”, char_array)：C风格，用于读入字符数组，行为类似cin >>，遇到空白符停止。需要预先分配足够大的数组。
• fgets(char_array, size, stdin)：C风格，读取一行到字符数组，会存储换行符（如果数组空间足够）。需要注意处理末尾可能存在的换行符。

一个经典的陷阱是cin和getline混用。cin读取一个整数后，换行符会留在输入缓冲区。紧接着的getline会立刻读到这个空行，导致程序看似被“跳过”。

int n; string s; cin >> n; // 假设输入"5\n"，cin读取了5，留下了'\n' getline(cin, s); // 立刻读到了残留的'\n'，s变成空字符串！

解决方案：在cin >> n;之后，用cin.ignore()清空缓冲区，或者多调用一次getline“吃掉”那个空行。

int n; string s; cin >> n; cin.ignore(); // 忽略掉换行符 getline(cin, s); // 现在可以正确读取下一行内容了

洛谷“口算练习题”（P1957）一题，完美融合了多种输入判断技巧。它需要根据每行开头的字符决定运算类型，如果开头不是字母，则沿用上一行的运算类型。这要求你必须能完整读取一行，再进行分析。getline或fgets在这里是必不可少的。

6. 思维跃迁：统计与映射的妙用

字符串问题不止于变换和操作，更常见的是统计与分析。例如“笨小猴”（P1125）要求统计单词中字母出现频率，并判断最大最小频次差是否为质数。这类问题的核心是建立从字符到信息的映射。

最直接的映射工具就是数组。因为字母只有26个，我们可以用一个长度为26的int数组count[26]来充当映射表。

• count[0]对应字母 ‘a’ 的出现次数
• count[1]对应字母 ‘b’ 的出现次数
• …
• count[25]对应字母 ‘z’ 的出现次数

如何将字符ch映射到正确的索引？利用ASCII码的连续性：index = ch - ‘a’。

#include <iostream> #include <string> #include <cmath> using namespace std; bool isPrime(int x) { if (x < 2) return false; if (x == 2) return true; if (x % 2 == 0) return false; for (int i = 3; i * i <= x; i += 2) { if (x % i == 0) return false; } return true; } int main() { string word; cin >> word; int count[26] = {0}; // 初始化所有计数器为0 // 统计阶段 for (char ch : word) { // 范围for循环，遍历每个字符 if (ch >= 'a' && ch <= 'z') { count[ch - 'a']++; } // 如果题目说明只有小写字母，可以不加判断 } // 查找最大最小值 int maxCnt = 0, minCnt = word.length(); // 最小值初始化为一个很大的可能值 for (int i = 0; i < 26; i++) { if (count[i] > 0) { // 只考虑出现过的字母 if (count[i] > maxCnt) maxCnt = count[i]; if (count[i] < minCnt) minCnt = count[i]; } } int delta = maxCnt - minCnt; if (isPrime(delta)) { cout << "Lucky Word" << endl << delta << endl; } else { cout << "No Answer" << endl << 0 << endl; } return 0; }

这里有两个值得学习的点：

1. 初始化技巧：int count[26] = {0};这行代码会将数组所有元素初始化为0。这是C/C++的语法糖。
2. 遍历方式：for (char ch : word)是C++11引入的范围for循环，比传统的下标遍历更简洁安全，尤其适合只读遍历。

当映射关系更复杂时（比如需要将单词映射到数字），我们可以使用C++的std::map或std::unordered_map。例如“斯诺登的密码”（P1603）一题，就需要将英文单词（如”one”, “both”）映射到其对应的数字平方模100的值。这时用数组映射就不方便了，因为键（key）是字符串而非单个字符。

#include <iostream> #include <string> #include <map> #include <algorithm> #include <vector> using namespace std; int main() { // 建立单词到数字的映射 map<string, int> wordToNum = { {"one", 1}, {"two", 4}, {"three", 9}, // ... 省略其他映射 {"first", 1}, {"second", 4}, {"third", 9} }; vector<int> nums; string word; for (int i = 0; i < 6; i++) { cin >> word; if (wordToNum.count(word)) { // 检查单词是否在映射中 nums.push_back(wordToNum[word]); } } // ... 后续对nums排序、组合成最小数字的逻辑 return 0; }

使用map让代码的意图非常清晰：就是查表。这种“用数据结构直接表达问题逻辑”的能力，是向中级竞赛选手迈进的关键。

7. 综合挑战：状态分析与边界处理

最后，我们来看一类更有挑战性的问题：它们需要你在遍历字符串时，维护某种“状态”，并根据字符的变化来更新状态和答案。洛谷“统计单词数”（P1308）和“honoka的键盘”（P3741）是这方面的典型。

“统计单词数”要求在一篇文章中查找一个单词出现的次数和首次位置，不区分大小写。一个精妙的做法是在单词和文章的首尾都加上一个空格，然后直接用find查找” word “。这样可以完美避免单词是另一个单词一部分的情况（例如在“this”中查找“is”）。

// 核心思路片段 string word, text; getline(cin, word); getline(cin, text); // 统一转为小写 transform(word.begin(), word.end(), word.begin(), ::tolower); transform(text.begin(), text.end(), text.begin(), ::tolower); // 首尾加空格，构造搜索模式 word = ' ' + word + ' '; text = ' ' + text + ' '; size_t pos = text.find(word); if (pos == string::npos) { cout << -1 << endl; } else { int firstPos = pos; int count = 0; while (pos != string::npos) { count++; pos = text.find(word, pos + 1); // 从下一个位置开始继续查找 } // 注意：因为我们在原文前加了一个空格，所以首次出现位置需要调整 cout << count << " " << firstPos << endl; }

而“honoka的键盘”则需要一点贪心思维。题目要求通过一次修改（将一个V改成K或将K改成V），使得字符串中“VK”子串的数量最多。我们的策略是：

1. 先扫描一遍，找出所有现成的“VK”并标记，同时计数。
2. 再扫描一遍，寻找是否存在“VV”或“KK”这样的相邻对（且未被第一步标记过）。如果存在，我们可以通过修改其中一个字符，制造出一个新的“VK”，从而使总数加一。

#include <iostream> #include <string> using namespace std; int main() { int n; string s; cin >> n >> s; int count = 0; vector<bool> used(n, false); // 标记数组，记录哪些位置已组成“VK” // 第一遍：统计并标记现有的“VK” for (int i = 0; i < n - 1; i++) { if (s[i] == 'V' && s[i+1] == 'K') { count++; used[i] = used[i+1] = true; // 标记这两个位置已被使用 i++; // 跳过下一个字符，因为它已配对 } } // 第二遍：寻找可以创造一个新“VK”的机会 for (int i = 0; i < n - 1; i++) { if (!used[i] && !used[i+1]) { if ((s[i] == 'V' && s[i+1] == 'V') || (s[i] == 'K' && s[i+1] == 'K')) { count++; break; // 只能修改一次，找到一次机会就退出 } } } cout << count << endl; return 0; }

这类题目锻炼的是你将问题分解为多个扫描阶段，并在每个阶段维护正确状态的能力。多画图，多用手模拟几个例子，是理解这类算法最有效的方法。

字符串处理的旅程，从理解字符在内存中的表示开始，到熟练运用各种函数和数据结构，最后到解决需要综合状态分析的问题。这条路没有太多高深的理论，更多的是细心、实践和对细节的把握。我刚开始刷题时，也经常因为少考虑一个边界条件、用错一个输入函数而调试半天。但每一次踩坑，都让下一次的代码更加稳健。洛谷上的这些字符串题目，就像一个个精心设计的木人桩，反复捶打你的基本功。当你能够不假思索地写出正确、高效的字符串处理代码时，你会发现，面对更复杂的算法数据结构，你也有了更扎实的底气去拆解和实现。剩下的，就是去题目中实践，把每一个技巧都变成肌肉记忆。