信息学奥赛刷题笔记：OpenJudge NOI 1.7 27 单词翻转的三种解法（C++实现）

信息学奥赛刷题笔记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()函数通过交换首尾字符实现翻转注意在本地测试时控制台输入后需要按CtrlZ再回车来模拟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 i1; } } 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处理本地测试时使用CtrlZ(Windows)或CtrlD(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) { vectorpairstring, bool tokens; // string和是否为单词的标志 // 分词逻辑... for(auto token : tokens) { if(token.second) // 如果是单词则翻转 reverse(token.first.begin(), token.first.end()); } // 重组字符串... }在实际比赛中选择哪种方法取决于具体问题的约束条件和个人的编码习惯。二维数组解法虽然略显原始但在某些内存受限的嵌入式环境中可能是唯一选择string类解法代码简洁适合快速开发直接遍历法则在空间效率上无可匹敌。理解每种方法的优劣才能在比赛中根据题目特点做出最佳选择。