信息学奥赛刷题笔记：OpenJudge NOI 1.7 27 单词翻转的三种解法（C++实现）
在信息学奥赛（NOI）的备赛过程中，字符串处理是基础但至关重要的技能。OpenJudge平台上的NOI 1.7 27题"单词翻转"就是一个经典的字符串操作题目，要求将输入句子中的每个单词进行翻转，但保持单词间的原始顺序。这道题目看似简单，却能考察选手对字符串处理、数组操作和算法思维的掌握程度。本文将深入分析三种不同的C++实现方法，从最基础的二维数组到更高级的string类操作，再到直接遍历的高效解法，帮助备赛的OIer们理解不同解法的优劣，提升解题的灵活性和代码优化能力。
1. 解法一：二维数组保存与翻转
二维数组是C语言风格字符串处理的典型代表，适合对内存操作有严格要求或需要兼容旧代码库的场景。这种方法的思路清晰：先将整个句子拆分成独立的单词存入二维数组，然后逐个翻转每个单词，最后输出结果。
#include <bits/stdc++.h> using namespace std; void rev(char s[]) { int len = strlen(s); for(int i = 0; i < len / 2; ++i) swap(s[i], s[len-1-i]); } int main() { char s[505], w[500][505]; cin.getline(s, 505); int len = strlen(s), wi = 0, wj = 0; for(int i = 0; i <= len; ++i) { if(s[i] == ' ' || s[i] == '\0') { w[wi++][wj] = '\0'; wj = 0; } else { w[wi][wj++] = s[i]; } } for(int i = 0; i < wi; ++i) { rev(w[i]); cout << w[i] << ' '; } return 0; }关键点分析：
- 内存预分配：需要预先估计最大单词数量和单词最大长度（这里分别设为500和505）
- 手动字符串终止：每个单词后需要手动添加'\0'作为结束符
- 双重索引管理：wi记录单词数量，wj记录当前单词的字符位置
- 自定义翻转函数：rev()函数通过交换首尾字符实现翻转
注意：在本地测试时，控制台输入后需要按Ctrl+Z再回车来模拟EOF结束输入
2. 解法二：string类与STL算法
C++的string类提供了更高级、更安全的字符串操作方式，配合STL算法可以大幅简化代码。这种方法利用了string类的substr方法和STL的reverse算法，代码更加简洁易读。
#include <bits/stdc++.h> using namespace std; int main() { string s, w[500]; int wi = 0, b = 0; getline(cin, s); for(int i = 0; i <= s.length(); ++i) { if(s[i] == ' ' || s[i] == '\0') { w[wi++] = s.substr(b, i-b); b = i+1; } } for(int i = 0; i < wi; ++i) { reverse(w[i].begin(), w[i].end()); cout << w[i] << ' '; } return 0; }优势对比：
| 特性 | 二维数组解法 | string类解法 |
|---|---|---|
| 内存管理 | 手动预分配 | 自动动态分配 |
| 字符串操作 | 手动处理 | 内置方法 |
| 代码复杂度 | 较高 | 较低 |
| 安全性 | 易出现越界 | 相对安全 |
| 适用场景 | 嵌入式/C兼容 | 现代C++项目 |
3. 解法三：直接遍历与即时输出
前两种方法都需要额外存储所有单词，而直接遍历法则采用"边读取边处理"的策略，无需存储中间结果，显著降低了空间复杂度，特别适合处理超长字符串。
#include <bits/stdc++.h> using namespace std; int main() { char s[505]; cin.getline(s, 505); int b = 0, len = strlen(s); for(int i = 0; i <= len; ++i) { if(s[i] == ' ' || s[i] == '\0') { for(int j = i - 1; j >= b; j--) cout << s[j]; cout << ' '; b = i + 1; } } return 0; }性能对比分析：
空间复杂度
- 二维数组：O(n*m)，n为单词数，m为最长单词长度
- string类：O(n*m)，但动态分配更灵活
- 直接遍历：O(1)，仅需存储原始字符串
时间复杂度
- 三种方法均为O(L)，L为字符串总长度
- 直接遍历法减少了中间存储步骤，实际运行可能更快
适用场景选择
- 需要后续处理单词：选择前两种
- 仅需输出结果：优先考虑直接遍历
- 内存严格受限：直接遍历最优
4. 解题技巧与常见错误
在实际编程竞赛中，字符串处理题目往往隐藏着一些陷阱。以下是解决单词翻转类题目时的实用技巧和常见错误：
输入处理技巧：
- 使用
getline而非cin >>读取整行，避免被空格截断 - 注意字符串末尾的'\0'处理
- 本地测试时使用Ctrl+Z(Windows)或Ctrl+D(Linux/Mac)模拟EOF
边界条件检查：
- 空字符串输入
- 仅有一个单词的情况
- 单词间多个连续空格
- 字符串开头或结尾有空格
常见错误示例：
// 错误1：忘记处理字符串结束符 for(int i = 0; i < len; ++i) { // 应为i <= len if(s[i] == ' ') { // ... } } // 错误2：翻转时索引计算错误 void rev(char s[]) { int len = strlen(s); for(int i = 0; i < len; ++i) // 应为i < len/2 swap(s[i], s[len-i]); // 应为s[len-1-i] }优化建议：
- 对于固定字符集（如仅小写字母），可考虑位操作优化
- 在性能关键场景，直接指针操作可能比数组索引更快
- 使用
reserve()预分配string内存减少重分配开销 - 考虑使用stringstream进行更灵活的单词分割
5. 扩展思考与变式题目
掌握基础解法后，可以通过以下变式题目进一步巩固字符串处理能力：
变式1：保留标点位置输入可能包含标点符号，要求翻转单词但保持标点位置不变。例如： "hello, world!" → "olleh, dlrow!"
变式2：指定单词翻转仅翻转句子中特定位置的单词（如偶数位置的单词）
变式3：多语言支持处理包含多字节字符（如中文）的文本翻转
变式4：内存极致优化在严格内存限制下（如1MB），处理超长文本（如1GB）的单词翻转
// 变式1的参考解法框架 void reverseWordsKeepPunctuation(string &s) { vector<pair<string, bool>> tokens; // string和是否为单词的标志 // 分词逻辑... for(auto &token : tokens) { if(token.second) // 如果是单词则翻转 reverse(token.first.begin(), token.first.end()); } // 重组字符串... }在实际比赛中，选择哪种方法取决于具体问题的约束条件和个人的编码习惯。二维数组解法虽然略显原始，但在某些内存受限的嵌入式环境中可能是唯一选择；string类解法代码简洁，适合快速开发；直接遍历法则在空间效率上无可匹敌。理解每种方法的优劣，才能在比赛中根据题目特点做出最佳选择。
