如果你在百炼OJ刷题看到题号2818、题目名“密码”的时候千万别急着写一个while(k--)就开始暴力模拟。我第一次做这题就是这么交的WA了两次又TLE了一次老老实实回来画了一下午置换图才算搞明白。这道题表面是字符串处理内核其实是组合数学里的置换群考点非常经典循环节轮换。不少人觉得它只是“某个OJ上的小题”但同样的套路翻个马甲出现在很多比赛和面试题里。这篇文章就把这题的来龙去脉、数学原理、完整C实现和所有我踩过的坑一次性讲透。1. 先别急着模拟2818密码题到底考什么1.1 题目版本与输入输出形式我手边的版本大概是这样的第一行给一个正整数n表示密钥长度第二行给n个整数是一个1~n的排列p代表加密规则第三行给一个字符串s长度可能小于n不足的部分用空格补足第四行给一个整数k表示加密次数。输入一直持续到n 0结束。加密规则是每加密一次把当前字符串的第i个字符移动到新字符串的第p[i]个位置上。重复k次之后得到密文现在题目给的是这个密文和k要求还原出原始明文。不同OJ上的描述可能略有差异有的把p[i]解释成“新串第i位来自原串第p[i]位”有的把输入顺序调换一下还有的会明确说“不够n位补空格”。但核心都一样给你一个置换、一个次数、一个最终字符串求初始字符串。如果你只是机械地“正向加密”那就完全反了。做题第一步永远是先搞清楚方向密文是“加密k次后的结果”我们要求的是“加密前的样子”所以对密文要做的是逆置换k次。1.2 为什么“while(k--)暴力模拟”会超时很多新手看到这个题的第一反应是直接模拟啊每次开一个新字符串按p重新排列循环k次就完了。这在n和k都很小的时候确实没问题。但这个题的恶心之处在于k的范围非常大常见数据可以给到2^31甚至更大而n虽然只有几十到一百多乘起来也完全不可接受。我试过直接模拟最坏情况下一个n80、k20亿的用例循环次数是1600亿别说超时程序直接跑飞了。这个题真正想考察的点不是“你会不会写循环”而是“你能不能发现周期”。打个比方时钟上有12个格子你拨了k下最终位置其实只取决于k mod 12跟k本身是100还是1000没关系。加密也一样字符串的位置是有限的置换来置换去过了一定的步数一定会回到原点。这个“一定的步数”就是循环节的长度。所以关键不是把k次都走完而是把k折叠到一个更小的量上这就是组合数学中置换、循环节要解决的事情。2. 置换、循环节与“组合数学”视角2.1 把加密操作看成置换数学上1~n的一个排列就是一个置换它定义了一个从位置集合到自身的一一映射。假设我们用下标i表示原位置p[i]表示加密后该字符去的新位置那么加密一次就可以写成函数f(i) p[i]。一个字符初始在第i位加密一次到f(i)加密两次到f(f(i))加密k次到f^k(i)。题目给的是字符串经过f^k作用之后的结果要求的是作用之前的结果这等同于对密文的每个位置做f^{-k}。排列和一般的映射最大的区别在于它是可逆的双射。这意味着不管操作多少次每个位置始终会被一个字符占着不会出现两个字符挤到同一个位置或者某个位置空掉的情况。这个性质保证我们可以在位置上自由地往前追、往后推。你可以把f想象成一张地图上的单向路每条路上一定有人走且每个路口只进一个人因为它是排列所以整张图必然是由若干个互不相交的环组成的不存在“岔路”和“死胡同”。2.2 循环节轮换拆解过程既然地图是由环组成的那么从任意一个位置出发沿着f一直走最终一定会走回出发点。这一圈上经过的所有位置就叫一个循环节也叫轮换cycle。整个置换可以被拆成若干个互不相交的循环节它们互不干扰字符只会在自己所在的环里转圈。举个例子假设n 6排列为p [2,4,6,1,3,5]我们从下标1开始走1 - 2 - 4 - 1所以(1, 2, 4)是一个长度为3的环。再从下标3开始走3 - 6 - 5 - 3所以(3, 6, 5)是另一个长度为3的环。拆环的方法很简单维护一个vis数组遍历所有位置如果当前位置没被访问过就沿着p一直走把经过的位置记下来直到回到起点为止。这样每个位置都会恰好属于一个环。这步看起来不起眼却是整个算法的地基。为什么要拆环因为在一个长度为len的环上走len步后所有字符都会回到原位也就是说k次置换等价于k mod len次。环越长优化效果越明显即使每个环长度不一样也可以分别处理这样整体的复杂度就从O(k*n)降到了O(n)。2.3 加密次数如何“折叠”到环上把一个环上的位置按顺序记下来比如ring [a0, a1, a2, ...]其中a0经过一次置换到a1a1到a2以此类推。那么在环上的任意一个位置ai经过t次置换后会落到a[(i t) % len]。反过来从位置ai往回追溯t次它来自a[(i - t len) % len]。这正是我们需要的已知密文最终在位置ai要求明文原来在哪个位置答案就是往前逆着置换方向走k mod len步。这里有一个很容易混淆的点方向。如果你定义的p[i]是“原位置i去新位置p[i]”那么从密文回溯明文是逆着p走如果你定义的是“新位置i来自原位置p[i]”那回溯方向就反过来。我自己的习惯是先用非常小的样例手算一遍确认代码里的加法和减法方向是否跟我的定义一致再继续写。手算样例时我会固定用一个n4的例子p [2,4,1,3]明文abcd加密一次后每个字符的去向是1-2、2-4、3-1、4-3得到密文cadb。如果你按这个例子推一遍就会发现无论是环的拆解还是回溯的偏移量都能对得上。3. 完整C解法与代码实现3.1 算法流程四步走直接用上面的数学推导代码思路非常清晰读入n、排列p、字符串s、加密次数k。注意p是1基的存进vector时全部减1转成0基下标。拆环。用一个visited数组标记每个位置是否已被划分到某个环里。对每个未访问的位置沿着p走下去得到一个环同时记录每个位置在环内的序号第几步。对密文的每个位置i找到它所在的环以及它在环内的序号pos。明文原位置等于环上向前数k % len步的位置。把密文s[i]放到算出来的明文字符串的那个位置上最后输出。如果题目的加密定义是反的也就是“新串第i位取自原串第p[i]位”那第3步的方向就要反过来。我的建议是代码里只写一个方向的逻辑然后用样例验证不要去背“正向用加、逆向用减”的口诀因为不同题目和不同人的写法会互相矛盾。逻辑清晰比口诀重要得多。3.2 代码与注释我给出一个能过大多数OJ的C实现下标从0开始方便字符串操作。代码里注释写得很细可以直接抄作业。#include bits/stdc.h using namespace std; int main() { int n; while (cin n n) { vectorint p(n); for (int i 0; i n; i) { cin p[i]; --p[i]; // 1基下标转0基 } // 字符串可能含空格所以用getline读一整行 string s; cin.ignore(); // 先吃掉上面数字行末尾的换行符 getline(cin, s); int k; cin k; // 把字符串长度补到n不足部分补空格 if ((int)s.size() n) { s.append(n - s.size(), ); } // 拆环 vectorint ringId(n, -1); // 每个位置属于哪个环 vectorint posInRing(n, -1); // 每个位置在环内的序号 vectorvectorint rings; // 存储所有环 for (int i 0; i n; i) { if (ringId[i] ! -1) continue; int cur i; vectorint ring; while (ringId[cur] -1) { ringId[cur] (int)rings.size(); posInRing[cur] (int)ring.size(); ring.push_back(cur); cur p[cur]; // 沿着置换走 } rings.push_back(ring); } // 根据密文还原明文 string ans(n, ); for (int i 0; i n; i) { int rid ringId[i]; int len (int)rings[rid].size(); // 密文位置i要回溯到明文位置 // 在环上往前数 k % len 步因为求的是之前的来源 int step (posInRing[i] - (k % len) len) % len; int origPos rings[rid][step]; ans[origPos] s[i]; } cout ans \n; } return 0; }这段代码的复杂度是O(n)因为每个位置最多被访问两次一次拆环一次还原。即使k 2147483647也只是做个取模运行速度飞快。实测n80、k20亿的极限数据运行时间在1毫秒级别暴力模拟根本没法比。3.3 两个容易写反的方向细节第一个坑step的加法和减法方向。我在代码里用的是posInRing[i] - (k % len)含义是“从密文当前位置回溯到加密前的来源位置”。如果你在测试样例时发现输出正好是某种循环平移别急着改取模先检查方向的加减号。用我上面给的abcd示例p [2,4,1,3]k1密文是cadb。手动跑一下代码位置0字符c所在的环是[0,2,1,3]还是[0,1,2,3]这取决于p的具体值。所以强烈建议在每个题里都先手算一遍小样例再对照代码输出确认方向。第二个坑下标从1转0后p[i]的含义容易搞混。有人喜欢保留1基下标做数组字符串用的是0基最后转换时漏掉一个减一样例过了大数据全错。我的做法是一开始就把p全部减1让整个代码统一到0基体系这样逻辑最不容易出错。4. 常见错误与现场排错记录4.1 读入字符串中的空格这个题的地狱级坑密文可能包含空格。很多同学用cin s读第三行结果一遇到空格就断开了只有前几个字符被读进去下面的整数k又读错整个输入流直接乱掉。正确做法是用getline(cin, s)读整行同时小心cin n和cin k后面残留的换行符。常见搭配是读完排列后先cin.ignore()再getline。如果题目有多组数据还要注意每组之间的空白行必要时用多个getline把多余空行吃掉。这个细节看起来小考场上卡十分钟一点都不意外。4.2 下标从1还是0我说过很多次但每次重写这题还是会有人犯。请记住题目输入的排列一定是1~n而字符串的下标是0~n-1不统一就会错位。正确的转换是读到x后立刻执行--x让p[i]表示“0基的原位置i去0基的新位置p[i]”。转换完以后整个代码里不要再出现任何“加1再还原”的操作。如果你在拆环时用cur p[cur]最后还原时发现访问了越界位置通常就是这里忘了减1或者多减了一次。4.3 k取模千万别在循环内乱改有人会用这种写法在外面算好k % n然后在每个环里再循环k次。这在小数据下没毛病但存在两个隐患一是n不是所有环长度的最小公倍数一个环的周期只有它自己的len不是全局的n二是如果你把k取模后再拿去遍历恰好这个k又很大虽然取模后可能变小了但依然不是最简做法。正确姿势是在每个环的内部单独用k % len作为偏移量而不是把k全局改掉。另外k建议用long long读入防止个别变态数据把int撑爆。4.4 输出明文空格怎么办如果原字符串本身不足n题目会要求补空格加密那么还原出来的明文长度也是n末尾可能有空格。很多输出判断会忽略行尾空格所以一般直接输出ans再加换行即可。但如果题目要求“输出原始字符串不输出补位空格”或者“遇到第一个空格就结束”你就要根据题意把末尾空格去掉。这个没有统一标准我每次做这道题都会看一遍输出样例确认末尾空格的行为后再决定是否需要erase。4.5 拆环时死循环的坑拆环如果用while (cur ! start)这种写法在一个环已经被访问过的情况下可能陷入死循环。更稳妥的判断条件是while (vis[cur] 0)进循环后立刻标记。我的代码里用的是while (ringId[cur] -1)因为ringId同时兼任访问标记和环编号一个数组顶两个用。如果你选用bool vis[]记得拆完一个环后环里所有点都要标记不然会重复访问答案错乱。还有一点p是排列不会出现多个点指向同一个点的情况所以cur p[cur]必然是一条闭合的链不存在“走到已经访问过但不是本环起点”的问题放心用。5. 同类题与扩展加密题背后的算法套路5.1 一个可复用的“置换幂”模板这题本质上是要求“置换P的k次幂”对字符串的作用反过来求原串。这类问题有一个非常通用的模板拆环 - 记录每个位置在环内的序号 - 根据k % len计算最终/原始位置。不只是字符串任何“按排列操作重复K次”的数组问题都可以用这一套。比如有一个数组每次按照某个排列重新洗牌问洗k次后的结果或者知道k次后的结果求原数组都是同样的套路。我刷题时会把这段拆环代码单独存成一个函数遇到相似题直接复制省得每次重写还容易写错。5.2 从“密码题”到字符串题目其实百炼OJ 2818这道题几乎可以对应POJ上的1026 Cipher两者思路完全一样。如果你刷完这题还想继续巩固可以把 POJ 1026 也做一遍感受一下同样的题换个壳之后有什么不同。再往深走如果加密加上了字母替换比如凯撒密码那就可以拆分处理先根据置换还原位置再根据替换规则还原字母顺序不能乱。很多字符串题都是这种“位置变换 字符变换”的组合把它们拆开分析每个部分都变得简单。我个人的建议是做完这题一定要把“置换幂”这个套路吃透因为它在算法题里的出场率极高尤其是考排列、分组、循环的题目几乎都能套上。最后说一点实战经验遇到这种“重复操作很多次”的题第一反应不要是硬循环而是找周期、找循环节、找不变量。刷题练的其实是这种建模能力。百炼2818的密码题虽然看起来只是个字符串加密还原的模拟题但它教会的置换拆环思想会在后面很多题目里反复用到。我自己后来做矩阵快速幂、状态压缩、循环节优化的题目时都会想起这道题。拿它入门置换群性价比非常高。