这是一道结合高中生物 “表观遗传学”（Epigenetics）中 CpG岛 概念的题目，难度定位在GESP 5级（约等于CSP-J 普及组第二题或第三题难度）。

---

题目：寻找基因启动子（CpG Island Hunter）

【背景知识讲解】

在高中生物必修二《遗传与进化》中，我们学习了DNA由4种碱基组成：A（腺嘌呤）、T（胸腺嘧啶）、C（胞嘧啶）、G（鸟嘌呤）。

但在更深入的表观遗传学中，有一个重要的概念叫做CpG位点。

• CpG位点：指的是DNA单链上，一个胞嘧啶（C）紧接着一个鸟嘌呤（G）的结构（即 ...CG...，注意方向是5'到3'，这里简化为字符串顺序）。这里的 p 代表磷酸二酯键。
• CpG岛（CpG Island）：通常，DNA中CpG位点的出现频率是很低的。但在基因的启动子（Promoter，基因开始转录的地方）附近，CpG位点会成簇高密度出现，这一段高密度的区域被称为“CpG岛”。

科学家常常通过寻找DNA序列中CpG含量最高的区域，来预测基因的位置。

【题目描述】

作为一名生物信息学实习生，你拿到了一条很长的DNA碱基序列 $S$（只包含字符 'A', 'T', 'C', 'G'）。 导师希望你在这条序列中，找到一个长度固定为 $L$ 的片段，使得该片段中包含的 CpG位点 的数量最多。

注意：

1. “CpG位点”定义为子串 "CG"。例如序列 ACGCG 中，包含2个CpG位点（下标1-2和3-4，下标从0开始）。
2. 如果有多个片段的CpG位点数量相同且均为最大，请输出起始位置最靠前（下标最小）的那一个。

【输入格式】

第一行包含两个整数 $N$ 和 $L$，分别表示DNA序列的总长度和需要截取的片段长度。 第二行包含一个长度为 $N$ 的字符串 $S$，表示DNA序列。

【输出格式】

输出一行，包含两个整数，中间用空格隔开。 第一个整数是该片段的起始下标（从1开始计数）。 第二个整数是该片段中CpG位点的数量。

【样例数据】

输入：

10 5
ACGCGTCGAT

输出：

1 2

样例解释：

• 取 $S[1..5]$ (ACGCG)，包含2个 "CG"，起始位置1。（最优）
• 取 $S[5..9]$ (GTCGA)，包含1个 "CG"。
• 取 $S[6..10]$ (TCGAT)，包含1个 "CG"。

【数据范围】

• 对于 100% 的数据：$1 \le L \le N \le 1,000,000$。

---

一、 思路提示（不提供完整代码）

1. 数据的预处理：题目关心的是 "CG" 这种组合。原始字符串是由 A,T,C,G 组成的，处理起来比较麻烦。能不能把这个问题转化一下？比如，我们可以标记出每一个 "CG" 出现的位置。如果 $S[i]$ 是 'C' 且 $S[i+1]$ 是 'G'，那么这就贡献了一个计数。
2. 核心目标：我们需要在一个长度为 $L$ 的“窗口”内，统计上述标记的数量。
3. 暴力法的局限：如果你打算从第1个字符开始截取长度为 $L$ 的子串数一遍，再从第2个字符开始截取数一遍……你会发现计算量太大（见后文分析）。
4. 观察相邻区间的关系：
   • 区间 A：下标 $[1, L]$
   • 区间 B：下标 $[2, L+1]$
   • 区间 B 和 区间 A 相比，只是少了一个头，多了一个尾。中间的部分完全没有变。利用这个性质，你还需要每次重新数中间那几千几万个碱基吗？

---

二、 预备知识点总结

要解决这道题，学生需要掌握以下 GESP 5级 / CSP-J 考纲中的知识点：

1. 字符串的基本操作：读取字符串（字符数组或 std::string），下标访问，字符比较。
2. 模拟算法：理解题目意图并将其转化为代码逻辑。
3. 时间复杂度分析基础：理解为什么双重循环在 $N=10^6$ 时会超时。
4. 滑动窗口算法（Sliding Window）：这是本题的核心，属于线性扫描算法的一种优化技巧。

---

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

假设我站在黑板前，你是我的学生。我们拿出一张草稿纸，一起来推导。

教练：“看到 $N=1,000,000$（一百万），你的第一反应是什么？” 学生：“不能用 $O(N^2)$，程序会跑不动，必须在 1秒内也就是 $O(N)$ 左右解决。”

教练：“很好。那我们先看看最笨的方法（暴力法）是怎么做的，以此来寻找优化的灵感。” 教练在草稿纸上画图：

序列 S:  A  C  G  C  G  T  C  G  A  T ...
下标:    1  2  3  4  5  6  7  8  9 10

假设 $L=5$。

步骤 1（暴力思维）：

• 窗口1 (下标1-5): A C G C G。

  • 我们需要遍历这个小窗口：
  • 位置1-2 (AC) ×
  • 位置2-3 (CG) √ (记1分)
  • 位置3-4 (GC) ×
  • 位置4-5 (CG) √ (记1分)
  • 总分：2。

• 窗口2 (下标2-6): C G C G T。

  • 遍历小窗口：
  • 位置2-3 (CG) √
  • 位置3-4 (GC) ×
  • 位置4-5 (CG) √
  • 位置5-6 (GT) ×
  • 总分：2。

教练：“停！发现问题了吗？当我们从窗口1移到窗口2时，我们在重复检查哪些位置？” 学生：“中间的 C G C G 部分被检查了两次。” 教练：“对！如果 $L$ 是 10000，那中间的 9999 个位置都被重复检查了。这太浪费了。我们怎么利用‘窗口1’的结果来快速算出‘窗口2’的结果？”

教练画出“滑动窗口”示意图：

       [  离开  ]                 [  进入  ]
旧窗口: [ A  C  G  C  G ] T  C  G  A  T
新窗口:   A [ C  G  C  G  T ] C  G  A  T

教练引导思考：

1. 初始状态：先算出第1个窗口（1到L）的得分，记为 current_score。
2. 移动一步：
   • 减法：最左边那个被移出去的组合如果是 "CG"，分数减1。
     • 注意细节：移出去的是 $S[i-1]$ 和 $S[i]$ 构成的对吗？并不是，是窗口最左侧的那一对关系。
   • 加法：最右边新进来的那个组合如果是 "CG"，分数加1。
3. 更新答案：比较 current_score 和 max_score。

教练补充细节（容易踩坑的地方）： “一定要注意，判断 'CG' 涉及到两个字符。 如果窗口范围是 $[i, j]$，我们统计的是 $k \in [i, j-1]$ 使得 $S[k]=='C' \land S[k+1]=='G'$。 当窗口向右移动一格：

• 移出的是下标 $i$。我们要检查 $S[i]$ 和 $S[i+1]$ 是不是构成 'CG' 吗？
  • 如果是，那这个 'CG' 就随着窗口移动而消失了吗？是的。
• 移入的是下标 $j+1$。我们要检查 $S[j]$ 和 $S[j+1]$ 是不是构成 'CG'。

复杂度分析：

• 暴力法：每一个窗口都要遍历 $L$ 次，共有 $N$ 个窗口。总复杂度 $O(N \times L)$。如果 $N, L$ 都是 $10^5$，运算量就是 $10^{10}$，绝对超时。
• 滑动窗口优化：每个字符只进窗口一次、出窗口一次。总复杂度 $O(N)$。完美解决。

---

四、 读题关键词总结（做题策略）

针对此类题目，我在平时的训练中会要求大家圈出这几个关键词：

1. “连续子串” / “片段” $\rightarrow$ 暗示这是区间问题，通常涉及双指针或滑动窗口。
2. “长度固定为 L” $\rightarrow$ 滑动窗口最强烈的信号。如果是“长度不固定”，可能是前缀和或动态规划。
3. “最大数量” $\rightarrow$ 需要一个变量 max_cnt 和 best_start_index 来记录过程中的最优解。
4. “位置最靠前” $\rightarrow$ 更新答案时的条件是 if (current > max) 而不是 if (current >= max)。只有严格大于才更新位置，这样能保留最早出现的。
5. 数据范围 $10^6$ $\rightarrow$ 必须设计线性时间复杂度 $O(N)$ 的算法。

---

加油！试着在草稿纸上画一画那个滑动的框，代码自然就出来了。