企业官网建设流程全解析

第一次在百炼OJ上刷到2818这道题时，看到标题“密码”两个字，我第一反应是它跟加密算法有关系，可能是凯撒密码或者简单的移位替换。点进去读题才发现，这其实是道非常经典的置换变换题：给定一条置换规则，让你把一段字符串反复变换k次，输出最终结果。这类题在OJ上难度不算高，但坑特别多——字符串可能带空格、变换次数k会很大、置换方向容易搞反，任何一个小问题都能让你Debug到怀疑人生。这篇文章就把这道题的完整思路、代码细节和排错经验都梳理一遍，给正在练“循环分解”和“置换”这类基础算法的同学做个参考。

1. 题目到底在考什么：一次置换的重复应用

1.1 从一个字符怎么跑到另一个位置讲起

先回到题目本身。题目会给你一个整数n，然后给出一组1到n的排列，比如p[1]、p[2]……p[n]，这组排列就是置换规则。接着给你一段待处理的字符串s，再给你一个变换次数k。你要做的，就是按照这条规则，把字符串连续变换k次，最后把变换结果输出来。

这里的“置换”可以理解成一种位置重排：原本在第i个位置的字符，经过一次变换后，会跑到第p[i]个位置上去。比如n等于3，p等于{2, 3, 1}，那字符串"abc"经过一次变换后，a从位置1跑到位置2，b从位置2跑到位置3，c从位置3跑到位置1，结果就是"cab"。

要注意的是，有些题目在描述置换方向时习惯反着写，也就是“第i个位置上的字符来自原串的第p[i]个位置”。这两种定义在数学上互为逆置换，实现出来的代码方向完全不同。我个人踩过这个坑，所以后面会专门讲怎么用一组小数据快速验证你的方向写没写反。

理解了“一次变换”之后，题目难度就落在“连续变换k次”上。如果只做1次变换，直接开一个临时数组循环赋值就行，三分钟搞定。但k一旦给到10^9，硬模拟就直接超时了。这也是这题真正想拉开差距的地方：你能不能识别出“重复变换”背后的数学结构，然后找到一个跟k无关、只跟n有关的解法。

1.2 模拟k次的代价与隐藏陷阱

很多同学第一反应就是写个双重循环，外层跑k次，内层对每个位置做交换。这种做法在n比较小、k比较小的时候没问题，但题目里k是可以给得很大的。假设n等于100，k等于10^9，外层循环10^9次，每次还要处理100个位置，哪怕编译器优化再猛，也是妥妥的超时。

更麻烦的是，连续做k次变换时，如果每次都完全重新复制一遍字符串，复杂度会叠加得很夸张。你可能会想，能不能每次只交换两个位置？但置换不是简单的两两交换，它可能把3个、5个甚至更多位置串成一个环，单纯两两换是描述不了这种结构的。

所以，这题真正的考点并不是“怎么模拟”，而是“怎么把k次变换压缩成一次计算”。这个压缩思路，就是我在下一节要重点拆解的循环分解法。刷题刷到一定量之后你会发现，凡是题目里出现“重复操作”“周期”“轮换”这类字眼，大概率都要往循环分解上想，这算是置换类题型的通用套路了。

1.3 哪些人适合先刷这道题

如果你正在准备算法竞赛，或者刚进入“数据结构与算法”的基础训练阶段，这道题非常适合作为置换环节的入门题。它不像KMP、归并排序那样需要背一堆模板，也不像动态规划那样需要很强的状态设计直觉，它考察的核心就是一个“找规律”的能力：你能不能把看似复杂的k次变换，化简成若干个循环内的简单旋转。

另外，这道题对代码基本功也有很好的检验作用。字符串的读入、空格的保留、数组索引从0开始还是从1开始、循环边界的处理，任何一个地方出问题都会导致WA。我见过不少同学算法思路完全正确，结果卡在读入上，折腾一晚上。所以这道题刷下来，你收获的不只是置换算法，还有对OJ输入输出细节的敏感度。

如果你是那种已经在刷排序算法、贪心算法，想换换思维方式的选手，也可以把这道题当个调剂。它的代码量不大，但能让你练到一种很多算法题都用得上的思想：分解成独立子结构，再分别处理。

2. 核心算法思路：循环分解与幂运算化简

2.1 把置换拆成互不相交的循环

要理解这道题的最优解法，得先认识置换的一个重要性质：任意一个置换都可以唯一分解成若干个互不相交的循环。所谓“互不相交”，就是每个位置只会出现在一个循环里，不会同时属于两个循环。

怎么理解循环呢？你可以把置换想象成一张“位置跳转图”：当前位置是i，按规则跳转到p[i]，再从p[i]跳转到p[p[i]]……一直跳下去，最终一定会跳回起点，因为位置总数是有限的，而且p是排列，不存在一个位置被两个位置同时指向的情况。

这样一个闭合的跳转路径，就构成了一个循环。比如p等于{2, 3, 1}时，1跳到2，2跳到3，3跳回1，所以{1, 2, 3}就组成了一个长度为3的循环。再比如p等于{2, 1, 4, 3}，那么{1, 2}是一个长度为2的循环，{3, 4}是另一个长度为2的循环。

找到这些循环的办法很简单：开一个访问标记数组，从1到n逐个扫描，遇到没访问过的位置，就沿着p一路走下去，把走过的位置都记下来，顺便标记已访问。走到底之后，这一组位置就是一个循环。把所有位置扫完，置换就完全分解开了。

这个分解过程本身只需要O(n)的时间，因为每个位置最多被访问一次。代码量也不大，核心就是一个while循环加一个vis数组。难点不在于怎么找循环，而在于想明白“为什么要找循环”。

2.2 k次变换的本质是循环内旋转位置

找到循环之后，解题的关键洞察就来了：一次变换，就是在每个循环内部，把所有字符沿着循环方向移动一个位置。做了k次变换，就相当于在这个循环内部连续移动k个位置。

更精确地说，在一个长度为len的循环里，某个字符在循环中的序号为j，变换k次之后，它的序号会变成(j + k)模len。因为是绕圈走的，所以序号对len取模就能回到循环内部。这里k可以非常大，但取模之后，真正有效的移动步数只有k % len步。

这个道理，跟一群人围成一圈跳舞很像。不管这支舞跳了多少拍，每个人最终的位置只跟“总拍数除以人数后的余数”有关。比如5个人围一圈，跳了13拍，每个人相当于只往前挪了3个位置，剩下10拍等于在原地绕了两整圈，没有实际影响。

所以，对于每一个循环，我只需要把循环里的字符统一移位k % len步，就可以一次性得到这个循环的最终形态。所有循环都处理完，整个字符串的最终结果也就出来了。整个算法的时间复杂度是O(n)，和k的大小完全无关，这才是本题真正要求的“高效做法”。

2.3 为什么这个方案比硬模拟稳得多

硬模拟的复杂度是O(nk)，而循环分解法是O(n)，当k达到10^9时，两者差距是数量级的。更重要的是，循环分解法不仅解决复杂度问题，还让代码逻辑更清晰：你只需要关心每个循环内部怎么转，不需要关心循环和循环之间的耦合关系，因为它们本来就不会互相影响。

这里还要补充一个容易忽略的细节：多个循环之间互不影响，意味着我可以单独处理每个循环，用独立的结果数组或者临时字符数组来存放。这样就不需要频繁修改原字符串，减少了出错风险。

我最初刷这道题时，一度想用“快速幂”的思路，把k次置换看成置换的k次方，然后尝试用倍增去算。后来发现没必要，因为置换这种“复合操作”和普通的数乘不一样，它天然是离散的循环结构，直接拆循环再取模，比快速幂还要直观。真正的快速幂在置换题里也有用，但一般是用来处理更复杂的变形，对2818这道题来说属于杀鸡用牛刀。

3. 完整实现与逐段代码讲解

3.1 C++整体框架与核心数据结构

下面给出我实际提交通过的C++代码框架，里面包含完整的循环分解和字符移位逻辑。

#include <bits/stdc++.h> using namespace std; int main() { int n; while (cin >> n && n) { vector<int> p(n + 1); for (int i = 1; i <= n; i++) { cin >> p[i]; } getchar(); // 吃掉整数行末尾的换行符 string s; getline(cin, s); int k; cin >> k; getchar(); // 吃掉k行末尾的换行符 // 若字符串长度不足n，按要求补足空格 while ((int)s.size() < n) { s += ' '; } vector<char> ans(n + 1, ' '); vector<bool> vis(n + 1, false); for (int i = 1; i <= n; i++) { if (!vis[i]) { vector<int> cyc; int cur = i; while (!vis[cur]) { vis[cur] = true; cyc.push_back(cur); cur = p[cur]; } int len = (int)cyc.size(); int shift = k % len; for (int j = 0; j < len; j++) { int from = cyc[(j - shift + len) % len]; ans[cyc[j]] = s[from - 1]; } } } for (int i = 1; i <= n; i++) { cout << ans[i]; } cout << endl; } return 0; }

这个代码里，p数组我用的是1-based下标，因为题目给的置换规则本身就是1到n的位置编号。选1-based可以避免“位置编号”和“数组下标”差1带来的混乱。字符串s本身是0-based的，所以我在取字符时用了s[from - 1]，这个细节很多教程不会提醒你，但写错一处就是WA。

3.2 循环分解部分的实现细节

循环分解的核心代码就几行：

while (!vis[cur]) { vis[cur] = true; cyc.push_back(cur); cur = p[cur]; }

从当前起点i出发，只要没访问过，就把当前节点加入循环列表，然后跳到下一个节点p[cur]。因为置换的性质决定了这条路必然绕回起点，所以一定会退出。要注意的是起点选取：外层for循环从1到n逐个检查vis，保证每个循环只会被处理一次，也不会漏掉任何一个位置。

这个写法有几个好处。第一，它天然支持多个循环的拆分，不需要额外处理循环之间的边界。第二，vis数组保证了时间复杂度是O(n)，每个节点只会入队一次。第三，如果某个循环长度为1，也就是p[i]等于i，那这个位置本身就是个自循环，处理起来非常自然：len等于1，shift等于k对1取模等于0，字符原地不动，符合直觉。

我见过有同学试图用“一个节点有没有被加入过”来判断是否完成循环，而不是用vis数组，结果在复杂样例上出现死循环。建议还是老老实实开一个bool数组，这样最稳。

3.3 字符移位与答案生成的注意事项

移位部分是这个题最容易出错的环节。代码里我写的是：

int from = cyc[(j - shift + len) % len]; ans[cyc[j]] = s[from - 1];

这里的意思是说：最终在cyc[j]这个位置上的字符，应该是原来在cyc[(j - shift) mod len]这个位置上的字符。换句话说，整个循环要往“前”挪shift步，所以当前槽位要从前面第shift个位置“拉”字符过来。加len再取模，是为了保证下标不出现负数。

这里的方向定义必须和前面第1题里的置换方向一致。如果你发现输出结果跟样例差了一位，或者整体乱了，多半就是这里的方向写反了。我建议写完代码后，先用一组特别小的数据手动验证，比如n等于2，p等于{2, 1}，s等于“ab”，k等于1，看结果是不是“ba”。如果是，方向就是对的；如果输出是“ab”或者“aa”，赶紧回头检查from的计算逻辑。

另外，补空格也要注意。原题要求字符串长度如果不足n，需要在末尾补空格到n位。我用的方法是while循环检查size并追加空格。如果你想写得紧凑一点，也可以一次性计算出需要补多少空格，用append(n - s.size(), ' ')来处理。

4. 实战排错与常见问题速查

4.1 字符串带空格时怎么读入

这是2818这题最容易坑人的地方，没有之一。题目里的待变换字符串是可能包含空格的，所以不能用cin >> s来读，否则只在第一个空格处截断，后面的内容全丢。正确姿势是用getline(cin, s)一次读一整行。

但用了getline之后，新的问题来了：前面的cin >> n和cin >> p[i]在读完后，行尾的换行符还留在缓冲区里，如果直接getline，会先读到一个空串。所以必须在读完整数列之后调用一次getchar()，把那个换行符吃掉。同样，读完k之后也要再getchar一下，否则下一组数据的getline又会读到空行。

我一开始没注意这个细节，样例全部通过，但交上去WA了好多次。后来加了两个getchar()，问题立刻解决。这种输入缓冲区的坑，几乎每个OJ上的字符串题都会遇到，属于必须掌握的通用经验。

4.2 置换方向写反了怎么排查

这个问题的典型表现是：小样例输出完全对，但自己构造的复杂数据总是差那么一点点；或者样例直接就不对，字符集整体错位。

解决方法是先确定题目到底用的是“跟随后继”的方向还是“来自前驱”的方向。你可以用n等于2这种最小规模的数据去试。比如p等于{2, 1}，s等于“ab”，一次变换后如果期望是“ba”，说明规则是“第i位字符跑到p[i]位”，也就是我代码里的写法。如果期望是“ab”不变，说明规则是“第i位字符来自p[i]位”，那你就得在移位时换成反向逻辑。

更稳妥的做法是，在拿到题目后第一时间读清楚样例说明，甚至可以把样例输入手算一遍，用自己的代码跑一遍，确保理解一致再写核心逻辑。说实话，方向问题完全可以通过一个5分钟的验证规避，别像我当初一样，写完一版然后反复试错，浪费时间。

4.3 边界条件：k等于0和n等于0的处理

k等于0时，按题意变换0次，输出原字符串。我的代码里shift会对len取模，但k为0时shift为0，from等于cyc[j]本身，所以ans会原样复制字符串，结果正确，不需要特判。

n等于0时，题目规定这是输入结束标记，所以while循环的条件是cin >> n && n，这样读到0就退出，不会进入死循环。这是POJ类题目的典型格式，把它写在读入条件里比在循环内break要干净。

还有一个小边界：当字符串长度刚好等于n时，补空格循环不会执行，没有问题。当字符串长度大于n时，我见过一些同学收到RE，实际上是访问越界。一般来说题目会保证长度不超过n，或者要求截断，但我还是建议你在读入后顺手判断一下，如果超长就resize到n，这样更保险。

4.4 时间超限和答案错误的常见原因

如果交上去TLE，十有八九是你在用最朴素的k次模拟。这个问题在数据量大时会非常明显。解决办法就是回到第2节的循环分解思路，而不是在代码上做局部优化。有些同学可能会想用“k mod n”来简化，但这里不能直接对n取模，因为n不是循环长度，多个循环的长度各不一样，你必须对每个循环分别计算k % len。

如果交上去WA，优先检查三件事：第一，字符串读入是否完整，特别是带空格的行；第二，数组下标有没有差1，尤其是从1-based的位置编号转换到0-based的字符数组；第三，方向有没有写反。这三件事解决掉，绝大多数WA都能变AC。

另外，有些版本的原题要求每组输出之间有空行，或者每组输出单独一行，这点要看题目的输出格式描述。纽提交错格式也会判PE或WA，建议提交前先把样例输出的空格、换行都对照一遍。

5. 从2818延伸开去的置换类算法思维

5.1 同类变体题怎么识别

刷完2818之后，你会发现很多题目都是它的变体。比如有一类问题是“给你一个置换，求它要作用多少次才能回到原始排列”，这其实就是在求置换的阶，也就是所有循环长度的最小公倍数。还有一类问题是“只问某个特定位置的字符经过k次变换后在哪个位置”，那只需要单独追踪一个循环，不需要处理全部字符串，复杂度还能进一步降低。

再比如二维网格的置换，像是在矩阵里做若干次旋转、镜像、行列交换，本质上也是置换的思想，只不过把位置编号变成二维坐标，你需要先给每个格子编号，再把它映射成一维位置序列。理解了循环分解，这类题目上手会快很多。

这些变体的共同特征，就是题目里会出现“操作重复多次”“周期变化”“问最终状态”等关键词。你一旦识别出这个特征，先别急着模拟，先想想能不能用循环分解把操作批量处理。

5.2 快速幂、KMP和置换思想的横向对比

有同学会把置换的多次复合和快速幂联系起来，这个方向是对的。快速幂解决的是“重复做同一种可结合的运算”的加速问题，置换复合恰好满足结合律，所以理论上也可以用倍增法求置换的k次幂。但在2818这种题里，循环分解比快速幂更直观，因为它直接把问题的解暴露出来了：每个小循环内旋转k % len步。

而KMP、归并排序这类题，和置换的思路又不太一样。KMP的核心在于部分匹配表，归并排序的核心在于分治合并，它们都更强调“比较”和“顺序”，而置换题强调的是“位置映射”和“周期”。不过它们有个共同点，都是对数据结构的某种抽象理解，刷题时不能只背模板，要理解背后的结构性质。

从算法体系上看，置换和循环分解是群论入门里最简单的部分，但应用面很广。字符串洗牌、密码学中的多表替换、棋盘状态变换，很多场景都会用到。我建议你把“循环分解”当作一个独立的知识点记在笔记里，配合poj 2818这道题作为第一道练习题，以后再遇到同类题就不慌了。

5.3 给刷题者的几条实在建议

最后说几条我自己刷这道题和同类题时总结出的经验。第一，不管题目看起来多简单，先手算样例，确认置换方向再动手写代码，这个习惯能帮你省下至少半小时的调试时间。第二，输入输出格式一定以题目的样例为准，特别是涉及空格的字符串，读入方式要反复确认。第三，善用小的打印调试：在找循环之后，把每个循环的元素打出来看一眼，就知道自己的分解逻辑对不对了。

我还想特别强调一点：算法题不是背出来的，是“试”出来的。2818这道题我刷完一遍之后，又自己改了好几个版本，比如尝试用快速幂实现、尝试把方向反转、尝试只处理单个位置的查询，每一次改动都能对置换有更深的理解。这种“一题多改”的做法，比盲目刷十道同类型的新题效果要更好。

如果你刚刷完这道题，建议你顺手再做一道类似的置换题目，把一个循环拆开、处理、验证的流程练熟。刷题最怕的是似懂非懂，只要你能在不看题解的情况下，独立把循环分解的代码写出来，并且解释清楚为什么k要按循环长度取模，这道题就算真正吃透了。