这道题我印象太深了。每年准备北大计算机考研复试的同学基本都会在OJ上撞见它——题目编号3405名字叫“W的密码”。字符串长度不超过100三个移位参数输出变换后的结果。听起来像个五分钟能写完的签到题但真正动手做的时候不少人会在分组下标、移位取模、多组输入这几个地方翻车。我当年第一次做这题的时候也被“循环右移”这个表述坑过后来在论坛上看到好几个人问同样的问题才知道这是题目翻译导致的经典歧义。今天就把这道题的完整思路、实现细节、常见坑一次讲透不管你是刚开始刷机试还是准备冲刺复试这篇都值得收藏。1. 这道题到底在考什么先读懂题面1.1 题目规则梳理先冷静把题目规则拆开看。输入数据是这么构成的每一组测试数据包含一个字符串以及三个整数a、b、c。字符串由字母和数字等字符组成长度不超过100。a、b、c分别表示对三组字符进行循环右移的位数。当a、b、c同时为0时整个输入结束。关键规则有两条。第一条是分组规则。字符串中的字符按位置从1开始计数第1、4、7、10...个字符属于第一组第2、5、8、11...个字符属于第二组第3、6、9、12...个字符属于第三组。说白了就是把整个字符串按“位置模3”分成三个子序列。第二条是移位规则。第一组中的字母循环右移a位第二组中的字母循环右移b位第三组中的字母循环右移c位。这个“循环右移”是凯撒密码式的位移也就是每个字母独立在字母表里向后移动指定位置超过末尾就从开头继续。比如a右移1位变成bz右移1位变成a。大写字母在大写字母表里循环小写字母在小写字母表里循环。数字、标点这类非字母字符保持原样。1.2 容易被绕晕的三个点第一个坑是分组下标的起点。题目说的是第1、4、7个字符属于第一组但写代码时数组下标从0开始。很多新手直接拿i%3来分组却忘了对应关系下标0、3、6才是“第1、4、7个”。换句话说第一组对应的是i%30第二组对应i%31第三组对应i%32。用错了分组顺序整个输出就全错位了。第二个坑是“字母循环右移”的理解。我见过有人把题目理解成“每组字符序列整体向右轮转”——比如第一组是aXc右移1位变成caX。这不是本意。原题的规则是每个字母自己在字母表里向后移动非字母不参与移动也不参与计数。这种歧义大部分来自网上中文题面翻译不精确后来在北大OJ的原题语境里默认就是逐个字母做凯撒位移。第三个坑是参数a、b、c可能很大。字母表一共26个字母所以移动26位等于没动移动27位等于移动1位。如果直接拿超大整数去算(char bigNum) % 26很容易越界。正确做法是先把步数对26取模再参与计算。1.3 多组输入和结束条件还有一个很容易在考试时突然卡住的点输入是多组数据且以“a0 b0 c0”作为结束标志。每组数据是“一行字符串 一行三个整数”的结构。正常用cin str读取字符串没有问题但如果题目里字符串可能包含空格就得改用getline。北大机试通常不会在字符串里塞空格不过我还是建议你养成用getlineignore的习惯后面会专门讲这个坑。2. 整体设计思路与方案选型2.1 直接遍历法最符合直觉的做法这题最直接的思路就是遍历原字符串对每个字符判断它属于第几组然后调用一个移位函数处理它。以0下标为例i % 3 0属于第一组使用参数ai % 3 1属于第二组使用参数bi % 3 2属于第三组使用参数c。对每个字符先判断它是不是字母如果是就根据它属于第几组做对应的凯撒位移不是字母就直接保留。这种做法的优势是逻辑简单不需要额外的存储空间时间复杂度O(n)空间复杂度O(1)。原题字符串长度不超过100性能完全不是问题。2.2 分组取出再放回法另一种常见思路网上还有一种解法先把第一组、第二组、第三组的字符分别取出来放到三个临时数组里然后对每个数组中的字母进行移位最后再按原位置放回去。这个思路在逻辑上更贴近题面描述但实现起来多了一步“放回”操作稍不留神就会把位置搞混。比如你用一个数组保存了所有属于第一组的字符位置移位之后又得遍历这个位置数组把修改后的字符填回原字符串容易多写不少代码。我个人更推荐第一种直接遍历法。既然可以一次扫描解决问题就不必引入额外结构徒增风险。机试场上时间紧代码越短越不容易出bug。2.3 复杂度分析和边界条件时间复杂度自然是O(n)这里n是字符串长度。对每个字符只做常数次判断和一次赋值哪怕字符串长度拉满到1000甚至10000也毫无压力。边界条件值得提前想清楚字符串为空时循环不执行直接输出空行a、b、c为0时输出原字符串原样字符串中全是数字或标点没有任何字母所有字符保持原样输出字符串长度不足3时比如长度为1那么只有下标0属于第一组其他组没有字符程序依然正常工作。这些边界情况虽然简单但往往就是测试数据里最阴人的部分。2.4 移位函数的核心逻辑移位函数是整个程序的核心代码很短但要注意细节char shift(char ch, int k) { k % 26; if (ch a ch z) { return a (ch - a k) % 26; } if (ch A ch Z) { return A (ch - A k) % 26; } return ch; }这里先用k % 26把步数压缩到0到25避免后面计算数值溢出。然后判断大小写字母用字符减去基准字符得到相对偏移加上步数后对26取模再加回基准字符。非字母直接返回原字符。好多新手会问为什么不能直接ch k再加判断因为a的ASCII码是97z是122如果ch是zk是1直接相加得到123这个值对应的是{不是a。所以必须用相对偏移的方式处理。3. 完整代码实现C版与逐段讲解3.1 基础版代码直接读取字符串下面这段代码适合题目明确说明字符串不含空格的情况。它是机试里最稳妥的写法简单直接#include iostream #include string using namespace std; char shift(char ch, int k) { k % 26; if (ch a ch z) { return a (ch - a k) % 26; } if (ch A ch Z) { return A (ch - A k) % 26; } return ch; } int main() { string str; int a, b, c; while (cin str a b c) { if (a 0 b 0 c 0) { break; } for (int i 0; i (int)str.size(); i) { if (i % 3 0) { str[i] shift(str[i], a); } else if (i % 3 1) { str[i] shift(str[i], b); } else { str[i] shift(str[i], c); } } cout str endl; } return 0; }这段代码有个细节值得注意while (cin str a b c)一次性读取字符串和三个整数。如果遇到文件结束或者读取失败cin会返回false循环自动结束。这样即使没有0 0 0结束标志也能安全退出。3.2 支持空格的进阶版代码如果你在OJ上遇到字符串可能包含空格的题目就得换一种读取方式。典型写法是#include iostream #include string using namespace std; char shift(char ch, int k) { k % 26; if (ch a ch z) { return a (ch - a k) % 26; } if (ch A ch Z) { return A (ch - A k) % 26; } return ch; } int main() { string str; int a, b, c; while (getline(cin, str)) { cin a b c; cin.ignore(); if (a 0 b 0 c 0) { break; } for (int i 0; i (int)str.size(); i) { if (i % 3 0) { str[i] shift(str[i], a); } else if (i % 3 1) { str[i] shift(str[i], b); } else { str[i] shift(str[i], c); } } cout str endl; } return 0; }这里的关键是cin.ignore()。cin a b c读完三个整数后行尾的换行符还留在输入缓冲区里如果不用ignore把它丢掉下一轮getline就会读到一个空行导致程序逻辑错乱。这是新手最容易踩的坑。3.3 为什么建议用int(str.size())做类型转换str.size()返回的是size_t类型本质是unsigned long long之类的无符号整数。如果字符串长度为0i (int)str.size()中的i是int两者比较没问题。但如果直接写str.size() - 1这种表达式在字符串为空时会出现无符号整数下溢得到一个巨大的数循环就乱了。我在代码里习惯写(int)str.size()就是提前把这个隐患掐掉。虽然本体的for (int i 0; i str.size(); i)在很多编译器下也能正常跑但既然有更稳的写法为什么不直接用呢。3.4 验证样例拿最简单的样例验证一下输入abcabcabc 1 1 1字符串abcabcabc三个参数都是1。按下标0到8遍历下标0是a属于第一组移位1位变成b下标1是b属于第二组移位1位变成c下标2是c属于第三组移位1位变成d下标3是a属于第一组变成b以此类推。输出就是bcdbcdbcd再测试一个包含数字的用例输入a1b2c3 1 1 1下标0是a第一组变成b下标1是1第二组非字母保持1下标2是b第三组变成c下标3是2第一组非字母保持2下标4是c第二组变成d下标5是3第三组非字母保持3。输出b1c2d3这两个自测用例能覆盖字母移位和非字母保持两种核心行为建议你在本地把它跑通再说。4. 常见错误与调试实录4.1 分组下标错位一错错一排这是我看到过最多的错误。因为字符串在程序里从下标0开始新手很容易把第一组写成i%31结果整个字符串的处理全部错位。比如字符串abcdef正确分组应该是原字符下标正确分组错误分组如果i%31当第一组a0第一组第三组b1第二组第一组c2第三组第二组d3第一组第三组一眼就能看出一旦分组起点错了每个字符用的移位参数全都不对输出面目全非。调试的时候如果发现输出结果规律性地“整体错位”优先检查分组判断条件。4.2 移位参数没有先取模a、b、c的值可能非常大比如10000。如果不先对26取模在做(ch - a k)时k的数值会很大虽然char加int会自动提升为int但最后对26取模的结果不会错问题是有些编译器或者后续处理可能出现意外。更重要的是如果某个版本的实现里你直接对char类型做运算再赋回char可能因为溢出得到负数最后变成乱码。我在实际写代码时习惯在shift函数第一行就写k % 26这属于防守型编程成本几乎为零却能避免很多隐蔽问题。4.3 多组输入的读取死循环用while (getline(cin, str))配合cin a b c时如果忘记cin.ignore()第一次读取正常第二次getline会直接读到上一次残留的换行符返回一个空字符串然后整组数据全部错乱。更严重的可能造成死循环程序一直空转。有个简单的验证方法在本地调试时输入两组数据观察第二次读到的str是不是空串。如果是就说明缓冲区的换行符没清干净。4.4 非字母字符处理遗漏有个不太容易想到的错误是有的同学写了移位函数但只处理了小写字母忘记大写字母。或者反过来。题目明确说了字符可能包含数字且大小写字母都可能出现所以移位函数必须同时覆盖a-z和A-Z两个区间。我自己在机试中遇到过一个大写字母测试点当时因为只处理了小写字母WA到怀疑人生。后来养成了习惯凡是跟字符相关的题目读题后第一件事就是确认大小写是否都要处理。4.5 常见问题速查表症状可能原因排查思路输出整体错位分组判断的模数起点写错打印i和i%3对比题目分组字母移位结果乱码移位参数未取模或字符运算溢出检查shift函数第一行是否有k%26第二组测试数据读取错误缺少cin.ignore()在cin a b c后加cin.ignore()大写字母没变移位函数漏掉大写分支检查是否同时处理A-Z数字或标点被改动非字母分支处理错误确认非字母原样返回5. 举一反三这类题的变形与刷题建议5.1 和本题相似的机试题目这道题是字符串处理类题目里的经典代表。和它相似的题还有几类纯凯撒密码题给定一个字符串和一个偏移量把所有字母统一移位分组加密类把字符串按一定规则分组每组用不同参数处理字符串原地修改类要求在不增加额外数组的情况下完成字符替换。这些题核心考点都一样字符ASCII操作、取模运算、下标映射、输入输出处理。把“W的密码”吃透这些题基本就是改改参数的事情。5.2 我在刷题时的一些习惯第一拿到题目先在草稿纸上手动模拟一个样例不要急着写代码。把分组、移位、非字母保留这些步骤在纸上过一遍很多逻辑错误在写代码之前就能暴露。第二写完代码后用几组边界数据自测包括空字符串、全数字字符串、只有一个字符的字符串、参数为0的情况。这些数据用不了几分钟但能帮你挡掉一半以上的WA。第三如果提交后WA不要盲目改代码。先构造一个自己能算出答案的小样例一步步跟踪程序输出定位第一个出错的字符再反向找原因。字符串处理题调试起来其实很快关键是别慌。5.3 推荐的学习路线如果你正在准备考研机试我的建议是把这类基础题放在刷题计划的第一周攻克。字符串处理、简单模拟、排序、查找这些基本功过了之后后面做图论、动态规划才会顺手。这道题完全可以作为热身题每天默写一遍直到不用看代码就能一次通过。我自己刷题多了之后慢慢发现一个规律机试场上真正卡住人的往往不是算法本身而是这种“明明看懂了题代码写出来却不对”的挫败感。而消除这种感觉的唯一办法就是把基础题练到形成肌肉记忆。“W的密码”就是值得形成肌肉记忆的题目之一。