信息学奥赛刷题笔记：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;
}

性能对比分析：

1. 空间复杂度

   • 二维数组：O(n*m)，n为单词数，m为最长单词长度
   • string类：O(n*m)，但动态分配更灵活
   • 直接遍历：O(1)，仅需存储原始字符串

2. 时间复杂度

   • 三种方法均为O(L)，L为字符串总长度
   • 直接遍历法减少了中间存储步骤，实际运行可能更快

3. 适用场景选择

   • 需要后续处理单词：选择前两种
   • 仅需输出结果：优先考虑直接遍历
   • 内存严格受限：直接遍历最优

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]
}

优化建议：

1. 对于固定字符集（如仅小写字母），可考虑位操作优化
2. 在性能关键场景，直接指针操作可能比数组索引更快
3. 使用 reserve() 预分配string内存减少重分配开销
4. 考虑使用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类解法代码简洁，适合快速开发；直接遍历法则在空间效率上无可匹敌。理解每种方法的优劣，才能在比赛中根据题目特点做出最佳选择。