如果你正在刷洛谷的入门题单那大概率会遇到 P1914 小书童——凯撒密码。这道题在很多人眼里就是一道过了就行的送分题但我在讨论区见过不少同学因为方向搞反、取模写错、读入姿势不对硬生生WA了四五发才过。这篇文章打算用一篇完整题解的方式把这题讲透——包括题目到底要你做什么、凯撒密码背后的数学本质、三种语言的实现以及我实际提交中总结的避坑经验。不管你是刚学C的OI新手还是想快速过一遍思路的老选手都能在这篇里找到有用的东西。1. 题目到底在问什么密文、明文与解密方向1.1 先读懂加密规则凯撒密码简单说就是把字母在字母表里平移若干位。题目给出的规则是将一个小写字母用字母表中它后面的第 k 个字母代替。k1 时a 变成 bb 变成 cz 变成 a。到这里都没问题问题出在后面这句输入给的是加密后的字符串要求输出加密前的字符串。也就是说我们要做的不是继续往后走而是往后退 k 位——把输入当成密文还原出明文。很多第一次做这道题的人看到凯撒密码四个字就条件反射地写加密方向a→bb→cc→d。样例输入 k1、字符串 abc他自信地输出 bcd提交WA沉默。这类问题几乎每年都会在讨论区出现。1.2 用样例反推解密方向样例会告诉你真相。P1914 的样例输入是1 abc样例输出是zab我们验证一下把zab当成明文按题目加密规则走一遍——z 后面的第 1 个字母是 aa 后面的第 1 个是 bb 后面的第 1 个是 c加密结果正好是abc。这说明逻辑闭合了任务是输入密文 → 输出明文。所以记住一句话这道题是解密不是加密。每次动手写之前先把题目里的加密后加密前圈出来确认自己要往哪个方向走。这一步花不了十秒钟却能帮你避开最蠢的那种 WA。1.3 这道题真正在考什么很多人觉得这题考的是字符串遍历其实不是。它真正考的是两件事把字符映射成整数来参与运算的能力对环形回绕的直觉——字母表不是一条直线而是首尾相接的圆环。这两点在后面所有字符串模拟题里都会反复出现。P1914 之所以被放在入门题单靠前的位置不是因为它算法难而是因为它能帮你建立一套处理字母环的固定思维模板。模板搭好了后面做 ROT13、维吉尼亚密码、各种移位加密变种都是套公式的事。2. 核心思路推导字母环上的位移与取模2.1 把字母表想成一条环形跑道把 26 个小写字母按顺序写成一圈a 在最上面顺时针依次是 b、c、d……一直到 z然后 z 再指向 a。现在每个字母往后数第 k 位就是在这条环形跑道上顺时针走 k 步往前数 k 位就是逆时针走 k 步。计算机不认识环形字母表它只认数字。所以第一步是把字母变成编号a 是 0b 是 1c 是 2……z 是 25。往后走 k 步就是编号加 k往前走 k 步就是编号减 k。一旦编号跑出 0~25 的范围就用取模运算把它拉回来。这里有一个特别重要的直觉环形结构 取模是信息学里一对绑定的搭档。以后你见到循环队列、约瑟夫环、数组循环移位本质都是同一件事——在固定长度的环上做加减然后用取模统一收口。2.2 公式是怎么一步步推出来的解密时对于密文字符 s[i]先转成编号idx s[i] - a往前挪 k 步newIdx idx - k处理回绕newIdx (idx - k) % 26问题来了在 C 和 Java 里负数取模的结果仍然是负数。比如(-1) % 26数学上我们想要的是 25但 C 会给你 -1。所以要用修正版公式newIdx (idx - k 26) % 26为什么加 26因为加了一个模数在模 26 的意义下相当于加了 0结果不会变。但它能把括号里的负数拉到正区间idx 在 0~25 之间k 在 0~25 之间idx - k 最小是 -25加上 26 后最小是 1正数取模百分百安全。如果 k 可能很大比如 k27最好先k % 26。为什么因为字母只有 26 个逆时针绕一整圈回到原点27 和 1 在模 26 意义下完全等价。先取模后面所有减法都被限制在 -25~25 范围内加 26 就足够修正了。2.3 字符与数字的双向转换这是本题第二个基本功。字符 a 在 ASCII 表里是 97z 是 122。但代码里一律写s[i] - a不要写s[i] - 97。原因有两个一是用字符常量表意更清楚看代码的人一眼就懂你在算字母编号二是只要当前字符集包含连续排列的小写字母这个写法就永远成立。你写 97 也没错但别人 review 你的代码时会多绕一下。反向转换是newIdx a把编号变回字符。这里要注意计算过程中得到的结果必须先保证在 0~25 区间再转成 char否则会得到不可打印的 ASCII 符号。很多乱码输出就是这么来的。2.4 边界位移速查表以 k1 为例几个关键位移关系密文idx解密公式 (idx-126)%26明文a0(0-126)%26 25zb1(1-126)%26 0ay24(24-126)%26 23xz25(25-126)%26 24y这类边界表格很值得自己动手推一次。以后遇到位移类题目不用每次从头想直接套公式就行。3. 完整C实现代码、注释与读入细节3.1 最简AC代码下面是本题最经典的 C 写法也是我推荐初学者优先掌握的版本#include bits/stdc.h using namespace std; int main() { int k; string s; cin k s; k % 26; for (char c : s) { c (c - a - k 26) % 26 a; } cout s endl; return 0; }提交到洛谷 P1914 可以直接 AC。这份代码短、清晰、没有多余分支适合作为字符移位的模板记忆。3.2 逐行拆解每个字符经历了什么cin k s;能一次性读入整数和字符串靠的是题目保证第二行是连续小写字母、不含空格。很多读入问题都是因为题目数据格式和你想的不一样读这一行前先看题面。k % 26;这行是防御性写法。题目虽然写了 0k26但有些平台数据并不严格按照题面来或者你拿这段代码去改别的题k 可能搞很大。先取模后面所有逻辑就不会因为 k 溢出而出错。for (char c : s)中用了引用遍历的同时直接修改原字符串。如果不加引用这里拿到的是字符副本改完原字符串一点变化都没有。这个细节看起来小实际犯的人不少。核心行c (c - a - k 26) % 26 a;从左往右看c - a把字符转编号- k向前解密 26消除负数% 26回绕 a转回字符。四步一气呵成。3.3 更稳妥的读入方案如果你担心数据里有空格或者想在任何场景下都用通用写法可以用getline读第二行int k; string s; cin k; cin.ignore(); // 吃掉第一行末尾的换行符 getline(cin, s);注意cin k读走整数后换行符还留在输入缓冲区里。如果直接getline(cin, s)读到的会是一个空串。所以cin.ignore()不可省略。这个吃掉换行符再读整行的组合在后续很多字符串题目里都会用到建议现在就记住。3.4 复杂度与代码风格时间复杂度 O(n)空间复杂度 O(1)n 是字符串长度。本题 n 最大只有 100随便跑。但这份算法真正的价值是哪怕字符串长度变成 10^6它依然轻松胜任。竞赛场景下我建议给 main 函数开头加上两行ios::sync_with_stdio(false); cin.tie(0);这能加速 C 的输入输出。本题数据量小加不加无所谓但养成本能反应后以后遇到大输入量题目会省下不少时间。4. Python和Java的对照实现同一个公式三种语言4.1 Python版本负取模天生友好Python 的取模运算对负数很友好(-1) % 26的结果是 25而不是 -1。所以 Python 代码可以少写一个 26k int(input()) s input().strip() ans .join( chr((ord(c) - ord(a) - k % 26) % 26 ord(a)) for c in s ) print(ans)这里需要注意的是input().strip()。Python 的input()会去掉行尾换行但字符串首尾可能有多余空白strip()一并清掉更保险。另外ord(c) - ord(a)和chr(...)是字符与整数的双向转换等价于 C 里的c - a和... a。4.2 Java版本StringBuilder别忘掉Java 的%行为和 C 一致负数取模还是负数所以需要保留 26import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int k sc.nextInt(); String s sc.next(); StringBuilder sb new StringBuilder(); for (char c : s.toCharArray()) { char dec (char) ((c - a - k % 26 26) % 26 a); sb.append(dec); } System.out.println(sb); } }用StringBuilder而不直接拼接字符串是个很容易被忽略的坑。Java 里String是不可变的每次都会创建新对象字符串一长性能就崩。StringBuilder原地操作是竞赛和机考的标准做法。4.3 三种语言取模行为对照表达式CJavaPython(-1) % 26-1-125是否需要手动 26需要需要不需要这个表值得存一下。同一个数学公式在不同语言里跑出来的结果可能完全不同。你背的模板是 C 的到了 Python 里可能反而会想怎么不加 26 也对 知道背后的原因写起来就不会慌。4.4 不同场景下的语言选型建议我的建议是刷信息学竞赛题主用 C因为比赛环境对 STL 和性能支持最好想快速验证思路、写草稿用 Python代码量短、心智负担小如果是面试或机考场景Java 的Scanner和StringBuilder组合要练熟。三种语言不是对立的它们是同一套思维的不同表达。5. 我实际提交中踩过的三个坑5.1 方向搞反样例输出zab不是bcd这是最常见的错没有之一。原因前面已经讲过这里只说我自己的一个习惯看完题目先不写代码把样例在心里走一遍。题目说输入abc、k1我就在草稿纸上写这是一个密文要还原。于是 z←aa←bb←c输出zab。这个习惯看起来笨但它能帮你开局就排除一堆低级错误。方向搞反的代码样例跑出来就是 bcd一眼就能看出来不对根本不需要提交。5.2 负数取模输出一串反引号错误写法长这样c (c - a - k) % 26 a;如果c是 ak是 1那么(0 - 1) % 26在 C 里是 -1不是 25。a 的 ASCII 是 9797 加上 -1 等于 96正好是反引号 的 ASCII 值。于是你的输出里会出现一串莫名奇妙的符号而不是 z。修复方法就是前面反复强调的 26。我第一次写这道题时就栽在这里当时对着反引号看了半天没反应过来后来手动推了一遍 ASCII 表才恍然大悟。这个坑一旦踩过这辈子都不会忘。5.3 偏移量越界题目没写的隐藏边界题目说 0k26所以很多人干脆不处理 k。但如果你拿这段代码去改变种题或者平台数据里混了一个 k30那就有问题了。比如 k27idx - 27 26是负数C 取模等于 -1直接翻车。防御办法很简单在循环前加一句k % 26;如果遇到更变态的负偏移量数据可以写成k (k % 26 26) % 26;这两行代码能把任何整数 k 统一压缩到 0~25 的安全区间。虽然 P1914 用不上但作为模板的一部分我建议直接写上一劳永逸。5.4 提交前的自测习惯我的个人习惯是提交前跑三组数据样例、边界、极值。具体到这道题样例1abc期望zab边界1az期望zy极值25abc期望zab不对k25 往前挪25位a 向前25位 字母 b这里要小心往前挪25位等于往后挪1位我不在这里把所有期望值列全因为你自己推一遍效果更好。重点是用边界数据验证回绕逻辑用极值大 k 验证取模逻辑。三组全过这道题基本就稳了。6. 从P1914延伸凯撒密码家族与其他环形位移题6.1 已知明文求密文加密方向的公式镜像如果题目反过来给定明文让你加密公式只要把减号改成加号c (c - a k % 26) % 26 a;加密和解密就是公式镜像一个向右走一个向左走。这也说明凯撒密码本身是对称的知道 k 就能加密也能解密。在竞赛里出题人经常把题目包装成输入明文输出密文你只要稍加变通就能应付。6.2 ROT13加密等于解密的特例ROT13 是 k13 的凯撒密码。因为 13 正好是 26 的一半在字母环上往右走 13 步之后再往右走 13 步就回到了原点。所以 ROT13 的加密操作和解密操作完全一样——同一个函数调用两次等于什么事都没发生。历史上有人在论坛用它隐藏剧透内容本质就是一个固定的移位。如果你理解了 P1914ROT13 就是一道改改参数就能 AC 的题。6.3 混合字符集大写、数字怎么办现实中的加密题目不会只考小写字母。处理思路是一样的只是基线不同字符集模数取编号小写 a-z26c - a大写 A-Z26c - A数字 0-910c - 0混合字符集时先用if判断当前字符的类型选定模数再套用同一个移位公式。这种分类型处理是字符串模拟题的标配思路P1914 是这条路的起点。6.4 维吉尼亚密码偏移量由密钥决定维吉尼亚密码是凯撒密码的进阶版不同位置的字符使用不同的偏移量偏移量由一个密钥字符串决定密钥字符的编号就是当前位的 k。理解了 P1914 后维吉尼亚密码的代码框架其实就是在循环中动态取 kk key[i % key.size()] - a; c (c - a - k 26) % 26 a;这个变种在很多进阶字符串题里出现。你会发现基础题的思维一旦内化进阶题只是加了一层变量而已。6.5 环形位移思维还能用在哪取模 环形这套组合绝不止字母加密这一处。数组循环移位、约瑟夫环、循环队列、时钟指针角度计算……本质都是把一条直线弯成环然后用取模处理越界。一道板子打下去后续碰到的环状问题都会有似曾相识的感觉。这也是我坚持把 P1914 讲这么细的原因——题不难但它背后那套思维值得你在心里存很久。最后再分享一个实操建议刷 P1914 的时候试着在白纸上亲手推一遍字母环 取模的完整过程再把 C 和 Python 两个版本各写一遍。这样做的效果比直接抄代码好十倍。等你以后遇到凯撒密码的变种题你会感激当初多花的这十分钟。