1 条题解
-
0
字典序通行码:解题说明
先调用
sort(s.begin(),s.end())得到最小排列。使用do { ... } while (next_permutation(s.begin(),s.end()))收集当前排列及其后继。next_permutation在当前排列有后继时生成紧邻的字典序后继并返回 true,已经是最大排列时返回 false。相同字母不会产生重复的字符串排列。收集到
vector<string>后,先输出大小,再逐行输出元素。每个字符串都是合法排列;从最小排列出发、每次跳到下一个排列,保证完整、无重复且顺序正确。若长度为 L、不同排列数为 P,总时间 O(P·L),空间 O(P·L)。L≤9,P≤362880,满足限制。也可以先用阶乘除以各字符频数阶乘得到数量,然后边枚举边输出。
常见错误:没有预先排序,漏掉输入之前的排列;只写 while 循环而漏掉最小排列;把相同字母当成不同物件输出重复行;忽略最大输入的输出量。
验证期望由独立 Python 算法生成,不读取参考程序。样例先手算,再以空实现确认测试失败;正式数据包含边界、固定种子随机及两个最大规模用例。
C++17 参考实现
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); string s; cin>>s; sort(s.begin(),s.end()); vector<string> codes; do { codes.push_back(s); } while(next_permutation(s.begin(),s.end())); cout<<codes.size()<<'\n'; for(const string &code:codes) cout<<code<<'\n'; return 0; }
- 1
信息
- ID
- 5268
- 时间
- 2000ms
- 内存
- 256MiB
- 难度
- 2
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者