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

/**
 * 题目：DNA聚合酶的校对 (DNA Polymerase's Proofreading)
 * 算法：栈 / 字符串模拟 (Stack / String Simulation)
 * 难度：GESP 5级 / CSP-J T2
 */

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

using namespace std;

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

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

    string commands;
    cin >> commands;

    // 2. 使用 string 模拟栈
    // string 在 C++ 中既是字符串，也是一个支持 push/pop 的容器
    string dna_chain = "";

    // 3. 遍历指令
    for (char cmd : commands) {
        if (cmd == 'X') {
            // 校对功能：删除末尾碱基
            // 关键点：操作前必须检查是否为空
            if (!dna_chain.empty()) {
                dna_chain.pop_back();
            }
        } else {
            // 聚合功能：添加碱基
            dna_chain.push_back(cmd);
        }
    }

    // 4. 输出结果
    cout << dna_chain << endl;

    return 0;
}

时间与空间复杂度分析

• 时间复杂度：
  • 我们需要遍历输入字符串 commands 一次，长度为 $N$。
  • 在循环内部，push_back 和 pop_back 都是摊销 $O(1)$ 的操作。
  • 总时间复杂度：$O(N)$。对于 $N=10^6$，轻松在 1 秒内完成。
• 空间复杂度：
  • 需要存储输入指令和最终的 DNA 链。
  • 最坏情况下（没有 X），DNA 链长度为 $N$。
  • 总空间复杂度：$O(N)$。

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

/**
 * 题目：DNA聚合酶的校对
 * 数据生成器
 */

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

using namespace std;

mt19937 rng(time(0));
const char OPTS[] = {'A', 'T', 'C', 'G', 'X'};

// 核心解法
string solve(int N, string S) {
    string res = "";
    for(char c : S) {
        if(c == 'X') {
            if(!res.empty()) res.pop_back();
        } else {
            res.push_back(c);
        }
    }
    return res;
}

void make_case(int id) {
    int N;
    string S = "";

    switch(id) {
        case 1: // 样例
            N = 10; S = "ATCGXXACGT";
            break;
        case 2: // 极小数据
            N = 5; S = "AXAXA";
            break;
        case 3: // 全是添加
            N = 100; 
            for(int i=0; i<N; ++i) S += OPTS[rng()%4]; // only ATCG
            break;
        case 4: // 全是删除
            N = 100;
            for(int i=0; i<N; ++i) S += 'X';
            break;
        case 5: // 删比加多（最终为空）
            N = 1000;
            for(int i=0; i<N; ++i) {
                // 60% 概率 X
                if(rng()%10 < 6) S += 'X';
                else S += OPTS[rng()%4];
            }
            break;
        case 6: // 波动（加加减加减减）
            N = 1000;
            for(int i=0; i<N; ++i) {
                // 30% 概率 X
                if(rng()%10 < 3) S += 'X';
                else S += OPTS[rng()%4];
            }
            break;
        case 7: // 大数据平衡
            N = 100000;
            for(int i=0; i<N; ++i) {
                if(rng()%10 < 2) S += 'X'; // 20% 删除
                else S += OPTS[rng()%4];
            }
            break;
        case 8: // 大数据，连续删除测试
            N = 100000;
            // 前半段加，后半段删
            for(int i=0; i<N/2; ++i) S += OPTS[rng()%4];
            for(int i=N/2; i<N; ++i) S += 'X';
            break;
        case 9: // 最大数据
            N = 1000000;
            for(int i=0; i<N; ++i) {
                if(rng()%100 < 15) S += 'X'; // 15% 删除
                else S += OPTS[rng()%4];
            }
            break;
        case 10: // 最大数据，最终非空
            N = 1000000;
            for(int i=0; i<N; ++i) {
                if(rng()%100 < 5) S += 'X'; // 5% 删除
                else S += OPTS[rng()%4];
            }
            break;
    }

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

    string out_file = to_string(id) + ".out";
    ofstream fout_out(out_file);
    fout_out << solve(N, S) << "\n";
    fout_out.close();

    cout << "Generated Case " << id << endl;
}

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

这道题以DNA聚合酶的校对机制为背景，形象地解释了 栈（Stack） 的工作原理。相比于之前的数学或数组题，这道题更侧重于数据结构的动态操作。希望这能成为你题库中的一道好题！