这是一个用于生成NOI/OJ评测数据的全自动生成器。

它包含了标准解法（Solver）和数据构造逻辑（Generator）。运行后，它会在当前目录下生成 1.in/1.out 到 10.in/10.out 共20个文件，覆盖了从边界情况、特殊构造到最大规模随机数据的各种场景。

核心功能特点：

1. 自动化：一次运行生成所有测试点。
2. 覆盖全：包含空数组、全0、无解、大量重复元素、极限数据等。
3. 正确性：内置了标准的 $O(N^2)$ 标程来生成对应的 .out 文件，确保输入输出严格匹配。

使用方法：

将以下代码保存为 gen.cpp，编译并运行即可。

/**
 * NOI 风格数据生成器 - 3Sum
 * 生成文件：1.in/out ~ 10.in/out
 * 编译标准：C++14
 */

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

using namespace std;

// =========================================================
// 第一部分：标准解法 (用于生成 .out 文件)
// 算法：排序 + 双指针, 时间复杂度 O(N^2)
// =========================================================
class Solver {
public:
    // 返回格式化好的输出字符串，如果无解返回空字符串
    string solve(int n, vector<int> nums) {
        if (n < 3) return ""; // 不足3个无法组成三元组

        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        
        for (int i = 0; i < n - 2; ++i) {
            // 剪枝：如果当前数 > 0，后面肯定都 > 0，无法凑成 0
            if (nums[i] > 0) break;
            
            // 外层去重
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            
            int target = -nums[i];
            int left = i + 1;
            int right = n - 1;
            
            while (left < right) {
                long long sum = (long long)nums[left] + nums[right]; // 防止计算过程溢出
                
                if (sum == target) {
                    ans.push_back({nums[i], nums[left], nums[right]});
                    
                    left++;
                    right--;
                    
                    // 内层去重
                    while (left < right && nums[left] == nums[left - 1]) left++;
                    while (left < right && nums[right] == nums[right + 1]) right--;
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        
        string res = "";
        for (const auto& triplet : ans) {
            res += to_string(triplet[0]) + " " + to_string(triplet[1]) + " " + to_string(triplet[2]) + "\n";
        }
        return res;
    }
};

// =========================================================
// 第二部分：数据生成器 (Generator)
// =========================================================
class Generator {
    mt19937 rng;
    
public:
    Generator() {
        rng.seed(chrono::steady_clock::now().time_since_epoch().count());
    }
    
    // 生成指定范围的随机整数 [min_val, max_val]
    int random_int(int min_val, int max_val) {
        uniform_int_distribution<int> dist(min_val, max_val);
        return dist(rng);
    }
    
    // 生成测试点
    void make_case(int id, int n, int val_min, int val_max, string type = "random") {
        string file_in = to_string(id) + ".in";
        string file_out = to_string(id) + ".out";
        
        cout << "Generating Case " << id << "... (N=" << n << ", Type=" << type << ")" << endl;
        
        vector<int> a;
        
        // --- 数据构造策略 ---
        if (type == "zeros") {
            // 全是 0
            a.assign(n, 0);
        }
        else if (type == "positive") {
            // 全是正数 (无解)
            for(int i=0; i<n; ++i) a.push_back(random_int(1, val_max));
        }
        else if (type == "dense_small") {
            // 范围极小，导致大量重复
            for(int i=0; i<n; ++i) a.push_back(random_int(-2, 2));
        }
        else if (type == "boundary_struct") {
            // 构造必定有解且在边界的情况，例如 -10000, 5000, 5000
            for(int i=0; i<n/3; ++i) a.push_back(-val_max);
            for(int i=n/3; i<2*n/3; ++i) a.push_back(val_max/2);
            for(int i=2*n/3; i<n; ++i) a.push_back(val_max/2);
            // 补齐并打乱
            while(a.size() < n) a.push_back(0);
            shuffle(a.begin(), a.end(), rng);
        }
        else {
            // 默认随机
            for(int i=0; i<n; ++i) a.push_back(random_int(val_min, val_max));
        }
        
        // 1. 写入 .in 文件
        ofstream fout(file_in);
        fout << n << "\n";
        for (int i = 0; i < n; ++i) {
            fout << a[i] << (i == n - 1 ? "" : " ");
        }
        fout << "\n";
        fout.close();
        
        // 2. 调用 Solver 生成 .out 文件
        Solver solver;
        string ans = solver.solve(n, a);
        
        ofstream fsol(file_out);
        fsol << ans; // 如果 ans 为空，则生成空文件（符合题意）
        fsol.close();
    }
};

int main() {
    Generator gen;
    
    // 题目约束：N <= 3000, Val [-10^5, 10^5]
    const int MAX_VAL = 100000;
    
    // 1. 边界测试：N=0 (空数组)
    gen.make_case(1, 0, 0, 0, "random");
    
    // 2. 边界测试：N=3, 刚好一组解
    // 手动覆盖一下确保有解
    {
        ofstream fout("2.in");
        fout << "6\n-1 0 1 2 -1 -4\n";
        fout.close();
        Solver s;
        ofstream fsol("2.out");
        fsol << s.solve(6, {-1, 0, 1, 2, -1, -4});
        fsol.close();
        cout << "Generating Case 2... (Sample)" << endl;
    }

    // 3. 特殊情况：全为 0 (大量重复解需去重为 0 0 0)
    gen.make_case(3, 50, 0, 0, "zeros");
    
    // 4. 特殊情况：无解 (全正数)
    gen.make_case(4, 100, 1, 100, "positive");
    
    // 5. 压力测试：去重逻辑 (值域极小 [-2, 2]，N=500)
    // 这会产生极其大量的重复三元组，考验去重效率
    gen.make_case(5, 500, -2, 2, "dense_small");
    
    // 6. 随机数据：中小规模
    gen.make_case(6, 500, -1000, 1000, "random");
    
    // 7. 随机数据：大规模 N=2000
    gen.make_case(7, 2000, -MAX_VAL, MAX_VAL, "random");
    
    // 8. 随机数据：最大规模 N=3000
    gen.make_case(8, 3000, -MAX_VAL, MAX_VAL, "random");
    
    // 9. 构造数据：最大规模 N=3000，但解比较稀疏 (值域很大)
    // 随机范围大，命中0的概率低
    gen.make_case(9, 3000, -MAX_VAL, MAX_VAL, "random");
    
    // 10. 构造数据：最大规模 N=3000，特定结构
    // 构造 {-10000, 5000, 5000} 这种形式，确保即便在大数据下也有解
    gen.make_case(10, 3000, 10000, 10000, "boundary_struct");

    cout << "All test data generated successfully!" << endl;
    
    return 0;
}

测试点详细设计说明

提示

• 由于 N=3000 时，$O(N^2)$ 大约运算 $9 \times 10^6$ 次，生成器生成最后几个点时可能需要几秒钟，这是正常的。
• 生成的 .out 文件已经严格按照字典序排序（因为代码中先 sort 原数组，双指针寻找时也是按顺序的），可以直接用于 OJ 判题。

你好！我是你的OI金牌教练。

刚才我们已经理清了思路，现在是“真刀真枪”写代码的时候了。在考场上，代码的正确性（逻辑无误）、鲁棒性（边界处理）和规范性（易读易调试）同样重要。

下面这份代码是严格按照 NOI/NOIP C++14 标准编写的，我不仅在关键逻辑处加了详细注释，还特意标注了**“易错点”**，这些都是历年考生容易丢分的地方，请务必仔细阅读。

NOI 标准 C++14 题解代码

/**
 * 题目：寻找零和三元组 (3Sum)
 * 算法：排序 + 双指针 (Sorting + Two Pointers)
 * 复杂度：O(N^2)
 * 风格：NOI C++14 标准
 */

#include <iostream>
#include <vector>
#include <algorithm> // 包含 sort

using namespace std;

// 全局常量定义，方便根据数据范围调整
const int MAXN = 3005; 

// 核心解题函数
void solve() {
    int n;
    // 易错点1：读入检测。虽然竞赛题通常数据格式标准，但养成检查读入的好习惯能防范空文件等异常
    if (!(cin >> n)) return;

    // 此时 vector 优于静态数组，因为可以用 size() 和方便的迭代器
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    // ---------------------------------------------------------
    // 关键步骤 1：排序
    // 目的：1. 方便去重（相同的数聚在一起）；2. 使用双指针的前提（单调性）
    // 时间复杂度：O(N log N)
    // ---------------------------------------------------------
    sort(a.begin(), a.end());

    // 存储结果，避免直接输出导致 I/O 次数过多影响效率
    vector<vector<int>> ans;

    // ---------------------------------------------------------
    // 关键步骤 2：固定第一个数 a[i]，转化为 2Sum 问题
    // 时间复杂度：O(N^2)
    // ---------------------------------------------------------
    for (int i = 0; i < n - 2; ++i) { // 注意边界：后面至少还要留两个位置给 j 和 k
        
        // 【优化点 1】：剪枝
        // 因为数组有序，如果当前数 a[i] 已经大于 0，
        // 那么后面的数肯定也都大于 0，三数之和不可能为 0，直接结束循环。
        if (a[i] > 0) break; 

        // 【易错点 2】：外层循环去重
        // 如果当前数 a[i] 和上一个数 a[i-1] 相同，
        // 说明这种情况在上一轮循环中已经处理过了，必须跳过，否则会产生重复三元组。
        // 注意必须是 i > 0 防止越界。
        if (i > 0 && a[i] == a[i - 1]) continue;

        // 双指针初始化
        int left = i + 1;
        int right = n - 1;
        int target = -a[i]; // 我们要找 a[left] + a[right] == -a[i]

        while (left < right) {
            // 注意：虽然题目范围 -10^5 到 10^5 加起来不会爆 int，
            // 但如果题目数据范围更大，这里求和建议用 long long 防止溢出。
            int sum = a[left] + a[right];

            if (sum == target) {
                // 找到一组解
                ans.push_back({a[i], a[left], a[right]});

                // 【易错点 3】：找到解后，左右指针必须同时移动
                // 光移动一个指针肯定不满足条件（因为数组有序，和会变）
                left++;
                right--;

                // 【易错点 4】：内层循环去重
                // 移动后，如果发现新位置的数和刚才一样，继续移动，直到不同为止。
                // 必须检查 left < right 防止越界。
                while (left < right && a[left] == a[left - 1]) left++;
                while (left < right && a[right] == a[right + 1]) right--;
            } 
            else if (sum < target) {
                // 和太小了，需要变大 -> 左指针右移
                left++;
            } 
            else { // sum > target
                // 和太大了，需要变小 -> 右指针左移
                right--;
            }
        }
    }

    // 输出结果
    for (const auto& triplet : ans) {
        cout << triplet[0] << " " << triplet[1] << " " << triplet[2] << "\n";
    }
}

int main() {
    // 【竞赛标配】：关闭同步流，加速 I/O
    // 遇到大数据量（如 N=3000 输出量可能很大）时，这一步至关重要
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();

    return 0;
}

复杂度分析与思考过程

在竞赛中，写完代码后的第一件事不是提交，而是自测复杂度和极限数据。

1. 时间复杂度 (Time Complexity)

• 推导过程：
  • 排序：std::sort 使用的是快速排序/堆排序的混合变种，平均时间复杂度为 $O(N \log N)$。
  • 外层循环：变量 $i$ 从 $0$ 遍历到 $N-2$，大约执行 $N$ 次。
  • 内层双指针：对于每个固定的 $i$，left 和 right 指针分别从两端向中间移动，每个元素最多被访问一次。所以内层复杂度是 $O(N)$。
  • 总复杂度：$O(N \log N) + O(N \times N) = O(N^2)$。
• 实际评估：
  • 题目给的数据范围 $N \le 3000$。
  • 代入计算量：$3000^2 = 9 \times 10^6$，即 900 万次运算。
  • C++ 在 1 秒内通常能处理 $10^8$（1 亿）次运算。
  • 结论：$9 \times 10^6 \ll 10^8$，该算法在 1 秒内绰绰有余，可以通过。

2. 空间复杂度 (Space Complexity)

• 推导过程：
  • 我们只使用了几个整型变量（i, left, right, sum 等）和输入数组 a。
  • std::sort 在 C++ 实现中通常需要 $O(\log N)$ 的栈空间。
  • ans 数组用于存储结果，这部分空间取决于答案的数量（Output Sensitive），但在算法评估中通常只看辅助空间。
  • 结论：辅助空间复杂度为 $O(1)$ 或 $O(\log N)$（取决于排序实现）。这远低于 256MB 的内存限制。

时间复杂度优化建议（进阶 Coach Tip）

虽然 $O(N^2)$ 已经足够 AC（Accepted），但在某些卡常数（Time Limit 很紧）的情况下，我们可以进一步做一些微小的优化：

1. 极值剪枝 (Min/Max Pruning)： 在固定 $a[i]$ 后，我们可以快速判断这一轮是否有必要进行：

   • 最小和过大：计算当前能凑出的最小和 min_sum = a[i] + a[i+1] + a[i+2]。如果 min_sum > 0，说明这一轮以及后续所有轮次（因为 $i$ 增加数变大）都不可能凑出 0 了，直接 break（比简单的 a[i]>0 更强）。
   • 最大和过小：计算当前能凑出的最大和 max_sum = a[i] + a[n-2] + a[n-1]。如果 max_sum < 0，说明仅靠当前的 $a[i]$ 即使加上最大的两个数也不够，那么当前的 $a[i]$ 肯定无解，直接 continue 进入下一个 $i$。

   代码实现片段：

   for (int i = 0; i < n - 2; ++i) {
       if (i > 0 && a[i] == a[i - 1]) continue;
   
       // 强力剪枝 1：最小可能和都 > 0，后面没戏了
       if (a[i] + a[i + 1] + a[i + 2] > 0) break;
       
       // 强力剪枝 2：当前最大可能和都 < 0，这个 a[i] 太小了，换下一个试试
       if (a[i] + a[n - 2] + a[n - 1] < 0) continue; 
       
       // ... 接原来的双指针逻辑
   }
   

教练总结： 这道题是考察思维严密性的绝佳题目。看似简单，但处理不好“重复”和“边界”就会丢分。请在草稿纸上模拟一遍 [-1, -1, 0, 1] 的去重过程，确保你完全理解了 continue 和 while 循环的作用。加油！