你好！非常高兴能继续为你设计题目。

看到你已经掌握了滑动窗口（CpG岛）、排序与环形处理（质粒切割）、标记法（信使RNA剪接）。

这一次，我们来一道涉及模拟（Simulation）和状态更新的题目。这道题的模型原型是计算机科学中著名的“一维元胞自动机”（Cellular Automaton），但我们将其包装在高中生物必修一《分子与细胞》中细胞的生命历程这一背景下。

题目难度定位 GESP 5级（CSP-J T2/T3），考察重点是多轮次的状态模拟以及辅助数组（Double Buffering）的使用。

---

题目：培养皿中的生存游戏 (The Game of Cellular Survival)

【背景知识讲解】

在高中生物必修一中，我们学习了细胞的增殖、分化、衰老和凋亡。细胞的生存环境对其命运有决定性影响。 生物学中有两个有趣的现象：

1. 接触抑制（Contact Inhibition）：正常细胞在培养皿中贴壁生长，当细胞相互接触汇合成片时，会停止分裂增殖。如果周围太拥挤，细胞甚至会死亡（凋亡）。
2. 旁分泌信号（Paracrine Signaling）：细胞往往需要接收邻近细胞分泌的生长因子才能存活。如果一个细胞完全孤立，没有邻居，它可能会因为缺乏信号而“孤独死”。

基于这两个原理，我们可以模拟一排细胞的生存演变过程。

【题目描述】

实验室在一条狭长的微流控通道（可以看作一维数组）中培养了一排细胞。 通道共有 $N$ 个格子，编号 $1$ 到 $N$。每个格子在初始时刻要么有一个活细胞（记为 1），要么是空的（记为 0）。

细胞的生存状态每过 1 秒会同时更新一次。更新规则如下（基于上一秒的状态）：

1. 对于原本是“活细胞”的位置：

   • 过于拥挤：如果它的左边和右边都有活细胞（邻居数量 $= 2$），它会因为接触抑制而死亡（变为 0）。
   • 过于孤单：如果它的左边和右边都没有活细胞（邻居数量 $= 0$），它会因为缺乏生长因子而死亡（变为 0）。
   • 环境适宜：如果它恰好只有 $1$ 个邻居（左边或右边），它将继续存活（保持 1）。

2. 对于原本是“空位”的位置：

   • 繁殖：如果它的左边和右边都有活细胞（邻居数量 $= 2$），这两个邻居会共同作用，分裂出一个新细胞填充该空位（变为 1）。
   • 否则，保持为空（保持 0）。

边界说明： 对于通道两端的格子（编号 $1$ 和 $N$），它们只有一个邻居（分别对应编号 $2$ 和 $N-1$）。

• 为了简化计算，我们假设通道之外（下标 $0$ 和 $N+1$）永远是空位（0）。

现在给出初始状态，请计算经过 $T$ 秒后的细胞分布情况。

【输入格式】

第一行包含两个整数 $N$ 和 $T$，表示通道长度和模拟时间。 第二行包含一个长度为 $N$ 的字符串 $S$，仅由字符 '0' 和 '1' 组成，表示初始状态。

【输出格式】

输出一行长度为 $N$ 的字符串，表示 $T$ 秒后的状态。

【样例数据】

输入：

7 1
0101010

输出：

0010100

样例解释： 初始状态：0 1 0 1 0 1 0 (下标 1~7)

• 位置 2 (1): 左(0) 右(0) $\to$ 孤单，死 $\to$ 0
• 位置 3 (0): 左(1) 右(1) $\to$ 繁殖，生 $\to$ 1
• 位置 4 (1): 左(0) 右(0) $\to$ 孤单，死 $\to$ 0
• 位置 5 (0): 左(1) 右(1) $\to$ 繁殖，生 $\to$ 1
• 位置 6 (1): 左(0) 右(0) $\to$ 孤单，死 $\to$ 0
• 其余位置维持 0。 1秒后结果：0 0 1 0 1 0 0。

【数据范围】

• $3 \le N \le 1,000$。
• $1 \le T \le 1,000$。
• 对于 100% 的数据，字符串只包含 '0' 和 '1'。

---

一、 思路提示

1. 同时更新的陷阱：

   • 题目中强调了“每过 1 秒会同时更新”。
   • 比如计算位置 $i$ 的新状态时，需要查看位置 $i-1$ 和 $i+1$。
   • 如果你直接在原数组上修改：S[i] = 新状态，当你接着计算 S[i+1] 时，你用到的 S[i] 就是刚刚改过的新状态了，但这不符合“基于上一秒状态”的规则。
   • 核心技巧：你需要两个数组（或两个字符串）。一个存“上一秒（旧）”，一个存“这一秒（新）”。计算完一整轮后，再把“新”的变成“旧”的，准备下一轮。这叫双缓冲（Double Buffering）。

2. 边界处理：

   • 题目说了，下标 $1$ 的左边（下标 $0$）和下标 $N$ 的右边（下标 $N+1$）视为 0。
   • 最方便的做法是：开一个长度为 $N+2$ 的数组，把 $S$ 放在中间（下标 $1$ 到 $N$），而下标 $0$ 和 $N+1$ 始终保持为 0。这样在循环 1 到 N 时，就不需要写特殊的 if (i==1) 或 if (i==N) 判断了，直接访问 i-1 和 i+1 即可。

3. 规则逻辑梳理：

   • 让 cnt = S[i-1] + S[i+1] （统计邻居数量，字符 '0'/'1' 要转为数字）。
   • 如果 S[i] == '1'：
     • cnt == 2 $\to$ 死 (0)
     • cnt == 0 $\to$ 死 (0)
     • cnt == 1 $\to$ 活 (1)
   • 如果 S[i] == '0'：
     • cnt == 2 $\to$ 生 (1)
     • 其他 $\to$ 空 (0)

---

二、 预备知识点总结

1. 模拟算法：根据题目描述的规则，一步步执行。
2. 双缓冲思想 / 辅助数组：解决“旧值被新值覆盖”导致计算错误的问题。
3. 哨兵节点（Sentinel）：通过填充边界（padding）来简化边界条件的判断代码。

---

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

教练：“我们来玩这个细胞游戏。假设现在是第 0 秒，状态是 0 1 1 0 0。” 学生：“好的。”

教练：“我们先算第 1 秒。记得，我们要用第 0 秒的样子来判断。”

• 位置 1 (0)：左边没东西(视为0)，右边是1。邻居数=1。我是空位，邻居不是2，所以我还是 0。
• 位置 2 (1)：左边(0)，右边(1)。邻居数=1。我是活的，只有1个邻居，所以我存活 (1)。
• 位置 3 (1)：左边(1)，右边(0)。邻居数=1。我是活的，只有1个邻居，所以我存活 (1)。
• 位置 4 (0)：左边(1)，右边(0)。邻居数=1。我是空位，邻居不是2，所以我还是 0。
• 位置 5 (0)：...还是 0。

结果：0 1 1 0 0。 教练：“咦？好像没变？” 学生：“是的，看起来这个状态比较稳定。”

教练：“那我们换个刺激的：0 1 0 1 0（中间隔开）。”

• 位置 2 (1)：左0右0 $\to$ 孤单 $\to$ 死 (0)。
• 位置 3 (0)：左1右1 $\to$ 繁殖 $\to$ 生 (1)。
• 位置 4 (1)：左0右0 $\to$ 孤单 $\to$ 死 (0)。 结果：0 0 1 0 0。 教练：“看，细胞位置发生了移动！这就是‘自动机’的神奇之处。”

时间复杂度分析：

• 我们要模拟 $T$ 轮。
• 每一轮要遍历 $N$ 个格子。
• 总复杂度是 $O(N \times T)$。
• 题目中 $N=1000, T=1000$，乘积是 $10^6$（一百万）。计算机一秒可以算 $10^8$ 次。所以完全没问题！

---

四、 读题关键词总结

1. “同时更新” $\rightarrow$ 必须用两个数组（current 和 next），不能原地修改。
2. “基于上一秒的状态” $\rightarrow$ 再次确认需要双缓冲。
3. “边界视为 0” $\rightarrow$ 暗示可以在数组两头多开两个空间，避免数组越界。
4. $N, T \le 1000$ $\rightarrow$ $O(N^2)$ 或 $O(NT)$ 的算法是可以接受的。

---