你好！我是你的 OI 金牌教练。针对 [JLOI2011] 不重复数字，我们不仅要生成符合规范的数据，更要通过数据构造来体现 $O(n^2)$、$O(n \log n)$ 和 $O(n)$ 算法之间的性能鸿沟。

为了解决你之前提到的“文件过大”和“生成卡顿”问题，我优化了 $T$ 和 $n$ 的分配比例：保持单组 $n$ 达到上限（用于卡掉 $O(n^2)$），但减少总组数 $T$（用于压缩文件体积）。

数据生成器代码 (C++14)

#include <iostream>
#include <cstdio>
#include <vector>
#include <unordered_set>
#include <random>
#include <chrono>

using namespace std;

// 随机数引擎，使用当前时间作为种子
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

// 生成 [min_v, max_v] 范围内的随机整数
int rand_int(long long min_v, long long max_v) {
    uniform_int_distribution<long long> dist(min_v, max_v);
    return (int)dist(rng);
}

// 模拟标准解法生成 .out 文件
void generate_out(const string& in_name, const string& out_name) {
    FILE* fin = fopen(in_name.c_str(), "r");
    FILE* fout = fopen(out_name.c_str(), "w");
    int T, n;
    if (fscanf(fin, "%d", &T) == 1) {
        while (T--) {
            fscanf(fin, "%d", &n);
            unordered_set<int> seen;
            seen.reserve(n); // 关键：预留空间，减少 rehash 时间
            bool first = true;
            for (int i = 0; i < n; ++i) {
                int x;
                fscanf(fin, "%d", &x);
                if (seen.find(x) == seen.end()) {
                    if (!first) fprintf(fout, " ");
                    fprintf(fout, "%d", x);
                    seen.insert(x);
                    first = false;
                }
            }
            fprintf(fout, "\n");
        }
    }
    fclose(fin);
    fclose(fout);
}

void make_test_case(int id) {
    string in_name = to_string(id) + ".in";
    string out_name = to_string(id) + ".out";
    FILE* fin = fopen(in_name.c_str(), "w");

    // 梯度设计：平衡区分度与文件大小
    int T, n_limit;
    long long v_min = -2147483648LL, v_max = 2147483647LL;

    if (id == 1) { // 样例
        fprintf(fin, "2\n11\n1 2 18 3 3 19 2 3 6 5 4\n6\n1 2 3 4 5 6\n");
    } else {
        if (id <= 3) { // 30% 分数段: n <= 100
            T = 5; n_limit = 100; v_min = 0; v_max = 100;
        } else if (id <= 6) { // 60% 分数段: n <= 10^4
            T = 5; n_limit = 10000; v_min = 0; v_max = 10000;
        } else { // 100% 分数段: n = 50000
            // 降低 T 以减小文件大小 (总数字量 15w-25w，文件约 1MB-2MB)
            T = (id == 10) ? 5 : 3; 
            n_limit = 50000;
        }

        fprintf(fin, "%d\n", T);
        for (int t = 0; t < T; ++t) {
            fprintf(fin, "%d\n", n_limit);
            for (int i = 0; i < n_limit; ++i) {
                int x;
                // 构造特殊数据
                if (id == 8) x = rand_int(-100, 100); // 高频重复，测试查找性能
                else if (id == 9) x = -2000000000LL + i * 7LL; // 绝不重复，卡死 N^2 且强制输出
                else x = rand_int(v_min, v_max); // 全域随机
                
                fprintf(fin, "%d%c", x, (i == n_limit - 1 ? '\n' : ' '));
            }
        }
    }
    fclose(fin);
    generate_out(in_name, out_name);
    printf("Case %d finished.\n", id);
}

int main() {
    for (int i = 1; i <= 10; ++i) {
        make_test_case(i);
    }
    return 0;
}

测试点规划说明 (区分度设计)

教练的生成建议与优化点解析

1. 文件体积优化：

   • 通过将 Case 9 和 10 的 $T$ 设为 3 或 5，总数字量控制在 $1.5 \times 10^5 \sim 2.5 \times 10^5$。
   • 结果：单个 .in 文件大小约为 1.2MB - 1.8MB。这既能让 $O(n^2)$ 算法跑出 $10^9$ 次运算（必死），又不会让文件超出 OJ 限制。

2. 避免 INT_MIN 陷阱：

   • 在生成数据时，rand_int 使用了 long long 的分布。在输出时直接使用 %d 或 fprintf 处理 int。注意：不要对随机数求绝对值，因为 abs(-2147483648) 是未定义行为。

3. 生成效率 (剪枝/优化)：

   • 在 generate_out 中使用了 seen.reserve(n)。如果不预留空间，unordered_set 在 Case 9 这种全不重复的数据下会进行多次内存重分配（Rehash），导致生成 .out 的过程极其缓慢。预留后生成速度可提升数倍。

4. 区分度逻辑：

   • $O(n^2)$: 在 $n=50,000$ 且 $T=3$ 的情况下，计算量为 $3 \times (5 \times 10^4)^2 / 2 = 3.75 \times 10^9$ 次，在 1.0s 内绝对无法跑完。
   • $O(n \log n)$: $3 \times 5 \times 10^4 \times \log_2(5 \times 10^4) \approx 2.4 \times 10^6$ 次，轻松通过。
   • $O(n)$: 约 $1.5 \times 10^5$ 次哈希操作，极速通过。

读题关键词 (出题人/解题人视角)

• “不打乱顺序”：意味着不能先 sort 再 unique，或者排序必须带上原始索引。
• “32 位有符号整数”：确认了必须使用 Hash 或大范围离散化，不能开布尔数组。
• “T 组数据”：在生成和测试时，务必检查容器是否重置，以及总数据规模（Sum of $n$）是否会卡死程序。

你好！我是你的 OI 教练。对于这道 [JLOI2011] 的经典题目，在 $2.5 \times 10^6$ 总数据量的压力下，代码的执行效率和容器的选择至关重要。

以下是基于 C++14 标准的题解代码、复杂度深度分析及优化建议。

一、 题解标准代码 (C++14)

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

/**
 * [JLOI2011] 不重复数字
 * 核心考点：大值域下的去重（哈希应用）、快速输入输出
 */

void solve() {
    int n;
    if (!(cin >> n)) return;

    // 关键点 1：使用 unordered_set 而非 set
    // set 底层是红黑树，查询/插入是 O(log N)；unordered_set 底层是哈希表，平均 O(1)
    // 对于总计 2.5 * 10^6 的数据量，O(log N) 可能会造成 TLE。
    unordered_set<int> seen;

    // 优化：提前预留空间，减少哈希表 rehash（重构）的开销
    seen.reserve(n);

    bool first = true;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        
        // 关键点 2：利用 find 或 count 判断是否存在
        // find() == end() 表示该元素在此之前未出现过
        if (seen.find(x) == seen.end()) {
            if (!first) cout << " ";
            cout << x;
            seen.insert(x); // 存入哈希表
            first = false;
        }
    }
    cout << "\n"; // 每组数据结束后换行
}

int main() {
    // 关键点 3：极致的 I/O 优化
    // sync_with_stdio(false) 取消 C++ 与 C 缓冲区同步
    // cin.tie(nullptr) 取消 cin 与 cout 的绑定
    // 在处理百万级数据时，这是必须的操作，否则读入数据就会超时
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    if (!(cin >> t)) return 0;
    while (t--) {
        solve();
    }
    return 0;
}

二、 复杂度分析思考过程

在 NOI 竞赛中，我们需要在写代码前进行“算力估算”：

1. 时间复杂度分析

• 输入输出：总数据量约为 $T \times n = 50 \times 5 \times 10^4 = 2.5 \times 10^6$ 个整数。
  • 使用普通 cin：约需 3-5 秒（会 TLE）。
  • 使用关闭同步流的 cin：约需 0.5-0.8 秒（安全）。
• 哈希操作：
  • unordered_set 的查找和插入平均复杂度为 $O(1)$。
  • 总复杂度：$O(T \times n)$，即约 $2.5 \times 10^6$ 次基本运算。
  • 结论：在 1.0s 时限内，这个复杂度非常稳健。

2. 空间复杂度分析

• 哈希表存储：最坏情况下（所有数都不重复），unordered_set 需要存储 $5 \times 10^4$ 个 int。
• 内存计算：$5 \times 10^4 \times 4 \text{ bytes} \approx 200 \text{ KB}$。
• 结论：加上哈希表自身的指针开销，总空间远远小于 128MB 的限制。

三、 时间复杂度优化建议

如果在更高级别的比赛中，遇到 $T \times n$ 达到 $10^7$ 甚至更高，或者时限压缩到 0.2s，可以考虑以下进阶方案：

1. 手写哈希表 (Hand-written Hash Table)：

   • std::unordered_set 的常数较大。手写一个简单的“拉链法”或“开放寻址法”哈希表，性能通常能翻倍。
   • 代码提示：使用一个大质数作为 Mod（如 $999983$），用数组模拟链表。

2. 快读 (Fast Read/Write)：

   • 使用 getchar() 手写读入函数，直接解析数字字符，这是处理大规模数据的终极方案。

   inline int read() {
       int x = 0, f = 1; char ch = getchar();
       while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
       while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
       return x * f;
   }
   

3. 离散化 + 排序 (Discretization)：

   • 如果你不信任哈希（担心被构造数据卡冲突），可以将所有数连同它们的原始下标存入结构体，按数值排序。
   • 排序后相同的数会排在一起，保留下标最小的那个，最后再按原始下标排回去输出。复杂度 $O(n \log n)$，胜在稳定。

四、 易错点/坑点总结

1. 多组数据重置：seen 必须在每组数据处理前清空。在 solve 函数内部定义 unordered_set 可以利用其析构函数自动清理，但在竞赛中，为了效率，有时会定义成全局变量并手动 seen.clear()。
2. 值域陷阱：题目提到“32 位有符号整数”，意味着数值可能为负。unordered_set 可以处理负数，但如果你自己手写哈希取模，记得先对负数做处理（例如 (x % mod + mod) % mod）。
3. 输出格式：注意每行最后一个数字后是否可以带空格。大多数 OJ（包括 NOI 系统）允许行末空格，但如果不允许，需要用 first 标记位来精确控制。

你好！我是你的 OI 信息学奥赛金牌教练。今天我们来分析 [JLOI2011] 不重复数字 这道题。这道题是考察“去重”逻辑与“高效查找”数据结构的经典入门题。

一、 预备知识点

1. 哈希表 (Hash Table)：处理大值域数据去重的核心工具。
2. C++ STL 容器：
   • std::unordered_set：基于哈希表的集合（C++11/14 标准，平均复杂度 $O(1)$）。
   • std::set：基于红黑树的集合（复杂度 $O(\log n)$，在 $2.5 \times 10^6$ 总量级下可能偏慢）。
3. 快速输入输出 (Fast I/O)：处理多组数据且总量级达到 $10^6$ 时，cin/cout（不关同步）或 scanf/printf 的效率差异。
4. 离散化思想：当数值范围很大（32位整数）但数量较少时，如何映射到小范围空间。

二、 教学启发与草稿纸推理过程

1. 启发式提问

• 教练问：如果给出的数都在 $0$ 到 $10^6$ 之间，你会怎么做？
• 学生答：开一个布尔数组 vis[1000001]，扫一遍，没见过的就输出并标记。
• 教练问：现在数值范围是 $32$ 位有符号整数（约 $-2 \times 10^9$ 到 $2 \times 10^9$），数组开得下吗？
• 学生答：开不下，内存会爆。
• 教练问：我们需要在不创建超大数组的情况下，快速判断“这个数之前是否出现过”。且题目要求保留第一次出现的数，意味着我们不能打乱原始顺序。你想到了什么？

2. 草稿纸上的模拟（图形化思路）

假设输入：1 2 18 3 3 19 2

方案 A：排序法（逻辑推演）

1. 记录每个数的值和原始下标 (val, pos)。
2. 按 val 排序，相同的 val 按 pos 排序。
3. 去重后，再按 pos 重新排回来。

• 缺点：实现稍显复杂，复杂度 $O(n \log n)$。

方案 B：哈希表法（推荐思路） 准备一个“黑名单”容器（Hash Set）：

3. 复杂度与优化思考

• 时间复杂度：$T$ 组数据，每组 $n$ 个数。使用哈希表单次插入/查找平均 $O(1)$，总复杂度 $O(T \cdot n)$。
• 空间复杂度：$O(n)$，用于存储当前组内不重复的数字。
• 优化建议：
  • 由于 $T=50, n=5 \times 10^4$，总数据量为 $2.5 \times 10^6$。在 NOI 竞赛中，这种规模建议使用 scanf 或 cin.tie(0)。
  • 关键点：每组数据处理完，必须清空容器。

三、 算法流程图 (Mermaid 语法)

graph TD
    Start("开始") --> ReadT("读取数据组数 T")
    ReadT --> LoopT{"T 大于 0?"}
    
    LoopT -- "是" --> ClearSet("清空哈希容器 Set")
    ClearSet --> ReadN("读取当前组元素个数 n")
    ReadN --> LoopN{"已处理 i 小于 n?"}
    
    LoopN -- "是" --> ReadX("读取整数 x")
    ReadX --> Check{"x 是否在 Set 中?"}
    
    Check -- "不存在" --> PrintX("输出 x 并加空格")
    PrintX --> InsertX("将 x 存入 Set")
    InsertX --> NextI("i 增加 1")
    
    Check -- "已存在" --> NextI
    
    NextI --> LoopN
    
    LoopN -- "否" --> PrintNewline("输出换行符")
    PrintNewline --> DecT("T 减少 1")
    DecT --> LoopT
    
    LoopT -- "否" --> End("结束")

四、 题目描述 (NOI 竞赛格式)

不重复数字

【问题描述】 给定 $n$ 个整数，要求把其中重复的去掉，只保留第一次出现的数。

【输入格式】 本题有多组数据。 第一行一个整数 $T$，表示数据组数。 对于每组数据： 第一行一个整数 $n$，表示该组数据的数字个数。 第二行 $n$ 个整数，表示给定的序列。

【输出格式】 对于每组数据，输出一行，为去重后剩下的数，两个数之间用一个空格隔开。每组输出占一行。

【样例输入】

2
11
1 2 18 3 3 19 2 3 6 5 4
6
1 2 3 4 5 6

【样例输出】

1 2 18 3 19 6 5 4 
1 2 3 4 5 6 

【数据规模与约定】

• 对于 $30\%$ 的数据，$n \le 100$，给出的数 $\in [0, 100]$。
• 对于 $60\%$ 的数据，$n \le 10^4$，给出的数 $\in [0, 10^4]$。
• 对于 $100\%$ 的数据，$1 \le T \le 50$，$1 \le n \le 5 \times 10^4$，给出的数在 $32$ 位有符号整数范围内。
• 时间限制：1.0s
• 内存限制：128MB

五、 读题关键词总结

在 NOI 读题时，遇到此类题目的敏感词如下：

1. “保留第一次出现”：暗示不能简单排序（排序会打乱顺序），或者排序时需要记录原始位置。
2. “32 位有符号整数”：这是最关键的信号！说明数值范围在 $[-2^{31}, 2^{31}-1]$。
   • 反应：不能用数组下标计数。
   • 对策：必须使用 std::map、std::unordered_set 或手写哈希表。
3. “多组数据” (T)：
   • 反应：注意多组数据之间容器的重置（clear）。
   • 对策：检查全局变量是否在每组循环开始时正确初始化。
4. “空格隔开”：注意输出格式，最后一个数字后的空格通常不影响判题，但换行符必须准确。

教练点评：此题是检验你对“空间换时间”理解的优秀题目。对于 100% 的数据，尽量避免使用 std::set，因为其内部的红黑树维护开销在 $2.5 \times 10^6$ 的数据量面前可能会导致 TLE，建议优先考虑 std::unordered_set 或手写开放寻址法哈希。