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

/**
 * 题目：培养皿中的生存游戏 (The Game of Cellular Survival)
 * 算法：模拟 / 元胞自动机 (Simulation / Cellular Automaton)
 * 难度：GESP 5级 / CSP-J T2
 */

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
    // 1. I/O 加速
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, T;
    if (!(cin >> N >> T)) return 0;

    string s_input;
    cin >> s_input;

    // 2. 数据结构准备
    // 我们使用 int 数组来存储状态，0表示空，1表示活
    // 大小开 N+2，其中下标 0 和 N+1 是“哨兵”，永远为 0
    // 实际有效数据存储在 1 到 N
    vector<int> current(N + 2, 0);
    vector<int> next_state(N + 2, 0);

    // 初始化 current 数组
    for (int i = 0; i < N; ++i) {
        // s_input 的下标是 0 到 N-1
        // current 的下标映射到 1 到 N
        current[i + 1] = s_input[i] - '0';
    }

    // 3. 开始模拟 T 轮
    for (int t = 0; t < T; ++t) {
        // 遍历每一个有效格子
        for (int i = 1; i <= N; ++i) {
            // 统计左右邻居数量 (利用哨兵，不需要判断边界)
            int neighbors = current[i - 1] + current[i + 1];

            if (current[i] == 1) {
                // 原来是活细胞
                if (neighbors == 2 || neighbors == 0) {
                    next_state[i] = 0; // 拥挤或孤单 -> 死
                } else {
                    next_state[i] = 1; // 适宜 -> 活
                }
            } else {
                // 原来是空位
                if (neighbors == 2) {
                    next_state[i] = 1; // 繁殖 -> 生
                } else {
                    next_state[i] = 0; // 维持空
                }
            }
        }

        // 4. 更新状态：将 next_state 复制给 current，准备下一轮
        // 也可以使用 current = next_state，但在 C++ vector 中这会发生拷贝
        // 这里的拷贝开销对于 N=1000 来说微乎其微
        current = next_state;
    }

    // 5. 输出结果
    for (int i = 1; i <= N; ++i) {
        cout << current[i];
    }
    cout << endl;

    return 0;
}

时间与空间复杂度

• 时间复杂度：外层循环 $T$ 次，内层循环 $N$ 次。总复杂度 $O(N \times T)$。
• 空间复杂度：使用了两个长度为 $N$ 的辅助数组。$O(N)$。

六、 数据生成器 (Generator.cpp)

/**
 * 题目：培养皿中的生存游戏
 * 数据生成器
 */

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

using namespace std;

mt19937 rng(time(0));

// 核心解法 (用于生成 .out)
string solve(int N, int T, string S) {
    vector<int> cur(N + 2, 0);
    vector<int> nxt(N + 2, 0);
    for(int i=0; i<N; ++i) cur[i+1] = S[i] - '0';

    for(int t=0; t<T; ++t) {
        for(int i=1; i<=N; ++i) {
            int neighbors = cur[i-1] + cur[i+1];
            if(cur[i] == 1) {
                if(neighbors == 2 || neighbors == 0) nxt[i] = 0;
                else nxt[i] = 1;
            } else {
                if(neighbors == 2) nxt[i] = 1;
                else nxt[i] = 0;
            }
        }
        cur = nxt;
    }
    
    string res = "";
    for(int i=1; i<=N; ++i) res += to_string(cur[i]);
    return res;
}

void make_case(int id) {
    int N, T;
    string S;

    switch(id) {
        case 1: // 样例
            N = 7; T = 1; S = "0101010";
            break;
        case 2: // 极小数据
            N = 3; T = 1; S = "101";
            break;
        case 3: // 静态平衡 (11111 -> 中间死, 两边活?)
            N = 10; T = 5; S = "1111111111";
            break;
        case 4: // 全空
            N = 20; T = 100; for(int i=0; i<N; ++i) S+='0';
            break;
        case 5: // 孤立点
            N = 20; T = 10; S = "00000010000000";
            break;
        case 6: // 随机小数据
            N = 50; T = 50;
            for(int i=0; i<N; ++i) S += (rng()%2 ? '1':'0');
            break;
        case 7: // 随机中数据
            N = 200; T = 200;
            for(int i=0; i<N; ++i) S += (rng()%2 ? '1':'0');
            break;
        case 8: // 满级数据 1
            N = 1000; T = 500;
            for(int i=0; i<N; ++i) S += (rng()%2 ? '1':'0');
            break;
        case 9: // 满级数据 2 (T很大)
            N = 1000; T = 1000;
            for(int i=0; i<N; ++i) S += (rng()%2 ? '1':'0');
            break;
        case 10: // 边界测试 (两头活，中间空)
            N = 1000; T = 100;
            S += '1';
            for(int i=1; i<N-1; ++i) S+='0';
            S += '1';
            break;
    }

    string in_file = to_string(id) + ".in";
    ofstream fout_in(in_file);
    fout_in << N << " " << T << "\n" << S << "\n";
    fout_in.close();

    string out_file = to_string(id) + ".out";
    ofstream fout_out(out_file);
    fout_out << solve(N, T, S) << "\n";
    fout_out.close();
    
    cout << "Generated Case " << id << endl;
}

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