企业官网建设流程全解析

百炼OJ上一道题名特别唬人的题，2818:密码。我第一次看到的时候，以为是字符串算法或者KMP之类的高端货，点进去读完题才反应过来：这就是一道暴力搜索题，考的是DFS回溯、剪枝和字符串匹配的组合，名字里带“密码”纯属唬人。这道题非常适合用来理解暴力枚举算法的边界和优化思路，也适合准备机考、刚接触OJ刷题的朋友练手。这篇我按自己的真实刷题过程来写，从读题、翻车、优化到最终提交的代码一次讲完，你照着抄也能过，更重要的是能把这套思路迁移到其他排列枚举型的OJ题上去。

1. 先读透题：这个“密码”到底要我们找什么

1.1 题目设定与输入输出格式

题目大意是这样：一个n位正整数被视作一串密码，要求各位数字互不相同，并且首位不能是0。再给定一个一位数p（2≤p≤9），如果这个数字X乘以p之后，得到的十进制数字串恰好是X自身数字串的某个循环右移，那么X就是一个合法密码。输入会给你多组数据，每组两个整数n和p，要求你按字典序升序输出所有合法密码；如果没有解，就输出None。

比如输入：

6 2

输出：

142857 285714 428571 571428 714285 857142

这六个数的来历很经典：它们是1/7循环节142857的所有循环移位，142857乘以2得到285714，285714也是142857的循环移位；同理剩下几个也都满足，所以题目结果是一整组答案，而不是只找一个。这就是为什么输出要求是“所有合法密码”，而不是“任意一个”。

1.2 三条硬约束在代码里分别对应什么

第一眼看，这个题面有三个约束：第一是n位正整数，首位不能是0；第二是各位数字互不相同；第三是乘p之后的数字串必须是原数字串的循环移位。前两个约束在代码里很容易翻译：首位不能为0，就让DFS第一层的枚举范围从1到9；各位互异，就用一个used[10]数组或者位掩码在搜索时标记哪些数字已经用过。

第三个约束最容易读歪，也是最容易写错的地方。要特别注意题目说的是“数字串”的循环移位，不是“数字”的循环移位。什么叫数字串的循环右移？就是把字符串最后一个字符挪到最前面，比如142857循环右移4位得到285714，再右移一次得到428571。这是一个纯粹的字符串操作，跟数值大小没有关系。很多人把这里理解成“把数字整体转一圈”，然后就卡住了，因为从数值上根本看不出142857和285714有什么循环关系。

一旦意识到要用字符串视角看，这题的核心就清晰了：枚举所有满足前两个约束的n位数字串，然后判断它乘p的结果能否在“双倍字符串”里找到它自己。这个判断方法后面细说，是一个非常经典的字符串技巧。

2. 第一版思路为什么会翻车：从“枚举”到“边枚举边淘汰”

2.1 误区一：以为这是字符串哈希问题

题名带“密码”，又涉及“循环移位”，很容易让人往字符串哈希、KMP、甚至什么加密算法上想。我第一反应也是去构造什么哈希映射，想直接通过某种数字特征判断循环移位，折腾了半天发现没必要。这道题n的范围只到10，本质上就是个暴力枚举题，哈希在这里属于杀鸡用牛刀，而且还会引入碰撞和边界判断的额外复杂度。

密码类题目在OJ里其实经常是“伪装”的搜索题，题面越唬人，核心往往越朴素。以后看到带“密码”“加密”“破解”字样的题，先别急着往密码学方向想，先看看数据范围：如果n是个位数或者10左右，大概率就是暴力搜索加剪枝。

2.2 误区二：直接全排列然后统一检查

最简单的实现方法是用next_permutation枚举所有n位不重复数字的排列，然后逐个检查。代码写起来很短，但问题在于它把所有排列都完整生成后才会做检查，中间没有任何提前止损的机会。

算一下规模：如果没有任何限制，10位数字有90亿种可能；加上首位不能为0并且各位互异之后，总数变成9 × 9! = 3265920，大约327万个排列。每个排列都要做一次乘法和一次字符串匹配，看起来好像不多，但这里有一个很多人忽略的隐藏代价：每次匹配要先把数字转成字符串，再做双倍串查找，就算字符串长度不超过10，327万次叠加起来也是上千万次的字符操作。在OJ普遍1秒到2秒的时间限制下，这种写法非常容易超时。

我最早就是先用next_permutation写了个“能跑但很勉强”的版本，本机测试n=10大概跑了3秒多，交上去果然TLE。这时候我才意识到，枚举空间已经不是主要问题了，真正的瓶颈在于每个叶子节点都要做一次相对昂贵的完整检查。

2.3 关注点应该在“剪枝空间”而不是“枚举空间”

暴力枚举算法给人最直观的印象是“把所有可能都试一遍，试到天荒地老”。但实际上，一个合格的暴力枚举题，不会真的让你枚举完整状态空间，而是考察你能不能把题目的约束变成“剪枝条件”，在搜索的过程中就把大量不可能的分支提前砍掉。

换句话讲，枚举量 × 单次检查代价，才是总代价。next_permutation的思路是枚举完整排列、付出完整检查代价；而DFS回溯的思路是每填一位就顺手看一眼“这条路还有没有可能”，如果当前前缀已经注定生不出合法答案，就立刻回头。后者往往能快几个数量级。2818这道题，真正值得研究的就是怎么设计这些剪枝条件，以及剪枝的顺序怎么安排。

3. 核心设计：DFS回溯配合三处剪枝

3.1 剪枝一：用乘积位数反推合法X的范围

题目有一个非常重要的隐含条件：如果X乘p的结果是X的循环移位，那么结果的长度一定还是n位。循环移位不会改变字符串长度，所以X * p必然落在[10^(n-1), 10^n-1]这个区间内。

这个条件看似简单，却能推出一个很硬的范围约束。因为X * p < 10^n，所以X < 10^n / p；又因为X * p >= 10^(n-1)，所以X >= 10^(n-1) / p。结合首位不能为0，我们就能估算出X的首位取值范围。

举个例子，n=6, p=2时，X必须在[50000, 499999]中，但X是6位数，所以实际范围是[100000, 499999]，首位只能是1、2、3、4。第一层枚举直接从9个候选缩减到4个。到了n=10, p=9的时候更夸张，10^10 / 9大约是11.1亿，X作为10位数首位只能是1，相当于第一层直接被砍到只剩一个分支。

这个剪枝我在代码里没有单独写成一段复杂的区间逻辑，而是把它融入了DFS的枚举顺序：第一层仍然从1到9枚举，因为第一层只有9个分支，收益不够大；真正把范围约束利用起来的是下面这个中间层剪枝，它会把类似的位数约束在每一层都自动生效。

3.2 剪枝二：前缀上下界剪枝，中间层就敢放弃整棵子树

这是本文最核心的优化。DFS进行到第pos层时，当前已经填好的前缀是cur，还没用过的数字集合rest也是确定的。这时候不管后续怎么排列，完整的X一定介于两个极端之间：最小值是cur + rest升序排列，最大值是cur + rest降序排列。

既然X乘p的结果必须是n位数，那就可以做两个判断：

• 如果最小值 * p < 10^(n-1)，说明这棵子树里即使拼出最小的数，乘积也够不到n位，整棵子树不可能有合法答案，直接返回；
• 如果最大值 * p >= 10^n，说明这棵子树里即使拼出最大的数，乘积也已经溢出到n+1位，同样直接返回。

这个剪枝最大的好处是“安全性有保证”。它用的条件是“乘积必须是n位数”，这是任何合法答案都必须满足的必要条件，所以它不可能误杀真正的解。它只会在中间层就砍掉那些注定位数不对的分支，让真正走到叶子节点去做循环移位匹配的数量大幅减少。

我在本地测试时，给n=10、p=2的数据分别跑了两版：一版只在叶子做检查，一版加上前缀上下界剪枝。前者的时间已经接近时限，后者直接降到半秒以内。差距就是这么明显。

3.3 剪枝三：叶子检查用双倍串查找判断循环移位

有了解法的框架，叶子节点的检查也要写得干净。判断“字符串s是不是字符串t的循环移位”有一个经典做法：把t拼成t+t，然后看s是不是t+t的子串。因为循环移位本质上就是在一个环上滑动窗口，t的任意循环移位都能在t+t里找到，反过来t+t里任意长度等于n的连续子串也必然是t的某个循环移位。这就是把环形问题转换成线性匹配问题。

具体到这道题，设ms = to_string(X * p)，我们真正想判断的是“s是否是ms的循环移位”。那直接看(ms + ms).find(s) != string::npos就行了。在n不超过10的情况下，双倍串长度最多20个字符，find的实现已经充分优化，这个操作的常数极小。

这里有一个容易忽略的细节：先判断长度再拼接。如果ms的长度不等于n，它根本不可能是s的循环移位，直接返回false，连双倍串都不用拼。很多第一次做这道题的人把次序写反了，先拼接再判断长度，虽然结果没错，但白白浪费了一部分字符串操作。

3.4 为什么剪枝顺序这么排

剪枝的顺序很影响实际耗时，原则很简单：把代价低、淘汰率高的判断放在前面。

第一层限制首位从1开始枚举，这是循环变量天然控制的，零成本。中间层的前缀上下界剪枝，每层进入数字循环前都要算一次rest和两个极值，成本是O(n log n)，但淘汰率极高，所以这笔开销花得值。叶子检查里，先比较长度，再执行双倍串查找，也是把最便宜、淘汰率最高的判断放在最前面。整个搜索过程中，真正执行完整find的叶子节点数量已经比原始全枚举少了好几个数量级，耗时自然就下来了。

如果用一句话总结这段优化：枚举是兜底，剪枝是灵魂，而代价最低的剪枝一定放在最前面。

4. 可直接提交的完整代码（C++与Python）

4.1 C++ 完整实现与关键变量解释

这道题我用C++提交，因为OJ上C++的字符串操作和递归速度都比Python稳。完整代码如下：

#include <bits/stdc++.h> using namespace std; int n, p; string cur; bool used[10]; vector<string> ans; long long pw[15]; bool check() { if ((int)cur.size() != n) return false; long long x = stoll(cur); long long m = x * p; string ms = to_string(m); if ((int)ms.size() != n) return false; string ds = ms + ms; return ds.find(cur) != string::npos; } void dfs(int pos) { if (pos == n) { if (check()) ans.push_back(cur); return; } // 中间层剪枝：前缀上下界 if (pos > 0) { string rest; for (int d = 0; d <= 9; d++) { if (!used[d]) rest.push_back(char('0' + d)); } if (rest.empty()) return; string mn_tail = rest; string mx_tail = rest; reverse(mx_tail.begin(), mx_tail.end()); long long mn = stoll(cur + mn_tail); long long mx = stoll(cur + mx_tail); if (mn * p < pw[n - 1]) return; if (mx * p >= pw[n]) return; } int start = (pos == 0) ? 1 : 0; for (int d = start; d <= 9; d++) { if (used[d]) continue; used[d] = true; cur.push_back(char('0' + d)); dfs(pos + 1); cur.pop_back(); used[d] = false; } } int main() { pw[0] = 1; for (int i = 1; i < 15; i++) pw[i] = pw[i - 1] * 10; while (cin >> n >> p) { cur.clear(); ans.clear(); memset(used, 0, sizeof(used)); dfs(0); sort(ans.begin(), ans.end()); if (ans.empty()) { cout << "None" << '\n'; } else { for (string &s : ans) cout << s << '\n'; } } return 0; }

几个关键点解释一下：cur用字符串而不是用整数维护，因为前缀上下界剪枝需要频繁拼接未用数字，字符串操作更直接。used数组负责互异判断，同时承担了让排列不重复生成的作用。pw数组预先算好10的幂，避免每层都重新算。乘积变量必须开long long，原因后面讲坑的时候会单独说明。

4.2 check()里的细节：先比长度，再做双倍串匹配

check()是这个解法里最容易被写错的地方，我再拆开讲一遍。第一步把cur转成long long，乘上p得到m。第二步判断m的位数，如果长度不等于n，说明乘积不可能是cur的循环移位，直接返回false。第三步把ms拼成双倍串，查找cur是否存在。

这里为什么不直接比较cur的循环移位和ms是否相等？因为要枚举n种移位，写起来啰嗦，而且每次都要重新构造字符串，常数比较大。双倍串查找一次搞定，代码短、思路清晰，还把“环形比较”这个抽象问题落地了。

另外，stoll在C++11里是标准库函数，大部分OJ都支持。如果你的OJ比较老，遇到stoll编译不过，可以用strtoll或者stringstream替代，但这个题一般不需要担心。

4.3 Python 验证版：本地测思路比交题更实用

如果你平时用Python刷题，这个题在n比较小的时候可以交，但n=10时Python版本在多组数据下容易超时。我建议把Python版本当作本地验证和生成答案的工具，主力提交还是用C++。Python版同样完整可运行：

import sys def solve_case(n, p): cur = "" used = [False] * 10 ans = [] pw = [10 ** i for i in range(15)] def dfs(pos): nonlocal cur if pos == n: m = int(cur) * p ms = str(m) if len(ms) == n and cur in (ms + ms): ans.append(cur) return if pos > 0: rest = [str(d) for d in range(10) if not used[d]] mn = int(cur + ''.join(sorted(rest))) mx = int(cur + ''.join(sorted(rest, reverse=True))) if mn * p < pw[n - 1] or mx * p >= pw[n]: return start = 1 if pos == 0 else 0 for d in range(start, 10): if not used[d]: used[d] = True cur += str(d) dfs(pos + 1) cur = cur[:-1] used[d] = False dfs(0) ans.sort() return ans if ans else ["None"] data = sys.stdin.read().strip().split() for i in range(0, len(data), 2): n = int(data[i]) p = int(data[i + 1]) for s in solve_case(n, p): print(s)

Python版本在n=6或者n=7时跑得飞快，用来验证思路完全够用，也方便你测试各种p值观察输出规律。

5. 我在提交过程中踩过的四个坑

5.1 把“循环移位”错写成“字符重排”

这是我交出的第一个WA版本。当时图省事，直接在check里对s和ms做字符计数比较，也就是排序后看两个串是否相等，心想“反正循环移位也不会改变字符集合，这样判断肯定没问题”。结果问题恰恰出在这里：字符集合相同只能说明两个串是“字符重排”，不能说明它们是“循环移位”。

最典型的反例就是n=4、p=9时，X=1089，乘9得到9801。1089和9801的字符集合完全一样，都是0、1、8、9各出现一次，但9801并不是1089的循环移位。1089的循环移位只有1089、9108、8910、0891四种，9801不在其中。用字符计数判断，1089就会被错误地当成合法密码输出，而正确答案里不应该有它。

所以这个WA的教训很直接：读题时看到“循环移位”四个字，就要想到双倍串查找，千万不要擅自放宽成“字符集合相等”，一旦放宽，假阳性就会悄悄混进来。

5.2 int溢出：n=10时乘积直接变负数

第二次提交的代码逻辑已经接近正确，但我用的是int类型保存乘法结果，本地测小数据全对，一交上去就WA，而且输出里出现了一堆奇怪的数字。排查半天发现问题出在溢出：n=10时，X最大可以到9876543210，乘以9是88888888890，早就超过了int的2147483647上限；即使是最小的10位无重数字1023456789，乘以9也达到9211111101，同样溢出。

C++里整数溢出是未定义行为，表现可能是负数，也可能是完全离谱的正数，总之这道题乘法结果必须要用long long来装。字符串转数字的时候也要用stoll而不是stoi，否则转换这一步就会截断。

5.3 多组数据状态没清干净，答案越滚越长

因为题目有多组数据，我在主函数里一开始只写了cin >> n >> p，没有把每组数据开始前的cur、used和ans清空。结果第二组数据的DFS会把第一组已经用掉的数字标记继承下来，导致合法的排列被错误跳过，答案缺失甚至为空。这个坑属于“低级但隐蔽”，因为本地只测一组数据时根本不会暴露，一交到OJ上就原形毕露。

正确处理是在while (cin >> n >> p)内部，每次循环都执行cur.clear()、ans.clear()、memset(used, 0, sizeof(used))。这个习惯对任何多组输入的搜索题都适用，建议想都不想直接写上。

5.4 自测用例设计：正例和反例一起测

这道题我后来总结出一套很实用的自测方法：每次改完代码，先跑n=6 p=2，预期输出是142857那六个循环移位；再跑n=4 p=9，预期是None（因为1089只是反例，不是循环移位）。这一正一反两个用例，能把check逻辑里最敏感的部分都覆盖到。

如果再想验证边界，就测n=1 p=2。一位数字乘2之后不可能还是相同长度的一位数字，所以无解，输出None。这种“多组小数据快速对拍”的习惯，对排查搜索类题目的隐蔽逻辑错误非常有效，建议每个刷题的人都养成。

6. 从2818延伸开：排列枚举题的通用套路

6.1 排列型暴力题的五步框架

刷完这道题之后，我总结出一套做排列枚举题的通用的步骤，后面遇到类似的题基本都是按这个思路走：

第一步，把题目的约束翻译成代码条件，尤其要分清哪些是必要条件、哪些是充分条件。第二步，确定枚举对象和枚举顺序，比如这道题是按位填数字，而不是枚举所有整数。第三步，找出能在中间层使用的剪枝条件，这一步的核心是“从当前已确定的部分，推出剩余部分的上下界或者合法范围”。第四步，在叶子节点用最精确的条件做最终验证，比如双倍串查找。第五步，处理好输入输出格式，多组数据记得清状态。

这套框架对八皇后、数独、全排列类问题都通用。差别只在剪枝条件不同，但思维路径完全一致。

6.2 什么时候该DFS，什么时候该next_permutation，什么时候该状压

很多初学算法的人会有个疑问：既然全排列可以用next_permutation，为什么还要自己写DFS回溯？我的判断标准是这样的：如果枚举规模很小、检查代价很低，比如n不超过8，直接next_permutation加检查是最省心、最不容易写错的；如果约束能从前缀推导出来、中间层有得剪，那就用DFS回溯，比如2818这道题；如果问题需要依赖“已经选过哪些数字”的记忆化结果，而不是简单的前缀信息，那就得上状压DP了。

三者不是互斥关系，而是一个递进：next_permutation是“生成完整排列再判断”，DFS是“边生成边判断”，状压DP是“把状态当作记忆化索引”。选哪个，取决于题目的约束长在哪一层。2818的约束（乘积位数、循环移位）都可以在前缀阶段做出“大概率不可能”的判断，所以DFS是最合适的。

6.3 改一个条件就能变成的新题

“密码”这类题的变体特别多，我把核心判断函数改了改，就能变成三四个不同的题。

如果把“循环移位”改成“倒序”，check函数就变成判断ms == reverse(cur)。这是经典题1089×9=9801，n=4 p=9时1089就会成为合法答案，和循环移位版本完全相反，非常有意思。

如果把“循环移位”放宽成“字符重排”，check函数就改成对s和ms分别排序再比较。这个变体的解会比原题多很多，同时也就回到了我踩过的那个坑：条件越宽，假阳性越多，出题人考的就是你能不能精确实现“循环移位”而不是“字符重排”。

如果再加一个约束，比如“各位数字之和等于给定值s”，那DFS就要额外维护一个sum参数，并且剪枝可以再加两条：当前sum已经超过s就返回，或者剩余位数哪怕全部填9也补不够s就返回。这类“约束数量越多，剪枝越丰富”的题，在OJ上比比皆是。

我个人的体会是，刷题不能只看题解跑没跑通，更值得复盘的是这个题到底卡在哪一步、哪个条件提供了最有效的剪枝。2818这道题我刷完很久了，但它教会我的不是循环移位怎么判断，而是“先用必要条件剪枝、再用充分条件验证”这套搜索题的底层逻辑。现在我遇到带“密码”“加密”这类名字的OJ题，第一反应都是先冷静下来看看数据范围，十有八九又是一道伪装的暴力搜索题。