DNA聚合酶的校对

ID: 19308

传统题

1000ms

32MiB

尝试: 1

已通过: 1

难度: 10

上传者:

tobyforever

我们已经涉及了DNA序列分析、细胞生命历程、自然选择、遗传密码和多基因遗传。这一次，我们将目光投向高中生物必修二中关于 DNA复制（DNA Replication） 的一个极其精细的机制——校对功能（Proofreading）。

这道题目考察的是栈（Stack）这一核心数据结构的应用，或者说是字符串的动态操作。难度定位 GESP 5级（约等于 CSP-J T2）。

题目：DNA聚合酶的校对 (DNA Polymerase's Proofreading)

【背景知识讲解】

在高中生物必修二《遗传与进化》中，我们学习了DNA分子的半保留复制。这个过程需要 DNA聚合酶（DNA Polymerase） 将游离的脱氧核苷酸连接到模板链上。

但是，DNA聚合酶并不是一台只会“无脑”拼接的机器。它具有惊人的 “校对”（Proofreading） 功能：

聚合作用：通常情况下，它将碱基（A, T, C, G）一个接一个地加到新合成的子链末端（5' $\to$ 3'方向）。
外切酶活性：如果它发现刚刚添加的那个碱基配对错了（例如A配了C），它会利用 3' $\to$ 5' 外切酶活性，“倒车”回去把那个错误的碱基切除（Backtrack），然后再尝试添加正确的碱基。

正是这种“写一个、检查一个、错了就删”的机制，保证了DNA复制的极高准确性。

【题目描述】

作为一名生物模拟系统的开发者，你需要模拟 DNA 聚合酶在复制过程中的行为。系统输入一串由字符组成的“操作指令”字符串 $S$ 。

如果字符是 'A', 'T', 'C', 'G'：表示聚合酶识别到了对应的碱基，并将其添加到新链的末端。
如果字符是 'X'（代表 Error Detected）：表示聚合酶检测到了刚添加的碱基是错误的，启动校对功能，切除（删除）新链末端的最后一个碱基。

注意：

如果当前新链是空的，遇到 'X' 指令时，聚合酶什么也不做（没有东西可切）。
处理完所有指令后，请输出最终合成的 DNA 单链序列。

【输入格式】

第一行包含一个整数 $N$ ，表示操作指令字符串的长度。第二行包含一个长度为 $N$ 的字符串 $S$ ，仅包含字符 'A', 'T', 'C', 'G', 'X'。

【输出格式】

输出一行字符串，表示经过校对后最终生成的 DNA 序列。如果不包含任何碱基，输出空行。

【样例数据】

输入：

10
ATCGXXACGT

输出：

ATACGT

【样例解释】

我们需要模拟 DNA 聚合酶处理指令序列 ATCGXXACGT 的全过程。初始时，DNA 链为空。

步骤	读取指令	操作类型	操作详情	当前 DNA 链状态
1	A	聚合 (添加)	将 A 加到末尾	`A`
2	T		将 T 加到末尾	`AT`
3	C		将 C 加到末尾	`ATC`
4	G		将 G 加到末尾	`ATCG`
5	X	校对 (删除)	发现错误，切除末尾的 G	`ATC`
6	X	校对 (删除)	发现错误，切除末尾的 C	`AT`
7	A	聚合 (添加)	将 A 加到末尾	`ATA`
8	C		将 C 加到末尾	`ATAC`
9	G		将 G 加到末尾	`ATACG`
10	T		将 T 加到末尾	`ATACGT`

最终结果：经过所有指令处理后，DNA 链的序列为 ATACGT。

【补充边界测试建议】

为了确保代码的健壮性（特别是处理“空栈弹出”的情况），建议在后台测试数据中加入以下情况：

空链删除（边界情况）：
- 输入：3 XAX
- 解释：
  - 遇到 X：链为空，什么也不做（链仍为空）。
  - 遇到 A：添加 A（链为 A）。
  - 遇到 X：删除 A（链为空）。
- 输出：（空行）
连续清空：
- 输入：4 ABXX
- 解释：添加 A, B $\to$ AB；删除 B $\to$ A；删除 A $\to$ (空)。
- 输出：（空行）

【数据范围】

对于 100% 的数据： $1 \le N \le 1,000,000$ 。
输入字符串仅包含 'A', 'T', 'C', 'G', 'X'。

一、思路提示

生活中的类比：
- 这就像我们在电脑上打字。A, T, C, G 是字母键，X 就是键盘上的 Backspace（退格键）。
- 如果你打错了，按一下退格键，光标前面的字就没了。再按一下，又没了一个。
数据结构的选择：
- 我们需要一种数据结构，支持“在末尾添加”和“在末尾删除”。
- 这正是**栈（Stack）**的典型特性：后进先出（LIFO）。
- 最新进来的碱基，如果遇到 X，是最先被删掉的。
实现方式：
- 你可以使用 C++ STL 自带的 std::stack<char>。
- 但其实，std::string 或 std::vector<char> 本身就支持 push_back()（入栈）和 pop_back()（出栈），用它们来模拟栈会更方便，因为最后题目要求输出整个字符串，string 可以直接输出。
边界条件：
- 如果当前栈是空的（链里没有碱基），这时候来了个 X 怎么办？
- 题目说了“什么也不做”。所以在执行删除操作前，一定要判断 !st.empty()（栈不为空）。

二、预备知识点总结

**栈（Stack）**的概念：理解后进先出。
STL容器操作：
- string 的 push_back(char c)：在末尾添加字符。
- string 的 pop_back()：删除末尾字符。
- string 的 empty()：判断是否为空。
时间复杂度分析：每个字符只处理一次， $O(N)$ 。

三、启发式教学：草稿纸上的推理过程

教练：“大家拿出一张纸，我们来模拟这个酶的工作。把纸当成 DNA 链。” 学生：“好的。”

操作流：A T X C X X G
步骤 1：读到 A。
- 动作：写上 A。
- 纸上：A
步骤 2：读到 T。
- 动作：写上 T。
- 纸上：A T
步骤 3：读到 X。
- 动作：划掉最后一个字（T）。
- 纸上：A
步骤 4：读到 C。
- 动作：写上 C。
- 纸上：A C
步骤 5：读到 X。
- 动作：划掉最后一个字（C）。
- 纸上：A
步骤 6：读到 X。
- 动作：划掉最后一个字（A）。
- 纸上：(空)
步骤 7：读到 G。
- 动作：写上 G。
- 纸上：G

教练：“看，这其实就是我们在做一个‘堆叠’的游戏。进一个，叠上去；退一个，拿下来。在编程里，这就叫栈。”

四、读题关键词总结

“添加” / “切除” $\rightarrow$ 对应 push 和 pop 操作。
“末端” $\rightarrow$ 暗示操作只发生在序列的一端，这是栈的特征。
“如果为空则不做” $\rightarrow$ 必须进行 empty 检查，防止运行时错误（Runtime Error）。

#19308. DNA聚合酶的校对