为了协助你高效地准备 NOI 竞赛练习题，我编写了符合竞赛标准的 数据生成器 和 SPJ (Special Judge)。

一、 数据生成器 (gen.cpp)

该生成器采用 C++14 标准，利用非递归的 std::next_permutation 算法生成不重复的全排列。这个算法天然处理重复元素，且不占用递归栈。

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <random>

using namespace std;

// 核心生成逻辑：迭代式生成所有不重复全排列并写入文件
void generate_output(int n, vector<int>& nums, const string& out_name) {
    ofstream fout(out_name);
    if (!fout.is_open()) return;

    // 处理重复元素全排列的前提：必须先排序
    sort(nums.begin(), nums.end());

    do {
        for (int i = 0; i < n; ++i) {
            fout << nums[i] << (i == n - 1 ? "" : " ");
        }
        fout << "\n";
    } while (next_permutation(nums.begin(), nums.end()));
    
    fout.close();
}

int main() {
    // 10个测试点的 n 规模设计
    int test_n[] = {1, 3, 3, 6, 8, 8, 8, 8, 8, 8};
    mt19937 rng(12345);

    for (int t = 1; t <= 10; ++t) {
        int n = test_n[t - 1];
        string in_name = to_string(t) + ".in";
        string out_name = to_string(t) + ".out";

        vector<int> nums;
        // 特殊情况处理
        if (t == 1) nums = {100};                      // 边界: n=1
        else if (t == 2) nums = {1, 1, 1};             // 边界: 全部相同
        else if (t == 3) nums = {1, 1, 2};             // 样例
        else if (t == 4) nums = {1, 2, 3, 4, 5, 6};    // 无重复全排列
        else {
            // 生成带重复的随机数据
            uniform_int_distribution<int> val_dist(-10, 10);
            for(int i = 0; i < n; ++i) {
                // 通过减小随机范围来增加重复概率
                nums.push_back(val_dist(rng) % (t / 2 + 1)); 
            }
        }

        // 写入输入文件
        ofstream fin(in_name);
        fin << n << "\n";
        for (int i = 0; i < n; ++i) fin << nums[i] << (i == n - 1 ? "" : " ");
        fin << "\n";
        fin.close();

        // 生成标准答案
        generate_output(n, nums, out_name);
        cout << "Test data " << t << " generated (n=" << n << ")." << endl;
    }
    return 0;
}

二、 特判程序 (checker.cpp)

使用 testlib.h 标准库。该 SPJ 会验证选手输出的每一行是否为原序列的合法排列，且利用 set 确保没有重复输出，最后核对总排列数是否正确。

#include "testlib.h"
#include <vector>
#include <set>
#include <algorithm>
#include <map>

using namespace std;

// 使用 C++14 兼容语法计算不重复全排列的总数
long long count_unique_permutations(vector<int> nums) {
    int n = nums.size();
    map<int, int> counts;
    for (int i = 0; i < n; ++i) {
        counts[nums[i]]++;
    }
    
    auto fact = [](int k) {
        long long res = 1;
        for (int i = 2; i <= k; ++i) res *= i;
        return res;
    };
    
    long long total = fact(n);
    // C++14 修正：改用传统的迭代器或范围 for 遍历 map
    for (auto const& item : counts) {
        int freq = item.second; // item 是 std::pair<const int, int>
        total /= fact(freq);
    }
    return total;
}

int main(int argc, char* argv[]) {
    // 插件初始化
    registerTestlibCmd(argc, argv);

    // 1. 读取输入
    int n = inf.readInt();
    vector<int> source;
    for (int i = 0; i < n; ++i) {
        source.push_back(inf.readInt());
    }
    sort(source.begin(), source.end());

    long long expected_count = count_unique_permutations(source);

    // 2. 读入用户输出并验证
    set<vector<int>> user_perms;
    long long actual_count = 0;

    // seekEof() 会自动跳过末尾的空格和换行，更具鲁棒性
    while (!ouf.seekEof()) {
        actual_count++;
        
        // 保护：防止死循环或输出天文数字导致 SPJ 崩溃
        if (actual_count > expected_count + 100) {
            quitf(_wa, "输出的全排列数量远超预期值 %lld", expected_count);
        }

        vector<int> curr;
        for (int i = 0; i < n; ++i) {
            curr.push_back(ouf.readInt());
        }

        // A. 验证是否为原序列的排列
        vector<int> sorted_curr = curr;
        // 修正笔误：确保变量名一致
        sort(sorted_curr.begin(), sorted_curr.end());
        if (sorted_curr != source) {
            quitf(_wa, "第 %lld 行不是原序列的合法排列（数字或频率不对）", actual_count);
        }

        // B. 验证是否重复
        if (user_perms.count(curr)) {
            quitf(_wa, "第 %lld 行输出了重复的排列", actual_count);
        }
        user_perms.insert(curr);
    }

    // 3. 最终验证数量
    if (actual_count < expected_count) {
        quitf(_wa, "排列数量不足：期望 %lld, 实际只读到 %lld", expected_count, actual_count);
    }
    if (actual_count > expected_count) {
        quitf(_wa, "排列数量过多：期望 %lld, 实际读到 %lld", expected_count, actual_count);
    }

    quitf(_ok, "答案正确！共验证了 %lld 个唯一全排列。", expected_count);
    return 0;
}

三、 复杂度分析思考过程

1. 数据范围选取 ($n \le 8$)：

   • 全排列的时间复杂度是 $O(N \cdot N!)$。
   • 当 $N=8$ 时，$8! = 40,320$。$40,320 \times 8 \approx 3.2 \times 10^5$。
   • 输出文件大小：每行约 20 字节，总大小约为 $40,320 \times 20 \approx 800$ KB。这完美符合 2MB 以内的要求。
   • 如果 $N=9$，$9! = 362,880$，文件将达到 7MB 以上，超出了理想阈值。

2. 空间复杂度与防爆栈：

   • 生成器使用了迭代法（next_permutation），空间复杂度 $O(N)$，且无递归调用，绝对不会爆栈。
   • SPJ 内部使用了 set<vector<int>>，在 $N=8$ 情况下，集合存储约 4 万个排列，占用内存约 $40,320 \times 32 \text{ bytes} \approx 1.3$ MB，远低于 256MB 的限制。

3. 异常处理：

   • 在计算总数时，我们统计了频率并使用阶乘除法。由于频率 freq 最小为 1，fact(freq) 最小为 1，绝对不会发生除以 0 的异常。

四、 读题理解关键词

在 NOI 考试中，遇到此题需通过以下关键词快速拆解：

• “可包含重复数字”：立刻反应出搜索前需要 sort。
• “不重复的全排列”：意味着必须通过 used[i-1] == false 进行树层剪枝。
• “任意顺序”：这代表考场上如果时间紧迫，你可以不考虑字典序，但为了通过普通 diff 的练习题，通常还是按搜索顺序输出。而在有 SPJ 的正式比赛中，只要不重不漏即可。

教练寄语： 这道题是搜索算法中“查重”与“回溯”结合的最高形式。如果你能手写出那个带 !used[i-1] 的判断，并理解它是如何砍掉整棵子树的，那么你在搜索专题上已经具备了冲击省一的实力。加油！

同学，全排列 II 是搜索算法中的经典“去重”题目。处理重复元素的关键在于：在搜索树的同一层，不要选择数值相同的元素。

下面我为你准备了三个版本的代码，带你从“工具使用”进阶到“算法内核”。

版本一：STL 神器法（竞赛最稳方案）

在 NOI 竞赛中，如果题目没有特殊的剪枝要求，std::next_permutation 是处理重复元素全排列的最优选择，因为它内部已经高度优化了去重逻辑。

思考过程：

• 时间复杂度：$O(n \cdot n!)$。该函数生成下一个排列的平均复杂度是 $O(1)$，总共有 $n!$ 种可能。
• 空间复杂度：$O(1)$（不计存储输入的数组）。
• 注意：必须先执行 sort，否则无法找全所有排列。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // 竞赛优化：加速 I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<int> nums(n);
    for (int i = 0; i < n; ++i) cin >> nums[i];

    // 核心：处理重复元素必须先排序，保证相同元素相邻
    sort(nums.begin(), nums.end());

    do {
        for (int i = 0; i < n; ++i) {
            cout << nums[i] << (i == n - 1 ? "" : " ");
        }
        cout << "\n";
    } while (next_permutation(nums.begin(), nums.end()));

    return 0;
}

版本二：标准回溯剪枝（NOI 核心功底）

这是你必须刻在脑海里的代码。通过排序和 used 数组，在搜索树中进行“水平切割”。

思考过程：

• 时间复杂度：$O(n \cdot n!)$。
• 空间复杂度：$O(n)$，递归深度。
• 关键逻辑：if (i > 0 && a[i] == a[i-1] && !used[i-1]) continue;。
  • 这行代码的意思是：如果当前数字和前一个相同，且前一个数字刚刚被回溯过（used 为 false），说明在当前这一层我们已经用过这个数值了，必须跳过。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n;
int a[15], path[15];
bool used[15];

void dfs(int depth) {
    if (depth == n) {
        for (int i = 0; i < n; ++i)
            cout << path[i] << (i == n - 1 ? "" : " ");
        cout << "\n";
        return;
    }

    for (int i = 0; i < n; ++i) {
        // 易错点 1：当前位置已经被占用，跳过
        if (used[i]) continue;

        // 关键剪枝点：
        // 如果 a[i] == a[i-1]，且 a[i-1] 没被使用过
        // 说明我们正处在“同一层”递归中，正准备第二次尝试同一个数值
        // 为了去重，这种情况必须剪掉
        if (i > 0 && a[i] == a[i - 1] && !used[i - 1]) continue;

        used[i] = true;
        path[depth] = a[i];
        dfs(depth + 1);
        
        // 回溯：恢复现场
        used[i] = false;
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    if (!(cin >> n)) return 0;
    for (int i = 0; i < n; ++i) cin >> a[i];

    // 必须排序，否则 a[i] == a[i-1] 的逻辑失效
    sort(a, a + n);

    dfs(0);
    return 0;
}

版本三：最优复杂度优化建议

当 $n$ 较大或时限极紧时，我们可以进一步优化。

优化思考过程：

1. 传值 vs 传引用：在 dfs 中永远不要直接传递 vector 作为参数，那会产生大量的 $O(n)$ 拷贝开销。
2. 树层去重优化：使用 !used[i-1] 还是 used[i-1]？
   • !used[i-1]：是在“树层”去重，效率极高，因为它直接砍掉了一整个分支。
   • used[i-1]：是在“树枝”去重，虽然结果也对，但搜索量大。
3. I/O 优化：全排列是典型的“输出密集型”题目，cout 性能往往不如 printf 或 fwrite。

复杂度分析总结

1. 时间复杂度：
   • 最坏情况下（无重复元素）：$O(n \cdot n!)$。
   • 最优情况下（全部元素相同）：$O(n)$。
   • 平均：$O(n \cdot \text{unique\_permutations})$。
2. 空间复杂度：
   • $O(n)$：递归栈的最大深度为 $n$，标记数组 used 的大小为 $n$。
3. 数据规模建议：
   • 在 NOI 赛场上，若看到 $n \le 10$ 且有重复元素，优先考虑带剪枝的 DFS。
   • 若 $n > 12$，全排列通常不是唯一考点，可能需要结合动态规划（状压 DP）或组合数学公式。

读题关键词总结

做排列类题目时，请像雷达一样扫描这些词：

• “所有” (All) $\rightarrow$ 搜索路径。
• “不重复/唯一” (Unique) $\rightarrow$ 需要剪枝逻辑 a[i] == a[i-1]。
• “重复数字” (Duplicates) $\rightarrow$ 必须先执行 sort。
• “顺序无关” (Any order) $\rightarrow$ 暗示你可以用最容易实现的 DFS 序。

教练寄语： 同学，你要记住，used[i-1] == false 的真谛在于：我们刚刚用过它，并且已经搜索完了以它开头的所有可能性，现在把它放回来了。如果我们现在再用一个同样的数，那不是在做重复劳动吗？ 掌握了这个逻辑，你就能掌握所有带重复元素的搜索题！