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

/**
 * 题目: 小肠绒毛的“流水线” (The Intestinal Queue)
 * 作者: Isaac Asimov (AI)
 * 知识点: std::queue 的基本操作
 */

#include <iostream>
#include <string>
#include <queue>  // 必须包含 queue 头文件

using namespace std;

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

    int n;
    cin >> n;

    // 定义一个存储字符串的队列
    queue<string> q;

    for (int i = 0; i < n; i++) {
        int type;
        cin >> type;

        if (type == 1) {
            // 摄入操作: 入队
            string name;
            cin >> name;
            q.push(name);
        }
        else if (type == 2) {
            // 吸收操作: 出队
            // 【关键】必须先判断非空
            if (q.empty()) {
                cout << "Empty" << endl;
            } else {
                // 先获取队首元素
                cout << q.front() << endl;
                // 再将其移除
                q.pop();
            }
        }
        else if (type == 3) {
            // 查询操作: 获取大小
            cout << q.size() << endl;
        }
    }

    return 0;
}

数据生成器 (Generator)

这个生成器会生成一系列随机的摄入、吸收和查询操作，并包含“空队列取数”的边界情况。

请保存为 gen_queue.cpp 并运行。

/**
 * Project: The Intestinal Queue (Data Generator)
 * Author: Isaac Asimov (AI)
 */

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

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;
        cin >> n;
        queue<string> q;

        for (int i = 0; i < n; i++) {
            int type;
            cin >> type;
            if (type == 1) {
                string s; cin >> s;
                q.push(s);
            } else if (type == 2) {
                if (q.empty()) cout << "Empty" << endl;
                else {
                    cout << q.front() << endl;
                    q.pop();
                }
            } else {
                cout << q.size() << 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);
}

// 常见营养物质列表
vector<string> nutrients = {
    "Glucose", "AminoAcid", "FattyAcid", "Water", "VitaminC", 
    "VitaminD", "Sodium", "Potassium", "Iron", "Calcium",
    "Fructose", "Galactose", "Glycerol", "Chloride"
};

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

    int n;

    // 规模控制
    if (case_id <= 3) n = rand_int(10, 20);
    else if (case_id <= 7) n = rand_int(100, 1000);
    else n = rand_int(10000, 100000); // 压力测试

    fout << n << endl;

    // 模拟队列当前的实际大小，用于控制生成逻辑
    // 避免生成太多无效的 pop 操作
    int current_size = 0;

    for (int i = 0; i < n; i++) {
        int type;
        
        // 概率控制操作类型
        int dice = rand_int(1, 100);
        
        if (case_id == 5) {
            // Case 5: 疯狂弹出测试 (Empty test)
            if (dice <= 70) type = 2; // 70% 概率弹出
            else type = 1;
        }
        else if (case_id == 6) {
            // Case 6: 疯狂堆积测试
            if (dice <= 80) type = 1; // 80% 概率入队
            else type = 2;
        }
        else {
            // 常规随机
            if (dice <= 50) type = 1;       // 50% 入队
            else if (dice <= 90) type = 2;  // 40% 出队
            else type = 3;                  // 10% 查询
        }

        fout << type;
        if (type == 1) {
            string name = nutrients[rand_int(0, nutrients.size() - 1)];
            // 偶尔加个编号区分同名物质
            if (rand_int(0, 1)) name += "_" + to_string(rand_int(1, 100));
            fout << " " << name;
            current_size++;
        }
        else if (type == 2) {
            if (current_size > 0) current_size--;
        }
        fout << endl;
    }

    fout.close();
}

int main() {
    ios_base::sync_with_stdio(false);
    cout << "--- Generating Intestinal Queue 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;
}

阿西莫夫的点评

这道题虽然简单，但它是通往更复杂数据结构（如 BFS 广度优先搜索）的必经之路。

• 生物学隐喻：通过“食糜的流动”，学生可以直观地理解 Queue 与 Stack 的区别——消化道不能“后进先出”（否则那就叫呕吐了，那可是病理状态）。
• 工程细节：在 pop 之前检查 empty，是每个写代码的人必须养成的安全习惯，就像过马路前要看红绿灯一样。