信息学奥赛解题实战：OpenJudge NOI 1.7 27 单词翻转的三种编程思路详解

1. 题目解析与解题思路概览

遇到字符串处理类题目时，很多初学者容易陷入"直接硬编码"的误区。我们先来看OpenJudge NOI 1.7 27这道单词翻转题的本质要求：输入一行由多个单词组成的字符串，要求输出每个单词字母顺序反转后的结果，但单词间的空格位置保持不变。

举个例子： 输入："hello world" 正确输出："olleh dlrow" 错误输出："dlrow olleh"（这是整体反转，不符合要求）

这类题目在信息学奥赛中非常典型，考察三个核心能力：

1. 字符串分割：如何准确识别单词边界（空格分隔）
2. 局部处理：对每个单词独立进行反转操作
3. 输出控制：保持原有空格位置不变

实际解题时会遇到几个常见陷阱：

• 连续多个空格的处理
• 字符串开头/结尾有空格的情况
• 超长字符串的存储限制（特别是使用C风格字符数组时）

2. 解法一：二维数组存储法

2.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; }

2.2 关键点分析

1. 输入处理：使用cin.getline()读取整行，避免cin>>遇到空格就截断
2. 单词分割：通过空格和'\0'判断单词边界
3. 反转算法：经典的对称交换法，时间复杂度O(n/2)

2.3 优劣对比

优势：

• 内存布局直观，便于理解字符串存储本质
• 适合嵌入式等需要精确控制内存的场景

劣势：

• 需要预先分配固定大小的二维数组（可能浪费内存）
• 手动处理字符串终止符'\0'容易出错

3. 解法二：STL string容器法

3.1 现代C++实践

这种方法充分利用C++标准库的特性，代码更简洁安全：

#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; }

3.2 技术亮点

1. substr方法：直接提取子串，避免手动处理字符数组
2. reverse算法：使用STL内置算法，避免重复造轮子
3. 自动内存管理：string类自动处理内存分配和释放

3.3 常见问题

初学者容易犯的错误：

• 忘记初始化字符串索引变量b
• 错误计算substr的第二个参数（应该是长度而非结束位置）
• 误用reverse参数（需要传迭代器而非字符串对象）

4. 解法三：原地遍历法

4.1 空间最优解

这种方法不需要额外存储空间，直接在遍历过程中输出结果：

#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; }

4.2 性能分析

• 时间复杂度：O(n)，只需一次完整遍历
• 空间复杂度：O(1)，仅用少量辅助变量

4.3 适用场景

特别适合：

• 内存受限的环境
• 只需要输出结果而无需保留中间数据的场景
• 超长字符串处理（避免内存溢出）

5. 调试技巧与边界测试

5.1 本地输入终止方法

在本地测试时，程序会等待持续输入。可以使用以下方法终止输入：

1. Windows系统：输入完成后按Ctrl+Z然后回车
2. Linux/Mac系统：Ctrl+D

5.2 测试用例设计

建议测试以下边界情况：

1. 空字符串输入
2. 单个单词无空格
3. 连续多个空格
4. 首尾带空格的情况
5. 超长单词（接近505字符限制）

例如测试用例：

输入：" abc def " 预期输出：" cba fed "

5.3 性能优化建议

1. 对于解法一，可以优化为动态分配内存
2. 解法二中vector替代原生数组更安全
3. 解法三可以改用双指针法减少变量数量

6. 算法思维扩展

6.1 其他字符串处理问题

掌握单词翻转后，可以尝试解决：

• 统计词频
• 字符串模式匹配
• 最长回文子串

6.2 数据结构选择

根据问题特点选择最优结构：

• 频繁插入删除：链表
• 随机访问：数组
• 动态增长：vector

6.3 竞赛技巧

1. 先写伪代码理清思路
2. 模块化编程（如单独写reverse函数）
3. 使用防御性编程处理边界条件