1 条题解

  • 0
    @ 2026-11-16 20:48:26

    字典序通行码:解题说明

    先调用 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
    上传者