C++ 标准解答 (NOIP C++14)

/**
 * 题目: 湿地保护区的物种名录 (Species List)
 * 作者: Isaac Asimov (AI)
 * 知识点: std::vector 的基本操作 (push_back, pop_back, traversal)
 */

#include <iostream>
#include <vector>

using namespace std;

// 定义 vector 数组
// zones[i] 代表第 i 号观测区的列表
// 全局变量，开在堆/静态区，防栈溢出
const int MAXN = 100005;
vector<int> zones[MAXN]; 

int main() {
    // IO 优化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    for (int i = 0; i < m; i++) {
        int op;
        cin >> op;

        if (op == 1) {
            // 操作 1: 记录 (push_back)
            int id, species_val;
            cin >> id >> species_val;
            zones[id].push_back(species_val);
        }
        else if (op == 2) {
            // 操作 2: 修正 (pop_back)
            int id;
            cin >> id;
            // 关键点：pop_back 前必须确保不为空，否则未定义行为(UB)
            if (!zones[id].empty()) {
                zones[id].pop_back();
            }
        }
        else if (op == 3) {
            // 操作 3: 归档 (遍历输出)
            int id;
            cin >> id;

            if (zones[id].empty()) {
                cout << "Empty" << endl;
            } else {
                // C++11/14 范围 for 循环，简洁明了
                // 也可以用 for(int j=0; j<zones[id].size(); j++)
                bool first = true;
                for (int val : zones[id]) {
                    if (!first) cout << " ";
                    cout << val;
                    first = false;
                }
                cout << endl;
            }
        }
    }

    return 0;
}

数据生成器 (Generator)

生成器会模拟观测过程，包含各种边界情况（如对空列表进行 pop 操作）。

请保存为 gen_vector.cpp 并运行。

/**
 * Project: Species List (Vector Data Generator)
 * Author: Isaac Asimov (AI)
 */

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

using namespace std;

// ==========================================
// Part 1: 标准解答逻辑
// ==========================================
class Solution {
public:
    void solve(string in_file, string out_file) {
        ifstream cin(in_file);
        ofstream cout(out_file);
        if (!cin.is_open()) return;

        int n, m;
        cin >> n >> m;
        
        // 动态分配 vector 数组，或者使用 vector<vector<int>>
        vector<vector<int>> zones(n + 1);

        for (int i = 0; i < m; i++) {
            int op;
            cin >> op;
            if (op == 1) {
                int id, x; cin >> id >> x;
                zones[id].push_back(x);
            } else if (op == 2) {
                int id; cin >> id;
                if (!zones[id].empty()) zones[id].pop_back();
            } else {
                int id; cin >> id;
                if (zones[id].empty()) cout << "Empty" << endl;
                else {
                    for(size_t k=0; k<zones[id].size(); k++) {
                        cout << zones[id][k] << (k == zones[id].size()-1 ? "" : " ");
                    }
                    cout << endl;
                }
            }
        }
        
        cin.close();
        cout.close();
        cout << "Generated: " << out_file << endl;
    }
};

// ==========================================
// Part 2: 数据生成逻辑
// ==========================================
mt19937 rng(2025);

int rand_int(int min, int max) {
    uniform_int_distribution<int> dist(min, max);
    return dist(rng);
}

void generate_input(int case_id) {
    string filename = to_string(case_id) + ".in";
    ofstream fout(filename);

    int n, m;

    // 1-3: 小规模测试
    if (case_id <= 3) {
        n = 3; m = 10;
    } 
    // 4-6: 中等规模
    else if (case_id <= 6) {
        n = 100; m = 1000;
    } 
    // 7-10: 大规模压力测试
    else {
        n = 10000; m = 100000;
    }

    fout << n << " " << m << endl;

    // 追踪每个区域的大小，以便生成合理的 pop 操作
    vector<int> current_sizes(n + 1, 0);

    for (int i = 0; i < m; i++) {
        int op;
        int dice = rand_int(1, 100);

        // 随机选择一个区域
        int id = rand_int(1, n);

        // 概率控制
        // Case 5: 专门测试空弹出 (pop empty)
        if (case_id == 5) {
            if (dice <= 60) op = 2; // 60% 概率删除
            else op = 1;
        }
        else {
            // 常规：60% 插入, 20% 删除, 20% 查询
            if (dice <= 60) op = 1;
            else if (dice <= 80) op = 2;
            else op = 3;
        }

        if (op == 1) {
            // Record
            int species = rand_int(100, 999); // 简化的物种ID
            fout << op << " " << id << " " << species << endl;
            current_sizes[id]++;
        }
        else if (op == 2) {
            // Pop
            fout << op << " " << id << endl;
            if (current_sizes[id] > 0) current_sizes[id]--;
        }
        else {
            // Query
            fout << op << " " << id << endl;
        }
    }

    fout.close();
}

int main() {
    ios_base::sync_with_stdio(false);
    cout << "--- Generating Species List Data ---" << endl;
    
    Solution solver;
    for (int i = 1; i <= 10; i++) {
        generate_input(i);
        string in = to_string(i) + ".in";
        string out = to_string(i) + ".out";
        solver.solve(in, out);
    }
    cout << "--- Done! ---" << endl;
    return 0;
}

阿西莫夫的点评

1. 为什么不用数组？ 如果用二维数组 int a[N][M]，你需要开 100000 * 100000 的空间，这在任何 OJ 上都会直接 Memory Limit Exceeded (MLE)。只有 vector 能做到“用多少开多少”。
2. 生物学意义： 这模拟了真实的**野外采样（Sampling）**过程。样本数量是不均匀分布的（Clumped Distribution），这正是动态数据结构存在的意义。
3. 防坑点： 再次强调，pop_back() 之前不检查 empty() 是导致程序崩溃的头号杀手。

希望这道题能帮助学生们在保护生物多样性的同时，掌握 C++ 最强大的容器——Vector。