这是一个非常实用的需求。为了方便你直接在本地生成一套完整的OJ测试数据，我编写了一个全自动的数据生成器。

这个程序会：

1. 自动生成 1.in 到 10.in。
2. 内置了标准题解算法，自动读取刚才生成的 .in 文件，计算结果并写入对应的 .out 文件。
3. 覆盖策略：从极小数据、边界数据（L=1, L=N）、稀疏数据、密集数据到满级大数据（N=100W）全覆盖。

数据生成器代码 (Generator.cpp)

你需要将此代码保存为 generator.cpp，编译并运行即可。它会在当前目录下生成20个文件。

/**
 * GESP 5级/CSP-J 题目：寻找基因启动子
 * 测试数据生成器 (Data Generator)
 * 
 * 功能：生成 1.in ~ 10.in 以及对应的 1.out ~ 10.out
 */

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

using namespace std;

// --- 配置部分 ---
const int TEST_CASE_COUNT = 10;
const char BASE[] = {'A', 'T', 'C', 'G'};

// 随机数生成器初始化
mt19937 rng(time(0));

// --- 核心算法 (用于生成 .out 文件) ---
// 这是一个完全正确的 O(N) 滑动窗口解法
pair<int, int> solve(int N, int L, const string& S) {
    if (L < 2) return {1, 0};

    int current_cnt = 0;
    // 初始化第一个窗口
    for (int i = 0; i < L - 1; ++i) {
        if (S[i] == 'C' && S[i+1] == 'G') {
            current_cnt++;
        }
    }

    int max_cnt = current_cnt;
    int best_pos = 1;

    // 滑动
    for (int i = 1; i <= N - L; ++i) {
        // 移出 S[i-1]...S[i]
        if (S[i-1] == 'C' && S[i] == 'G') {
            current_cnt--;
        }
        // 移入 S[i+L-2]...S[i+L-1]
        if (S[i+L-2] == 'C' && S[i+L-1] == 'G') {
            current_cnt++;
        }

        if (current_cnt > max_cnt) {
            max_cnt = current_cnt;
            best_pos = i + 1;
        }
    }
    return {best_pos, max_cnt};
}

// --- 辅助函数：生成随机DNA序列 ---
// mode 0: 均匀分布
// mode 1: 高密度 CG (CpG岛)
// mode 2: 极低密度 (主要是A和T)
string generate_dna(int n, int mode) {
    string s = "";
    s.resize(n);
    
    for (int i = 0; i < n; ++i) {
        int r = rng() % 100;
        if (mode == 1) { // 高密度 CG
            // 40% C, 40% G, 10% A, 10% T
            if (r < 40) s[i] = 'C';
            else if (r < 80) s[i] = 'G';
            else if (r < 90) s[i] = 'A';
            else s[i] = 'T';
        } else if (mode == 2) { // 低密度
            // 5% C, 5% G, 45% A, 45% T
            if (r < 5) s[i] = 'C';
            else if (r < 10) s[i] = 'G';
            else if (r < 55) s[i] = 'A';
            else s[i] = 'T';
        } else { // 均匀
            s[i] = BASE[rng() % 4];
        }
    }
    
    // 特殊构造：如果是 mode 1，我们可以强制插入一些连续的 CGCG 以保证肯定有解
    if (mode == 1 && n > 10) {
        int pos = rng() % (n - 10);
        for(int k=0; k<10; k+=2) {
            s[pos+k] = 'C';
            s[pos+k+1] = 'G';
        }
    }
    
    return s;
}

// --- 主生成逻辑 ---
void make_case(int id) {
    int N, L;
    string S;
    
    // 根据测试点编号设计数据强度和特征
    switch(id) {
        case 1: 
            // 样例数据 (完全一致)
            N = 10; L = 5;
            S = "ACGCGTCGAT";
            break;
            
        case 2:
            // 极小数据：N=L，整个字符串就是一个窗口
            N = 20; L = 20;
            S = generate_dna(N, 0);
            break;
            
        case 3:
            // 边界情况：L=1，不可能有CG，答案应该是 1 0
            N = 100; L = 1;
            S = generate_dna(N, 0);
            break;
            
        case 4:
            // 小数据：常规随机
            N = 1000; L = 50;
            S = generate_dna(N, 0);
            break;
            
        case 5:
            // 稀疏数据：很难找到CG
            N = 5000; L = 200;
            S = generate_dna(N, 2);
            break;
            
        case 6:
            // 密集数据：CGCG非常多
            N = 5000; L = 100;
            S = generate_dna(N, 1);
            break;
            
        case 7:
            // 中等数据：N=10^5
            N = 100000; L = 1000;
            S = generate_dna(N, 0);
            break;
            
        case 8:
            // 大数据：N=10^6，小窗口
            N = 1000000; L = 10;
            S = generate_dna(N, 0);
            break;
            
        case 9:
            // 大数据：N=10^6，大窗口 (N/2)
            N = 1000000; L = 500000;
            S = generate_dna(N, 0);
            break;
            
        case 10:
            // 极限数据：N=10^6，L=N-1，几乎全长
            N = 1000000; L = 999999;
            S = generate_dna(N, 0);
            break;
            
        default:
            N = 100; L = 10; S = generate_dna(N, 0); break;
    }

    // 1. 写入 .in 文件
    string in_file = to_string(id) + ".in";
    ofstream fout_in(in_file);
    fout_in << N << " " << L << "\n";
    fout_in << S << "\n";
    fout_in.close();

    // 2. 计算答案并写入 .out 文件
    string out_file = to_string(id) + ".out";
    ofstream fout_out(out_file);
    
    pair<int, int> ans = solve(N, L, S);
    
    fout_out << ans.first << " " << ans.second << "\n";
    fout_out.close();
    
    cout << "Generated Test Case " << id << ": N=" << N << ", L=" << L << endl;
}

int main() {
    cout << "Start generating data..." << endl;
    for (int i = 1; i <= TEST_CASE_COUNT; ++i) {
        make_case(i);
    }
    cout << "All done! 20 files created." << endl;
    return 0;
}

测试点详细设计说明（Coverage Analysis）

为了保证测试数据的严谨性，我对10个测试点做了如下规划：

1. Test 1 (Sample):

   • 目的: 验证题目样例，确保理解无误。
   • 数据: 10 5, ACGCGTCGAT。

2. Test 2 (Full Length):

   • 目的: 边界测试。当 $N=L$ 时，窗口无法滑动，只检查一次。
   • 数据: $N=20, L=20$。

3. Test 3 (L < 2):

   • 目的: 特殊边界。$L=1$ 时，无法容纳 "CG"，程序应健壮地输出 1 0，防止数组越界。
   • 数据: $N=100, L=1$。

4. Test 4 (Small Random):

   • 目的: 基础逻辑检查。
   • 数据: $N=1000, L=50$。

5. Test 5 (Sparse Case):

   • 目的: 生物学背景模拟。有些DNA区域GC含量极低。测试在“贫瘠”区域寻找最优解（可能最大值只有0或1，需正确返回第一个位置）。
   • 数据: $N=5000, L=200$，高概率生成 'A' 和 'T'。

6. Test 6 (Dense Case):

   • 目的: 性能与正确性。高密度 'CG' 意味着 current_cnt 变化频繁，且可能有多个位置数值相同，验证是否返回了下标最小的那个。
   • 数据: $N=5000, L=100$，高概率生成 'C' 和 'G'。

7. Test 7 (Medium Scale):

   • 目的: 过渡到大数据，检查 $O(N^2)$ 算法是否开始变慢（虽然 $10^5$ 还能勉强跑过，但为大数据做铺垫）。
   • 数据: $N=10^5, L=1000$。

8. Test 8 (Max N, Small Window):

   • 目的: 极限性能测试。$N=10^6$，小窗口意味着滑动次数最多（接近 $10^6$ 次）。
   • 数据: $N=10^6, L=10$。

9. Test 9 (Max N, Large Window):

   • 目的: 内存与缓存友好性测试。$N=10^6$，窗口极大。
   • 数据: $N=10^6, L=500,000$。

10. Test 10 (Almost Full):

    • 目的: 边界压力测试。
    • 数据: $N=10^6, L=999,999$。

使用方法

1. 复制上面的代码，保存为 generator.cpp。
2. 使用 C++ 编译器编译：g++ generator.cpp -o gen -O2。
3. 运行：./gen (Windows下是 gen.exe)。
4. 你的目录下会出现 1.in, 1.out ... 10.in, 10.out。
5. 将这些文件打包上传到你的OJ题目后台即可。

这是一个非常标准的**滑动窗口（Sliding Window）**算法题目。以下是符合NOIP/GESP要求的C++14标准题解代码。

核心代码 (C++14 Standard)

/**
 * 题目：寻找基因启动子 (CpG Island Hunter)
 * 算法：滑动窗口 (Sliding Window)
 * 难度：GESP 5级 / CSP-J T2-T3
 */

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

using namespace std;

int main() {
    // 1. 基础优化：关闭输入输出流同步，提高读写速度
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, L;
    if (!(cin >> N >> L)) return 0;
    
    string S;
    cin >> S;

    // 特殊情况处理：如果窗口长度小于2，不可能包含 "CG"
    if (L < 2) {
        // 输出起始位置1，数量0
        cout << "1 0" << endl;
        return 0;
    }

    // --- 步骤一：初始化第一个窗口 ---
    // 窗口范围：下标 [0, L-1]
    int current_cnt = 0;
    for (int i = 0; i < L - 1; ++i) {
        // 检查每一对相邻字符
        if (S[i] == 'C' && S[i+1] == 'G') {
            current_cnt++;
        }
    }

    // 记录当前的最佳结果
    int max_cnt = current_cnt;
    int best_pos = 1; // 题目要求1-based index，初始对应下标0

    // --- 步骤二：开始滑动窗口 ---
    // i 表示新窗口的【起始下标】
    // 原始窗口是 [0, L-1]，下一个窗口是 [1, L]，直到 [N-L, N-1]
    for (int i = 1; i <= N - L; ++i) {
        
        // 1. 处理“离开”窗口的部分：
        // 只有当最左边刚刚滑出的那一对是 "CG" 时，计数器才减1
        // 上一个窗口的起始是 i-1，滑出的配对是 S[i-1] 和 S[i]
        // 注意：虽然 S[i] 还在新窗口里，但它和 S[i-1] 组成的 "CG" 关系已经不在新窗口内了
        if (S[i-1] == 'C' && S[i] == 'G') {
            current_cnt--;
        }

        // 2. 处理“进入”窗口的部分：
        // 新窗口的结束下标是 i + L - 1
        // 新加入的配对是 S[i + L - 2] 和 S[i + L - 1]
        if (S[i + L - 2] == 'C' && S[i + L - 1] == 'G') {
            current_cnt++;
        }

        // 3. 更新答案
        // 题目要求：如果有多个相同最大值，输出位置最靠前的
        // 所以这里使用 > 而不是 >=，只有严格大于才更新位置
        if (current_cnt > max_cnt) {
            max_cnt = current_cnt;
            best_pos = i + 1; // 将0-based下标转换为1-based
        }
    }

    cout << best_pos << " " << max_cnt << endl;

    return 0;
}

代码详细分析

1. 易错点与关键点注释

• 下标换算：这是最容易晕的地方。
  • 如果当前窗口起始下标为 i，长度为 L，则结束下标为 i + L - 1。
  • 滑出判断：涉及的是 S[i-1] 和 S[i]。为什么？因为在上一轮（起始 i-1）中，它们贡献了一个潜在的 "CG"。现在 i-1 离开了，这个贡献要收回。
  • 滑入判断：涉及的是窗口最右端的两个字符，即倒数第二个 S[i + L - 2] 和倒数第一个 S[i + L - 1]。
• 边界条件：
  • 当 L=1 时，无法构成 "CG"，如果不特判 L < 2，循环 i < L - 1 会直接跳过，但后面的逻辑可能会因为数组越界（如访问 i + L - 2 变成 i - 1）而出错。
• 输入输出加速：ios_base::sync_with_stdio(false);。对于 $10^6$ 级别的字符读入，这也是一个好习惯，防止I/O超时。

2. 时间和空间复杂度分析

空间复杂度分析：

• 我们需要存储整个字符串 $S$，长度为 $N$。
• 使用了几个整型变量（N, L, current_cnt, max_cnt, best_pos, i）。
• 没有开辟额外的数组（如前缀和数组等）。
• 结论：$O(N)$。对于 $N=1,000,000$，内存占用约为 1MB 多一点，远小于竞赛常见的 256MB/512MB 限制。

时间复杂度分析思考过程：

1. 初始化阶段：我们需要遍历第一个窗口，循环次数为 $L$。
2. 滑动阶段：
   • 循环从 $i=1$ 到 $N-L$。总共执行约 $N-L$ 次。
   • 在循环内部，只进行了常数次操作（4次字符比较，1次整数比较，1次赋值）。这些操作是 $O(1)$ 的。
3. 总运算量：$L + (N - L) \times O(1) \approx N$。
4. 结论：$O(N)$。
   • 当 $N=10^6$ 时，计算机每秒能处理约 $10^8$ 次基本运算。$10^6$ 次运算耗时约 0.01秒，完全满足 1秒 的时间限制。

3. 为什么不能用暴力法（复杂度对比）

如果学生写的是双重循环（暴力法）：

// 错误示范
for(int i = 0; i <= N - L; i++) {
    int cnt = 0;
    for(int j = 0; j < L - 1; j++) { // 内部又遍历一遍 L
        if(S[i+j] == 'C' && S[i+j+1] == 'G') cnt++;
    }
    // ...
}

• 最坏情况：当 $L = N/2$ 时（例如 $N=10^6, L=500,000$）。
• 运算次数约为 $(N/2) \times (N/2) = N^2/4 \approx 2.5 \times 10^{11}$ 次。
• 这需要跑几千秒，肯定会 TLE (Time Limit Exceeded)。

4. 优化建议

当前的滑动窗口已经是本题的时间复杂度最优解（线性复杂度）。如果还要在常数级别“吹毛求疵”地优化（虽然比赛中通常不需要），可以考虑：

• 减少分支预测失败：将 if 判断转化为位运算或算术运算（例如 cnt += (expression)），但在现代编译器优化下，差异微乎其微。
• 位压缩（Bitset）：如果 $N$ 极大（如 $10^8$），可以用 std::bitset 标记所有 "CG" 的位置，然后问题转化为“区间求和”。但这需要 $O(N/64)$ 的空间和时间，对于本题 $N=10^6$ 来说，纯模拟的滑动窗口可读性更好且足够快。