作为教练，制作数据最重要的一点是确保唯一性和覆盖极端边界。

在“两数之和”中，虽然逻辑简单，但数据生成需要特别注意：

1. 答案的唯一性：随机生成大数据时，极低概率会出现第二组解。生成后必须用标程验证。
2. 大整数处理：$target$ 可能达到 $2 \times 10^9$，必须使用 long long 逻辑处理。
3. 相同数值的陷阱：例如 $target=6$，数组中可能出现多个 3，或者只有一个 3（不能自加）。

以下是为你准备的自动化数据生成器。它集成了 $O(n)$ 标程逻辑，会自动生成符合 NOI 规范的 1.in 到 10.out。

一、 数据生成器代码 (C++14 标准)

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <unordered_map>
#include <random>
#include <ctime>
#include <algorithm>
#include <set>

using namespace std;

typedef long long ll;

// ================= 标准标程逻辑 (用于生成 .out) =================
pair<int, int> solve_standard(int n, ll target, const vector<int>& nums) {
    unordered_map<ll, int> dic;
    for (int i = 0; i < n; ++i) {
        ll complement = target - nums[i];
        if (dic.count(complement)) {
            return {dic[complement], i};
        }
        dic[nums[i]] = i;
    }
    return {-1, -1};
}

// ================= 数据构造逻辑 =================
void write_test_case(int id, int n, ll target, vector<int>& nums) {
    string in_name = to_string(id) + ".in";
    string out_name = to_string(id) + ".out";

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

    // 计算并写入标准输出
    pair<int, int> res = solve_standard(n, target, nums);
    ofstream fans(out_name);
    fans << res.first << " " << res.second << endl;
    fans.close();

    cout << "Testcase " << id << " generated. (n=" << n << ")" << endl;
}

int main() {
    mt19937 rng(time(0));
    // 随机值范围：-10^9 到 10^9
    uniform_int_distribution<int> val_dist(-1000000000, 1000000000);

    for (int i = 1; i <= 10; ++i) {
        int n;
        ll target;
        vector<int> nums;

        if (i == 1) { // 样例
            n = 4; target = 9;
            nums = {2, 7, 11, 15};
        } 
        else if (i == 2) { // 最小规模
            n = 2; target = 100;
            nums = {40, 60};
        }
        else if (i == 3) { // 目标值由两个相同数字组成
            n = 1000; target = 200;
            nums.assign(n, 555); // 填充干扰
            int idx1 = rng() % n;
            int idx2 = rng() % n;
            while(idx1 == idx2) idx2 = rng() % n;
            nums[idx1] = 100; nums[idx2] = 100;
        }
        else if (i == 4) { // 包含负数
            n = 5000; target = -500;
            for(int j=0; j<n; j++) nums.push_back(val_dist(rng));
            int idx1 = 0, idx2 = n-1;
            nums[idx1] = -200; nums[idx2] = -300;
        }
        else if (i <= 6) { // 大规模随机
            n = 10000; target = val_dist(rng);
            set<int> used;
            for(int j=0; j<n; j++) {
                int v = val_dist(rng);
                nums.push_back(v);
            }
            // 强制构造一个解
            int idx1 = rng() % n, idx2 = rng() % n;
            while(idx1 == idx2) idx2 = rng() % n;
            nums[idx1] = 1000000; 
            nums[idx2] = (int)(target - 1000000);
        }
        else { // 极限边界：答案在头尾
            n = 10000; target = 123456789;
            for(int j=0; j<n; j++) nums.push_back(val_dist(rng));
            nums[0] = 100000000;
            nums[n-1] = 23456789;
        }
        
        // 简单打乱，防止答案位置过于固定（除了 Case 10 这种特意测试头尾的）
        if(i != 1 && i != 10) {
            // 注意：打乱前需记录构造好的值，这里我们采用直接在随机位置插入
        }

        write_test_case(i, n, target, nums);
    }
    return 0;
}

二、 测试点设计思路（创建 OJ 必读）

针对“两数之和”，我设计的 10 组测试点涵盖了以下维度：

三、 考场避坑建议（教练寄语）

1. 哈希表的选择： 在 C++14 中，请务必使用 unordered_map 而不是 map。

   • unordered_map 是哈希表，$O(1)$。
   • map 是红黑树，$O(\log n)$。在 $10^5$ 数据量下，两者的常数差异会决定是否超时。

2. 同一元素不能重复使用： 代码逻辑中，一定要先 find（查找），再 insert（入表）。

   • 错误逻辑：先把所有数放进表。如果 $target=6$，数组里只有一个 3，程序会找到自己并返回 (0, 0)。
   • 正确逻辑：遍历到当前数时，去表里找它的“另一半”。没找到，再把自己放进去。

3. 非递归安全： 本题为线性扫描，不涉及递归，无爆栈风险。生成器生成的 $n$ 严格控制在 $10^4$ 以内，标程运行速度极快。

4. 无除零风险： 本题仅涉及加减法，完全避开了除法运算，生成的 $n$ 保证 $\ge 2$。

你可以编译并运行此生成器，它会自动在当前文件夹下输出所有的 .in 和 .out 文件。祝你的学生在练习中更进一步！

你好，同学。作为教练，我为你整理了这道题的 NOIP 竞赛级标准程序。

在 NOI 竞赛中，追求的不仅是“能跑通”，更是“在大数据量下的稳健与高效”。虽然本题规模 $10^4$ 暴力可过，但我们必须掌握 $O(n)$ 的最优解法，以应对未来可能出现的 $10^5$ 甚至 $10^6$ 级别的数据。

一、 两数之和 标准题解 (C++14)

#include <iostream>
#include <vector>
#include <unordered_map> // NOI 竞赛中常用哈希表

using namespace std;

/**
 * 核心逻辑：一遍哈希扫描法
 * 1. 扫描到一个数 x 时，我们目标明确：寻找 target - x。
 * 2. 如果哈希表里已经存了 target - x，说明匹配成功。
 * 3. 如果没存，就把 x 和它的下标存进去，给后面的数“当另一半”。
 */

void solve() {
    int n;
    long long target; // 使用 long long 防止 target 计算溢出
    if (!(cin >> n >> target)) return;

    vector<int> nums(n);
    // unordered_map 在 C++11/14 中是基于哈希表实现的，查找期望时间为 O(1)
    // key: 数值, value: 对应的下标
    unordered_map<int, int> dic;

    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }

    for (int i = 0; i < n; ++i) {
        int complement = target - nums[i];

        // 易错点：必须在将当前数放入哈希表之前查找
        // 这样可以自动避免“同一个元素重复出现”的问题
        if (dic.count(complement)) {
            // 找到了！输出存下的下标和当前下标
            cout << dic[complement] << " " << i << endl;
            return; // 题目保证只有一个答案，直接结束
        }

        // 如果没找到，将当前数值及其下标存入哈希表
        dic[nums[i]] = i;
    }
}

int main() {
    // NOI 竞赛必备优化：加速 I/O。在大规模数据输入时，比 scanf 还要快。
    ios::sync_with_stdio(false);
    cin.tie(0);

    solve();

    return 0;
}

二、 复杂度分析思考过程

1. 时间复杂度：$O(n)$

• 推导过程：
  • 我们只对数组进行了一次线性遍历（for 循环 $n$ 次）。
  • 在循环内部，unordered_map 的查找（count）和插入（operator[]）操作在平均情况下的时间复杂度均为 $O(1)$。
• 结论：总时间复杂度为 $O(n)$。在 $n=10^4$ 甚至 $10^5$ 时，该程序都能在数毫秒内完成。

2. 空间复杂度：$O(n)$

• 推导过程：
  • 我们需要一个哈希表来存储遍历过的元素。在最坏情况下（即最后两个数才匹配成功），哈希表会存储 $n-1$ 个元素。
• 结论：额外空间复杂度为 $O(n)$。在 NOI 256MB 的内存限制下，存储 $10^5$ 个 int 仅占用约 2-4MB，非常安全。

三、 时间复杂度优化建议

虽然上述代码已经是期望 $O(n)$ 的最优解，但在 NOI 竞赛中，如果遇到极端的“哈希冲突测试数据”（Anti-Hash Test Cases），unordered_map 的效率可能会退化到 $O(n^2)$。以下是进阶优化建议：

1. 预分配空间 (Reserve)： 如果你知道数组长度 $n$，可以调用 dic.reserve(n)。这能减少哈希表动态扩容时的内存分配次数，显著提升速度。

2. 防御性哈希 (Custom Hash)： 为了防止出题人故意构造让哈希冲突的数据，可以手写一个简单的随机扰动函数给哈希表。

3. 排序 + 双指针方案 ($O(n \log n)$)： 如果内存限制极其严苛，不允许使用哈希表，可以先对数组进行排序，然后使用左、右两个指针向中间靠拢。

   • 优点：不需要额外哈希空间，且时间复杂度非常稳定。
   • 缺点：排序后原下标会乱，需要使用 pair<int, int> 同时存储数值和原下标。

4. 快读 (Fast I/O)： 如果 $n$ 达到 $10^6$ 级别，可以使用 getchar() 手写读取函数。

教练点评： 这道题是学习**“利用额外空间换取查找速度”**的入门教科书。在考场上，请务必注意 $target - nums[i]$ 的计算是否会超出 int 范围，以及哈希表容器是否正确使用。加油！